Enkeltfag 5 ECTS

Grafteori

Overordnede kursusmål

Hovedformålet er at præsentere grundlæggende resultater og metoder i grafteori, specielt med henblik på netværksalgoritmer.

See course description in English

Læringsmål

  • 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.

Anbefalede forudsætninger

01001/01003/01005/01017/01019, Matematisk modenhed.

Undervisningsform

Forelæsninger, grupperegning, fælles opgavegennemgang, afleveringsopgaver.

Fakultet

Se kurset i kursusbasen

Tilmelding

Sprog
Varighed

13 uger

Institut

Compute

Sted

DTU Lyngby Campus

Kursus ID 01227
Kursustype Bachelor
Semesterstart Uge 5
Semester slut Uge 19
Dage tors 13-17
Pris

7.500,00 kr.

Tilmelding