Hovedformålet er at præsentere grundlæggende resultater og metoder
i grafteori, specielt med henblik på netværksalgoritmer og
elektriske netværk.
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
finde afstande, antal korteste veje, minimale udspændende
træer, og minimale vandringer, der gennemløber alle kanter
finde maksimale strømninger, minimale snit samt kritiske og
optimale kanter
finde største parringer og mindste punktdække i 2-delte grafer,
og finde minimale jobtildelinger, samt lægge optimale skemaer
beregne Pauling bånd i benzoider
anvende strømrum og spændingsrum samt Kirchhoff's
træsætning til at bestemme strømme, spændinger og
indgangsresistanser i elektriske netværk
udregne sandsynligheder i forbindelse med tilfældige vandringer
(Markov kæder)
anvende Euler's formula i forbindelse med plane
grafer
Kursusindhold:
Grundlæggende grafteori, herunder Euler grafer, Menger's
sætning om grafsammenhæng, planaritet, parringsteori med anvendelse
til strukturrang, skemalægning, og Pauling bånd i benzoider.
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. Plane grafer.
