MM810: Grafteori I (5 ECTS)

STADS: 13004201

Niveau
Kandidatkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.
Udbydes efter behov

Ansvarlige undervisere
Email: stephan.brandt@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. 3. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra MM505, Lineær Algebra, skal være kendt, og stoffet fra MM510, Ringe og Talteori, og MM512, Grupper og Vektorrum, er en fordel.

Kursusintroduktion
At introducere grundlæggende emner og ræsonnementer fra grafteori, herunder algoritmiske aspekter.

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:
• 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

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

Litteratur

Meddeles ved kursets start.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Mundtlig eksamen der bedømmes med karakter efter 7-trinsskalen og ekstern censur.

Reeksamen ifølge reglerne vedtaget i studienævnet.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger:21 timer
Eksaminatotietimer/opgaveregning: 7 timer
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på engelsk, hvis der deltager internationale studerende, ellers undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2009 til 31. august 2016.