Inleiding grafentheorie 2017

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.

  1. College 1. Introductie: Behandeld: 1.1-1.5, 1.7, 1.8 en 1.14. Extra opgaven voor het werkcollege: 1.4 en 1.5. Voor meer informatie over het Ramsey getal zie deze wikipediapagina.
  2. College 2. Behandeld: 1.6, 1.9-1.13, en 1.15. Extra opgaven voor het werkcollege: 1.3, 1.6, 1.12. Voor meer informatie over de kaarttruc uit het college zie het boek Magical Mathematics.
  3. College 3. Behandeld 2.1-2.9 en de definitie van lijstkleuringen. Extra opgaven voor het werkcollege: 1.7-1.9.
  4. College 4. Behandeld: bewijs van 5-kleurbaarheid planaire grafen en lijnkleuren van bipartiete grafen met Delta kleuren. 2.10-2.14. Extra opgave: 1.13. Let op: de lijst met opgaven in de pdf met cursusinformatie is gewijzigd!
  5. College 5. Behandeld: Opgave 2.13a en Opgave 2.9. Verder Sectie 2.15 over schoolroosters, en Secties 3.1-3.9 over stromen en snedes. Extra opgave 1.11.
  6. College 6. Behandeld: Het maximum stroom algoritme en de max. stroom min. snede stelling. Secties 3.9-3.12. Extra opgaven: 1.10 en 1.11.
  7. College 7. Behandeld: de stelling van Menger uit Sectie 3.18 en een gedeelte van het bewijs van de 5-lijstkleurbaarheid van planaire grafen. Zie hier voor een uitwerking van het bewijs. Nb. dit is geen tentamenstof!

Tentamen: Het tentamen vindt plaats in Tentamenzaal USC Sporthal 2 Sciencepark, op vrijdag 31 maart van 9:00 uur tot 12:00 uur.

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. Nb. Secties 1.16-1.17 en 3.13-3.17 behoren niet tot de tentamenstof. Hier zijn enkele oude tentamens om je een indruk te geven: Tentamen 1 2015 Tentamen 2 2015 Tentamen 1 2016 Tentamen 2 2016