Inleiding grafentheorie

Introduction to Theory of Graphs

Studiewijzer 2017/2018

Globale inhoud

Dit vak beoogt de beginselen van de eindige grafentheorie uit te leggen, inclusief enkele toepassingen, zoals het kleuren van grafen en vinden van optimale stromen in netwerken. Een graaf bestaat uit punten en lijnen die sommige punten verbinden. In dit college worden de basisbegrippen geintroduceerd (graad, buren, samenhang, cykels, kleuring) waarna een aantal klassieke problemen wordt besproken: hoe kun je grafen herkennen waar je alle lijnen eenmaal kunt doorlopen en weer op het beginpunt uitkomt, en net zo met alle punten? Welke grafen kun je zo tekenen in het vlak dat de lijnen elkaar niet snijden? Hoe kun je punten van een graaf kleuren zodanig dat buren verschillende kleuren krijgen? Hoeveel kleuren heb je nodig om zo de hoofdstedengraaf van een landkaart te kunnen kleuren? Verder wordt er gekeken naar gerichte grafen (waar de lijnen pijlen zijn) en problemen met betrekking tot stromen in netwerken die je zo kunt beschrijven. 

Studiemateriaal

Syllabus

• 'Grafen: Kleuren en routeren'.

Leerdoelen

Aan het eind van dit vak kan de student:

• elementaire definities van de grafentheorie formuleren en er eenvoudige grafentheoretische opgaven mee oplossen.
• de stellingen uit de syllabus formuleren en deze gebruiken om eenvoudige grafentheoretische opgaven mee oplossen.
• technieken als dubbel tellen, inductie en het duiventil principe toepassen om er eenvoudige grafentheoretische opgaven mee oplossen.
• de volgende stellingen uit de syllabus formuleren en bewijzen: karakterisatie van Eulergrafen, Stelling van Dirac over Hamiltongrafen, 5-kleurraaheid van planaire grafen, de Eulerformule, Lijnkleurbaarheid van bipartiete grafen met Delta kleuren, de stelling van Menger, maximum stroom is ten hoogste de capaciteit van een snede.
• het algoritme voor het lijnkleuren van bipartiete grafen en het algoritme voor het bepalen van de maximale stroom in een netwerk toepassen.

Onderwijsvormen

• Hoorcollege
• Werkcollege
• Zelfstudie

Verdeling leeractiviteiten

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Van elke student wordt actieve deelname verwacht aan het onderdeel waarvoor hij/zij staat ingeschreven.
• Als een student door overmacht niet aanwezig kan zijn bij een verplicht onderdeel van het onderdeel, dient hij/zij dit zo snel mogelijk schriftelijk te melden bij de betreffende docent. De docent kan dan, eventueel na overleg met de studieadviseur, besluiten om de student een vervangende opdracht op te leggen.
• Het is niet toegestaan om verplichte onderdelen van een onderdeel te missen als er geen sprake is van overmacht.
• Bij kwalitatief of kwantitatief onvoldoende deelname, kan de examinator de student uitsluiten van verdere deelname aan het onderdeel of een gedeelte daarvan.
• Bij alle onderwijseenheden van jaar 1 en 2 is een student verplicht bij minimaal 80% van de werkcolleges en tutoraten aanwezig te zijn. Bovendien moet worden deelgenomen aan eventuele tussentoetsen en verplicht gesteld huiswerk. Als niet aan deze verplichting is voldaan, wordt de student uitgesloten voor de herkansing van de onderwijseenheid.

Aanvullende eisen voor dit vak:

Aanwezigheid bij de werkcolleges is verplicht. Als je niet bij minstens 80% van de werkcolleges aanwezig bent geweest dan vervalt je recht op het hertentamen, zoals vermeldt in het OER-B artikel 4.9 lid 2.

Toetsing

Inzage toetsing

De manier van inzage wordt via de webpagina van het vak gecommuniceerd.

Fraude en plagiaat

Dit vak hanteert de algemene 'Fraude- en plagiaatregeling' van de UvA. Hier wordt nauwkeurig op gecontroleerd. Bij verdenking van fraude of plagiaat wordt de examencommissie van de opleiding ingeschakeld. Zie de Fraude- en plagiaatregeling van de UvA: www.uva.nl/plagiaat

Weekplanning

Rooster

Het rooster van dit vak is in te zien op DataNose.

Honoursinformatie

Op dit vak is geen honoursuitbreiding mogelijk.

Aanvullende informatie

Aanbevolen voorkennis: Basiswiskunde.

Contactinformatie

Coördinator

• dr. Guus Regts