Studiewijzer 2019/2020

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

De student kan elementaire definities van de grafentheorie formuleren en er eenvoudige grafentheoretische opgaven mee oplossen.
De student kan de stellingen uit de syllabus formuleren en deze gebruiken om eenvoudige grafentheoretische opgaven mee oplossen.
De student kan technieken als dubbel tellen, inductie en het duiventil principe toepassen om er eenvoudige grafentheoretische opgaven mee oplossen.
De student kan de volgende stellingen uit de syllabus formuleren en bewijzen: 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.
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.

Onderwijsvormen

Hoorcollege
Werkcollege
Zelfstudie

Verdeling leeractiviteiten

Activiteit	Aantal uur
Hoorcollege	14
Tentamen	3
Werkcollege	14
Zelfstudie	53

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 A-6.4 omschreven, wordt in overleg met de studieadviseur een afwijkende regeling voorgesteld.

Toetsing

Onderdeel en weging	Details
Eindcijfer
0.8 (80%) Tentamen	Moet ≥ 5.5 zijn
0.2 (20%) Toetsjes

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

Weeknummer	Onderwerpen	Studiestof
1	Introductie: definitie van een graaf, voorbeelden en veel definities: graad, volledige graaf, volledig bipartiete graaf, deelgraaf, complement, lijngraaf, paden en wandelingen, circuits	1.1-1.9
2	Nog meer definities: samenhang, bomen en bossen, Euler-grafen, Hamilton-grafen, isomorfie	1.10-1.16
3	Kleuren van grafen: kleurgetal, maximum graad, planaire grafen, facetten, Euler-formule	2.1-2.9
4	Kleuren van grafen: 5-kleurbaarhied van planaire grafen, toepassingen van kleuren, bipartiete grafen, lijnkleuren van bipartiete grafen, schoolroosters	2.10-2.15
5	Stromen: gerichte grafen, paden en stromen, waarde van een stroom, maximum-stroom probleem, snedes en hun capaciteit, max-stroom en min-sende.	3.1-3.9
6	Max-stroom algoritme, max-stroom = min-snede,	3.10-3.12
7	Stelling van Menger. Mogelijkheid tot het stellen van vragen over de stof.	3.18
8	Tentamen

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.

Verwerking vakevaluaties

Hieronder vind je de aanpassingen in de opzet van het vak naar aanleiding van de vakevaluaties.

Contactinformatie

Coördinator

dr. Guus Regts

Eigenaar	Bachelor Wiskunde
Coördinator	dr. Guus Regts
Onderdeel van	Dubbele bachelor Wis- en Natuurkunde, jaar 1 Bachelor Wiskunde, jaar 1 Dubbele bachelor Wiskunde en Informatica, jaar 1

Inleiding grafentheorie