|
01227 Grafteori |
| Engelsk titel: Graph Theory |
|
Sprog: Engelsk Point: 5, Ekstern censur.
|
|
| Type: civilkursus, udbydes under åben uddannelse |
|
Eksamensplacering: |
E1-B (Dec 11 2001), F1-B (May 28 2002)
|
|
Vejledende placering: Midt i studiet. |
|
Undervisningsform: Forelæsninger, grupperegning, fælles opgavegennemgang, afleveringsopgaver. |
|
Evalueringsform: Skriftlig eksamen
|
| Karakter: 13-skala |
| Tidligere kursus: C0127 |
| Faglige forudsætninger: 01010 / 01011 eller 01000 / 01001, 01012 / 01013 / 01014, eller 01005 / 01015 / 01016 |
| Pointspærring: C0127 |
| Kursusmål: Hovedformålet er at præsentere grundlæggende resultater og metoder i grafteori, specielt med henblik på netværksalgoritmer og elektriske netværk. |
| 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. |
| Kontaktperson: Carsten Thomassen, building 303, (+45) 4525 3058, c.thomassen@mat.dtu.dk |
| Kursus URL: http://www.mat.dtu.dk/courses/01227 |
|
|
