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

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. 27. april, 2022