Hovedformålet er at præsentere grundlæggende resultater og metoder i grafteori, specielt med henblik på netværksalgoritmer og elektriske netværk. 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

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. 22. december, 2016