Klik hier voor de pdf file met cursus informatie. Hierin staan o.a. de opgaven die per week worden behandeld. Elke week zullen er mogelijk ook extra opgaven zijn en worden op de website aangegeven. De syllabus van A. Schrijver die we gebruiken kan hier gevonden worden. De pdf file met extra opgaven vind je hier. Deze file zal ik af en toe updaten.
Klik hier voor een link naar de opnames van de colleges.
1. College 1. Introductie. Behandeld: Complete grafen, compleet bipartiete grafen, driehoeken, Ramsey getallen (zie deze wikipediapagina voor meer informatie), paden, wandelingen, Euler-wandeling (Secties 1.1-1.10 van de syllabus). Extra opgaven: 1.4, 1.5 en 1.12.
2. College 2. Behandeld: Euler-wandelingen (in grafen en gerichte grafen) en bewijs stelling over existentie van Euler-wandelingen, Hamilton circuits en bewijs stelling van Dirac, lijngrafen, bomen, circuits. Klik hier voor informatie over het boek waar ik goocheltruc op het college uit heb gehaald. Extra opgaven:1.2, 1.3 en 1.13.
3. College 3. College door Sven Polak. Behandeld: kleuren, planaire grafen, De Euler-formule.
4. College 4. Behandeld: de 5-kleurbaarheid van planaire grafen, bipartiete grafen, lijnkleuringen, en het lijnkleuralgoritme voor bipartiete grafen.
5. College 5. Een voorbeeld uitgewerkt van lijnkleuren bipartiete grafen. Verder, stromen, snedes, capaciteit, max. stroom is kleiner of gelijk aan min. capaciteit snede en start met het stroom algoritme. Extra opgaven: 1.11
6. College 6. Uitleg maximumstroomalgoritme een voorbeeld uitgewerkt. Stelling `max stroom = min snede' en start met de stelling van Menger.
7. College 7. Stelling van Menger plus vragen opmerkingen over de tentamens. Tweede gedeelte lijstkleuren en 5-lijstkleurbaarheid van planaire grafen (geen examenstof!).
Tentamen: In het tentamen vraag ik om het bewijs en de formulering van een van de volgende zeven stellingen: Stelling van Dirac, Euler's karakterisatie van Euler-grafen, de Eulerformule, de 5-kleurbaarheid van planaire grafen, het lijnkleurgetal van een bipartiete graaf is gelijk aan de maximumgraad, maximum s-t stroom is begrensd door capaciteit van s-t snede en de stelling van Menger. Verder ga ik ook vragen om het maxiumstroomalgoritme of het lijnkleuralgoritme toe te passen op een concreet voorbeeld. Verder kun je nog drie andere opgaven verwachten waar je definities en stellingen uit de syllabus moet toepassen om tot de oplossing te komen.
Oude tentamens: Tentamen 2016, tentamen 2017, hertentamen 2016, hertentamen 2017, hertentamen 2015