NWI-WB060B
Inleiding Grafentheorie
Cursus informatieRooster
CursusNWI-WB060B
Studiepunten (ECTS)3
CategorieBA (Bachelor)
VoertaalNederlands
Aangeboden doorRadboud Universiteit; Faculteit der Natuurwetenschappen, Wiskunde en Informatica; Wiskunde, Natuur- en Sterrenkunde;
Docenten
Coördinator
dr. W. Bosma
Overige cursussen docent
Examinator
dr. W. Bosma
Overige cursussen docent
Contactpersoon van de cursus
dr. W. Bosma
Overige cursussen docent
Docent
dr. W. Bosma
Overige cursussen docent
Docent
drs. M. Campschroer
Overige cursussen docent
Collegejaar2021
Periode
KW1  (06-09-2021 t/m 07-11-2021)
Aanvangsblok
KW1
Onderwijsvorm
voltijd
Opmerking-
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Plaatsingsprocedure-
Cursusdoelen
  • De student kent de elementaire begrippen uit de grafentheorie en kan deze hanteren
  • 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.
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.

Instructional Modes
Niveau

Voorkennis

Toetsinformatie
Schriftelijk tentamen
Bijzonderheden

Verplicht materiaal
Dictaat
Dictaat van Prof. Lex Schrijver, met enige aanvullingen

Werkvormen
Cursusgebeurtenis

Hoorcollege

Werkcollege

Toetsen
Tentamen
Weging1
ToetsvormTentamen
GelegenhedenBlok KW1, Blok KW2