AU kursuskatalog arkiv

Grafteori 1 (Q1 + Q2) ( efterår 2011 - 10 ECTS )

Rammer for udbud

• Uddannelsessprog: dansk
• Niveau: Kandidatkursus.
• Semester/kvarter: 1. + 2. kvarter, efterår 2011.
• Timer per uge: 3 forelæsninger pr. uge i såvel 1. som 2. kvarter. Herudover er der mindst 12 øvelsestimer, der placeres som 2 gange 3 timer ultimo hvert kvarter. Der gives mulighed for yderligere øvelsestimer, hvis behov skønnes. 
• Deltagerbegrænsning:
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 34199

Formål

Kursets formål er at bibringe de studerende kendskab til grafteori i et omfang, der sætter dem i stand til at anvende grafteori som slagkraftigt modelleringsværktøj, der sine steder anvendes i praksis. Men også at bibringe dem tilstrækkeligt kendskab til området til, at de selv kan erhverve sig ny viden, og lære om grafteoretiske algoritmer.

Obligatorisk program

Kurset er baseret på bogen "Graphs: Theory and Applications" skrevet af K. Thulasiraman and M. N. S. Swamy, Wileys, 1992. Det obligatoriske stof omfatter kapitlerne 1, 2, 3, 5, 7 samt de første 3 afsnit af 8. Desuden vil der blive valgt dele af kapitlerne 4 og 6, der besluttes ud fra deltagernes ønsker. Desuden er øvelsestimerne en del af det obligatoriske program.

Indhold

Stofligt lig det obligatoriske program, der gennemgås via forelæsninger. Bogens teori suppleres med anvendelser, der hovedsagelig tager afsæt i problemstillinger inden for telekommunikation, og således inddrages lineærprogrammering som et redskab til løsning af grafteoretiske problemstillinger.
Kapitel 1 drejer sig om de basale definitioner, der knytter sig til introduktionen af grafteori. Kapitel 2 omhandler hovedsageligt egenskaber ved grafer, der kaldes som træer. Eksempler på sådanne egenskaber er kredse, cuts, cutsets. Kapitel 3 drejer sig om Euler- og Hamilton grafer, mens kapitel 5 alene drejer sig om orienterede grafer. Kapitel 7 omhandler plane grafer, mens kapitel 8 omhandler grafers robusthed (=stadig sammenhængende), hvis der fjernes et antal kanter eller knuder fra grafen. Kapitel 4 formulerer nogle aspekter af grafteori i termer fra vektorrums teori, mens kapitel 6 formulerer nogle graf-teoretiske aspekter ved hjælp af matricer med mere.

Faglige forudsætninger

Matematisk Programmering. Det er muligt at følge kurset på tredje år af bachelor-studiet i matematisk økonomi. Kurset er velegnet til studerende, som er interesserede i operationsanalyse eller for studerende som er interesseret i anvendt matematik.

Underviser

Steen Friis Møller.

Undervisnings- og arbejdsform

Bogen gennemgås via forelæsninger, der afvikles på tavle med tradition for spørgsmål fra såvel underviser til studenterne som omvendt. Øvelsestimerne afvikles via studenternes gennemgang af opgaverne på tavlen.

.

Litteratur

Bogen "Graphs: Theory and Applications" af K. Thulasiraman og M. N. S. Swamy, Wileys, 1992.

Kursushjemmeside

Kursushjemmesiden kan ses på instituttets hjemmeside http://www.imf.au.dk kort før kursets start.

Eksamensterminer

Eksamen: 2. kvarter

Udbyder

Institut for Matematiske Fag.

Særligt om dette kursus

Der lægges vægt på praktiske anvendelser af grafteori.

Læringsmål

Ved kursets afslutning forventes den studerende inden for kursets emneområde at kunne:

• Gengive centrale resultater og give stringente, detaljerede beviser for dem.
• Sammenholde centrale resultater.
• Anvende kursets grundlæggende teknikker, resultater og begreber på konkrete eksempler og opgaver.
• Anvende lineær programmering og teorien om vektorrum som nyttige midler i grafteori.

Bedømmelse

Kurset evalueres efter 7-trinsskalaen med intern censur.
Evalueringen foregår ved en mundtlig eksamen, som varer ca. 30 minutter inkl. evaluering og er uden forberedelse. Prøveformen uden forberedelse er altid blevet valgt af de studerende, når den anden mulighed har været samme, men med forberedelse.