Inleiding grafentheorie

Introduction to Theory of Graphs

Studiewijzer 2018/2019

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

Literatuur

• (optioneel) R. J. Wilson : Introduction to Graph Theory 

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
• Presentatie/symposium

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 persoonlijke omstandigheden niet aanwezig kan zijn bij een verplicht onderdeel van het programma, dient hij/zij dit zo snel mogelijk schriftelijk te melden bij de betreffende docent en de studieadviseur.
• 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. Voorwaarden voor voldoende deelname worden van te voren vastgelegd in de studiewijzer en op Canvas.
• 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. In geval van persoonlijke omstandigheden, zoals in OER-A Artikel 6.4 omschreven, wordt in overleg met de studieadviseur een afwijkende regeling voorgesteld.

Toetsing

Inzage toetsing

Om een inzagemoment aan te vragen, kun je contact opnemen met de coördinator.

Opdrachten

huiswerk

• niet becijferd

toets

• becijferd

opgaven

• niet becijferd

Je kunt je huiswerk wel inleveren als je feedback wilt hebben. 

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: http://student.uva.nl

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. Miranda Cheng