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 utvecklas i detalj den grundläggande teorin för grafer av olika typer, särskilt träd och bipartita grafer. 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, och ett annat att bestämma ett maximalt flöde i ett nätverk. Teorin för matchningar och Halls sats behandlas, samt uppspännande träd och Mengers sats. Vidare presenteras teorin för hörn- och kantfärgningar, omfattande Brooks sats och Vizings sats. Slutligen ges en introduktion till matroidteori.
Förväntade studieresultat
För godkänd kurs ska studenten kunna
Kunskap och förståelse
definiera grundläggande begrepp inom grafteori och matroidteori
redogöra för grunderna inom kromatisk grafteori
redogöra för grundläggande egenskaper hos matchningar
redogöra för teorin för stigar och sammanhängandegrad i en graf
redogöra för grundläggande matroidteori
bevisa i kursen behandlade satser
Färdighet och förmåga
tillämpa i kursen behandlade algoritmer för att lösa grafteoretiska problemställningar
tillämpa i kursen behandlade satser för problemlösning och bevisföring
Värderingsförmåga och förhållningssätt
avgöra i vilka situationer på kursen behandlade satser kan tillämpas.
Behörighetskrav
För tillträde till kursen krävs kurser i matematik om minst 60 hp eller minst två års sammanlagda studier och i båda fallen även en kurs i diskret matematik på grundnivå omfattande minst 7,5 hp eller motsvarande. Engelska 5/A och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).
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). Betyg för hel kurs utgör en sammanfattande bedömning av resultaten vid examinationens olika delar och sätts först när alla obligatoriska moment är bedömda.
Den som godkänts i prov får ej undergå förnyat prov för högre betyg. För studerande som inte blivit godkänd vid ordinarie provtillfälle anordnas ytterligare provtillfälle. 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 prefekt för institutionen för matematik och matematisk statistik. Examination baserad på denna kursplan garanteras under två år efter studentens förstagångsregistrering på kursen.
Tillgodoräknande Student har rätt att få prövat om tidigare utbildning eller motsvarande kunskaper och färdigheter förvärvade i yrkesverksamhet kan tillgodoräknas för motsvarande utbildning vid Umeå universitet. Ansökan om tillgodoräknande skickas in till Studentcentrum/Examina. Mer information om tillgodoräknande finns på Umeå universitets studentwebb, www.student.umu.se, och i högskoleförordningen (6 kap). Ett avslag på ansökan om tillgodoräknande kan överklagas (Högskoleförordningen 12 kap) till Överklagandenämnden för högskolan. Detta gäller såväl om hela som delar av ansökan om tillgodoräknande avslås.
Övriga föreskrifter
I en examen får denna kurs ej ingå tillsammans med en annan kurs med likartat innehåll. Vid osäkerhet bör den studerande rådfråga studierektorn i matematik och matematisk statistik
Litteratur
Giltig från:
2016 vecka 46
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
