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å ett sådant är att bestämma en matchning av maximal vikt. Vidare presenteras teorin för hörn- och kantfärgningar och en inledning ges till extremalsatser för grafer, t ex Turáns sats. Slutligen ges en introduktion till matroidteori.
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 av Brooks sats, Vizings sats samt egenskaperna hos bipartita grafer.
redogöra för grundläggande egenskaper hos matchningar i form av Halls sats
redogöra för teorin för stigar och sammanhängandegrad i en graf i form av uppspännande träd och Mengers sats
redogöra för den grundläggande teorin kring matroider.
Behörighetskrav
För tillträde till kursen krävs kurser i matematik om minst 60 hp eller minst två års sammanlagda studier innefattande 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:
2013 vecka 3
Wilson Robin J. Introduction to graph theory 5th ed. : Harlow : Prentice Hall : 2010. : viii, 184 s. : ISBN: 978-0-273-72889-4 (pbk.) Obligatorisk Se Umeå UB:s söktjänst
