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
- redogöra för teori för matchningar och färgningar
- formulera och använda algoritmer för att hitta matchningar i bipartita och allmänna grafer
- 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, tillämpa och bevisa centrala satser ur kursen
Behörighetskrav
Univ: För tillträde till kursen krävs kursen Grafteori (5MA076), Linjär algebra (5MA019) samt en grundläggande kurs i matematisk statistik om minst 6 hp eller motsvarande kunskaper.
Engelska 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. Dessa kan kombineras med andra examinationsformer, exempelvis skriftliga inlämningsuppgifter. På en skriftlig tentamen ges något av betygen Underkänd (U), Godkänd (G) eller Väl godkänd (VG). Vid övriga former av examination ges något av betygen Underkänd (U) eller Godkänd (G). För att bli godkänd på hela kursen krävs att samtliga prov och obligatoriska moment är godkända. På hela kursen 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 erhållit betyget godkänt på kursen kan därefter ej examineras 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 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).
Ö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
Litteraturlistan är inte tillgänglig via den webbaserade utbildningskatalogen.
Kontakta aktuell institution.
