MM856: Grafteori

Indgangskrav

MM856 samlæses med MM855, og man kan derfor kun tilmelde sig et af disse kurser.

Faglige forudsætninger

Studerende, der følger kurset, forventes at have basal kendskab til grafteori og diskret matematik svarende til stofffet i MM541 (Kombinatorisk Matematik).

Formål

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.

Målbeskrivelse

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.
forklare sammenhænge mellem begreber og resultater i grafteori
benytte grafteori algoritmer til at løse komplekse problemer.

Indhold

Kurset indeholder følgende faglige hovedområder: Grafer, træer, afstande, pardannelser i generelle grafer, veje, kredse, farvning i grafer, Hamilton kredse, planar grafer, random grafer, NP-hårdhed og digrafer.

Litteratur

Se itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Efterår og januar

Udprøvninger

Portfolio og tests

EKA

N310057102

Censur

Intern prøve, to eller flere bedømmere

Bedømmelse

7-trinsskala

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Varighed

3 timer

Hjælpemidler

Alle almindelige hjælpemidler er tilladte fx lærebøger, egne noter, computerprogrammer som ikke benytter internettet m.v.

Internet er ikke tilladt. Du må dog gå ind på kursets hjemmeside i itslearning i forbindelse med åbning af system "DE – Digital Eksamen". Noter fra kurset, som du ønsker at anvende som hjælpemidler, skal downloades til din computer senest dagen før eksamenen. Under eksamenen er det ikke sikkert at alt kursusmateriale er tilgængeligt for dig.

ECTS-point

Uddybende information

Portfolio eksamen bestående af: to dele:

Obligatoriske opgaver - vægter 20 %
Skriftlig eksamen (januar) - vægter 80 %

Eksamensformen ved reeksamen vil være ren skriftlig stedprøve.

Vejledende antal undervisningstimer

90 timer per semester

Undervisningsform

Skemalagte undervisningstimer:

Antal undervisningstimer i alt: 90

Heraf:

Fællestimer i klasselokale/auditorium: 90

Disse timer består af forelæsninger og opgave regning.

Andre planlagte undervisningsaktiviteter:

Studere kursusmaterialet og forberede de ugentlige øvelser, individuelt eller gennem gruppearbejde.

Ansvarlig underviser

Navn	E-mail	Institut
Anders Yeo	yeo@imada.sdu.dk	Algoritmer

Skemaoplysninger

Odense

Vis fuldt skema

Administrationsenhed

Institut for Matematik og Datalogi (matematik)

Team hos Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil	Uddannelse	Semester	Udbuds periode

Overgangsordninger

Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.

Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.