Zoek
English
  Studiegidsen 2011-2012
Radboud UniversiteitStudiegidsenFaculteit der Natuurwetenschappen, Wiskunde en Informatica > Bachelor Wiskunde

Inleiding Grafentheorie 

Vakcode
NWI-WB060B
Studiepunten
3
Periode
eerste kwartaal
Werkvormen
  • 16 uur hoorcollege
  • 16 uur werkcollege
Leerdoelen
  • De student kent de elementaire begrippen uit de grafentheorie
  • De student weet iets van de geschiedenis van het vak (Euler, vierkleurenprobleem).
  • De student kan bepalen of een eindige graaf planair is of niet, kan eenvoudige roosterings- en routeringsproblemen omzetten in een grafenprobleem, en dat vervolgens oplossen.
  • De student kan het algoritme voor het bepalen van de maximale stroom in een netwerk toepassen.
Beschrijving

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.

Tentaminering
Schriftelijk tentamen
Literatuur
dictaat van Prof. Lex Schrijver