01227 Grafteori

2024/2025

Kursusinformation
Graph Theory
Engelsk
5
Bachelor
Kurset udbydes som enkeltfag
Tilvalgskurser, IT og Økonomi
Tilvalgskursus (B Eng), IT-elektronik
F1B (tors 13-17)
Campus Lyngby
Forelæsninger, grupperegning, fælles opgavegennemgang, afleveringsopgaver.
13-uger
F1B
Skriftlig eksamen
Skriftlig eksamen: 4 timer
Skriftlige hjælpemidler er tilladt
7-trins skala , ekstern censur
(01001/01003/01005).­(01017/01019) , Matematisk modenhed.
David Earl Roberson , Lyngby Campus, Bygning 322 , dero@dtu.dk
Carsten Thomassen , Lyngby Campus, Bygning 322, Tlf. (+45) 4525 3058 , ctho@dtu.dk
01 Institut for Matematik og Computer Science
I studieplanlæggeren
Overordnede kursusmål
Hovedformålet er at præsentere grundlæggende resultater og metoder i grafteori, specielt med henblik på netværksalgoritmer.
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
  • 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.
Sidst opdateret
02. maj, 2024