01227 Grafteori
2024/2025
Overordnede kursusmål
Hovedformålet er at præsentere grundlæggende resultater og metoder
i grafteori, specielt med henblik på netværksalgoritmer.
Læringsmål
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
- kombinere grundlæggende grafteoretiske begreber og resultater
til besvarelse af strukturspørgsmål vedrørende grafer
- konstruere simple beviser for grafteoretiske udsagn
- genkende forskellige grafklasser, så som træer, todelte grafer,
komplette grafer og plane grafer.
- modellere et givet problem som et grafproblem
- anvende grafalgoritmer til at løse et givet problem, feks.
korteste veje, maksimum flow, maksimale parringer, minimale
dækninger, antal af udspændende træer, effektiv modstand, mm.
- modificere kendte grafalgoritmer til at løse et givet
problem.
- argumentere for korrekthed af grafalgoritmer
- analysere kompleksiteten af grafalgoritmer
Kursusindhold
Grundlæggende grafteori, herunder Euler grafer, Menger's
sætning om grafsammenhæng, planaritet, parringsteori med anvendelse
til strukturrang, skemalægning. Netværksstrømninger, som udgør
grundlaget for kombinatorisk optimering med anvendelse i f.eks.
operationsanalyse. Beskrivelse og kompleksitet af algoritmer
(korteste veje, mindste udspændende træer, det kinesiske postbuds
problem, største parringer, jobtildelingsproblemet) af interesse i
datalogi. Det matematiske grundlag for elektriske netværk, herunder
effektive modstande udtrykt ved hjælp af udspændende træer og
determinanter. Tilfældige vandringer.
Sidst opdateret
02. maj, 2024