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.
