Introduktion till grafteori, 7,5 hp

Innehåll

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