Grafentheorie en netwerk-optimalisatie vormen het hoofdthema van dit college. We bestuderen een aantal centrale onderwerpen waaronder 1. netwerk-stromen 2. bomen 3. matching 4. graaf-kleuring 5. vlakke grafen en schenken daarbij aandacht aan zowel theorie (o.a. min-max stellingen, vierkleurenstelling, Kuratowski, eigenwaardenvan grafen) als aan (combinatorische) algoritmen. Tenslotte zal er aandacht worden besteed aan connecties met (integer) lineaire programmering en semidefinite programmering. Als voorkennis is basiskennis (lineaire) algebra en bekendheid met lineaire programmering aan te bevelen.
Tentaminering
Schriftelijk tentamen en wekelijkse huiswerkopdrachten
Voorkennis
Lineaire algebra 1 en Besliskunde 1
Literatuur
“Graph Theory” van R. Diestel (zie elektronische editie online) en hand-outs
Links
Webpagina college