Inleiding Grafentheorie

Introduction to Graph theory

Studiewijzer 2024/2025

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

• Grafen: de student kent definities, voorbeelden en basiseigenschappen van de volgende concepten: graaf, graad, volledige graaf, volledig bipartiete graaf, deelgraaf, complement, lijngraaf, paden en wandelingen, circuits, samenhang, bomen en bossen, Euler-grafen, Hamilton-grafen, bipartiete grafen, gerichte grafen, paden en stromen.
• Stellingen: Studenten kunnen de volgende belangrijke stellingen formuleren, bewijzen en toepassen: karakterisatie van Eulergrafen, Stelling van Dirac over Hamiltongrafen, 5-kleurbaarheid 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.
• Technieken: De student kan technieken als dubbel tellen, inductie en het duiventil principe toepassen om er eenvoudige grafentheoretische opgaven mee oplossen.
• Algoritmen: De student kan het algoritme voor het lijnkleuren van bipartiete grafen en het algoritme voor het bepalen van de maximale stroom in een netwerk toepassen.
• De student is zich bewust van de het belang van de historische context van wiskundige problemen en kan daar zelfstandig achtergrondinformatie over opzoeken en verwerken.

Onderwijsvormen

• Hoorcollege
• Werkcollege
• Zelfstudie

Verdeling leeractiviteiten

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Van elke student wordt actieve deelname verwacht aan het onderdeel waarvoor de student staat ingeschreven.
• Naast de algemene eis dat de student actief participeert in het onderwijs, worden de aanvullende eisen per onderdeel in de studiewijzer omschreven. Hier staat ook omschreven voor welke onderdelen van het onderdeel een aanwezigheidsplicht geldt.
• Als een student door persoonlijke omstandigheden niet aanwezig kan zijn bij een verplicht onderdeel van het programma, dient de student 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 persoonlijke omstandigheden.
• 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 tevoren vastgelegd in de studiewijzer en op Canvas.

Toetsing

Het eindcijfer is het tentamencijfer als dit lager is dan een 5.5. Anders is het het maximum van het tentamencijfer en het gewogen gemiddelde van 80% van het tentamencijfer en 20% van de toetsjes (waar het slechtste toetsje niet meetelt).

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

Honoursinformatie

Op dit vak is geen honoursuitbreiding mogelijk.

Contactinformatie

Coördinator

• dr. Guus Regts