Kursen behandlar grafteoretiska begrepp och problemställningar, samt algoritmers användning både inom den matematiska teorin för grafer och i dess tillämpningar. I kursen utvecklar man i detalj teorin för grafer, träd, nätverk, matchningar och färgningar. I kursen presenteras också vissa av de algoritmer som helt eller delvis löser ställda grafteoretiska problem. Exempel på sådana är att bestämma om en graf är plan och att bestämma en stabil matchning av maximal vikt. Vidare presenteras teorin för hörn- och kantfärgningar och en inledning till extremalsatser för grafer, t ex Turáns sats.
Förväntade studieresultat
Efter avslutad kurs ska studenten kunna
definiera grundläggande begrepp inom grafteori, såsom sammanhängandegrad, kromatiskt tal och matchningar
tillämpa grunderna inom kromatisk grafteori i form Brooks sats, Vizings sats samt egenskaperna hos bipartita grafer.
redogöra för grundläggande egenskaper hos matchningar i form av Hall och Tuttes satser
redogöra för teorin för stigar och sammanhängandegrad i en graf i form av uppspännande träd och Mengers sats.
Behörighetskrav
För tilltrdäde till kursen krävs kurser i matematik om minst 60 hp eller minst två års sammanlagda studier. Dessutom krävs kursen Introduktion till diskret matematik (5MA008) eller motsvarande kunskaper.
Undervisningens upplägg
Undervisningen bedrivs i huvudsak i form av föreläsningar och lektionsundervisning.
Examination
Kunskapsredovisningen sker i form av skriftliga prov. På de skriftliga proven samt på hel kurs ges något av betygen Underkänd (U), Godkänd (G) eller Väl godkänd (VG). Betyget utgör en sammanfattande bedömning av resultaten vid examinationens olika delar och sätts först när alla obligatoriska moment är godkända. Den som godkänts i prov får ej undergå förnyat prov för högre betyg.
En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 22 §). Begäran om ny examinator ställs till prefekten för institutionen för matematik och matematisk statistik.
Examination baserad på denna kursplan garanteras under minst två år efter studentens förstagångsregistrering på kursen.
Tillgodoräknande prövas alltid individuellt (se universitetets regelsamling och tillgodoräknandeordning).
Litteratur
Giltig från:
2009 vecka 13
West Douglas Brent Introduction to graph theory 2. ed. : Upper Saddle River, N.J. : Prentice Hall : cop. 2001 : xix, 588 s. : ISBN: 0-13-014400-2 Se Umeå UB:s söktjänst
