MM810: Grafteori I

13004201(tidligere UVA) er identisk med denne kursusbeskrivelse.

Kursuset udbydes efter behov. Kandidatkursus forhåndsgodkendt som PhD-kursus.

Kurset har til formål at sætte den studerende i stand til at gengive
definitioner og resultater fra grafteori inden for kursets pensum,
hvilket er vigtigt i forhold til identificere matematiske strukturer fra
grafteori i konkrete eksempler.

Kurset bygger oven på den viden, der
er erhvervet i kurserne MM510 og MM515, og giver et fagligt grundlag for
at studere videregående emner med henblik på et speciale i diskret
matematik.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

• Give
  kompetencer til at planlægge og udføre videnskabelige projekter på højt
  fagligt niveau herunder styre arbejds- og udviklingssituationer, der er
  komplekse, uforudsigelige og forudsætter nye løsningsmodeller
• Give
  færdigheder til at sætte sig ind i, analysere, modellere og løse givne
  problemstillinger på et højt abstraktionsniveau ud fra logiske og
  strukturerede ræsonnementer
• Give viden om avancerede modeller og metoder i grafteori

For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:

• gengive definitioner og resultater fra grafteori inden for kursets pensum
• anvende teorien til at løse konkrete opgaver med udgangspunkt i kursets pensum
• argumentere for skridtene i opgaveløsningen
• gennemføre
  stringente og fuldstændige beviser for påstande med udgangspunkt i
  kursets pensum (tælleargumenter, induktion, indirekte beviser,
  algoritmiske beviser)
• forklare sammenhænge mellem begreber og resultater i grafteori
• benytte matematisk terminologi og symboler fra mængdelære, funktionsteori og logik
• identificere matematiske strukturer inden for kursets pensum i konkrete eksempler

Kurset indeholder følgende faglige hovedområder: Grafer, delgrafer, sammenhængende grafer, trær, ikke separable grafer, træ-søge-algoritmer, kompleksitet af algoritmer, sammenhæng, uafhængige mængder og kliker, pardannelse, Hamilton kredse.

Se BlackBoard for pensumlister og yderligere litteraturhenvisninger.

På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
For at sætte de studerende i stand til at nå læringsmålene for kurset tilrettelægges undervisningen således, at der er 42 forelæsningstimer, holdtimer etc. på et semester.

Disse undervisningsaktiviteter udmønter sig i en anslået vejledende fordeling af arbejdsindsatsen hos en gennemsnitsstuderende på følgende måde:

• Introfase (forelæsning, holdtimer) - Antal timer: 22
  
• Træningsfase: Antal timer: 20
  
• Total: Antal timer: 42
  

Aktiviteter i studiefasen: At studere kursusmaterialet og forberede de ugentlige øvelser, individuelt eller gennem gruppearbejde.