Grafteori, 7,5 hp

Innehåll

Kursen ger en fördjupning inom teorin för matchningar i och färgning av grafer, samt en introduktion till ett antal områden inom mer avancerad grafteori. Inom matchningsteori behandlas mini-maxsatser, stabila matchningar i bipartita grafer och Tuttes sats om matchningar i allmänna grafer, samt blom-algoritmen för att snabbt hitta perfekta matchningar i allmänna grafer. Inom graffärgningsteori studeras strukturen hos grafer med visst kromatiskt tal, samt speciella klasser av grafer där färgningsproblem kan lösas effektivt. Vidare omfattar kursen introduktioner till Ramseyteori, slumpgrafer och egenvärden till grafer.

Förväntade studieresultat

För godkänd kurs skall den studerande kunna:

Kunskap och förståelse

• utförligt redogöra för teori för matchningar och färgningar
• definiera centrala familjer av grafer och redogöra för deras egenskaper och inbördes förhållanden
• definiera Erdös-Renyis slumpgrafmodeller och härleda grundläggande resultat om deras egenskaper
• definiera egenvärden för grafer och bevisa deras koppling till expansion i grafer
• formulera och bevisa centrala satser ur kursen

Färdighet och förmåga

• tillämpa algoritmer för att hitta matchningar i bipartita och allmänna grafer
• tillämpa satser för problemlösning

Värderingsförmåga och förhållningssätt

Behörighetskrav

För tillträde till kursen krävs 90 hp avklarade kurser inkluderande en kurs i grafteori på grundnivå om minst 7,5 hp 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. För kursen som helhet sätts något av betygen Underkänd (U), Godkänd (G), eller Väl Godkänd (VG).  För godkänt betyg på kursen krävs godkänt på alla delar av examinationen.

Avsteg från kursplanens examinationsform kan göras för en student som har beslut om pedagogiskt stöd på grund av funktionsnedsättning. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Efter begäran av studenten ska kursansvarig lärare, i samråd med examinator, skyndsamt besluta om anpassad examinationsform. Beslutet ska sedan meddelas studenten.

Den som erhållit godkänt betyg på kursen kan ej examineras för högre betyg. För studerande som inte blivit godkända 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 prefekten 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 studierektor i matematik och matematisk statistik.