Kursen ger en introduktion till avancerade tekniker för studier av graffärgning, faktorer i grafer och teorin för cykler i grafer. Inom graffärgning diskuteras grafpolynomet och hur dess koefficienter är kopplade till graffärgningar och orienteringar av grafer. Som tillämpning på grafpolynomet diskuteras latinska kvadrater. Existens av olika typer av riktade cykler och deras koppling till andra strukturer tas upp. I teorin för cykler studeras olika villkor som säger när en matchning ingår i en Hamiltoncykel eller Hamiltonstig.
Förväntade studieresultat
För godkänd kurs ska studenten kunna:
• definiera grafpolynomet och redogöra för kopplingen till färgningar och orienteringar av grafer. • formulera och bevisa Hajos sats om strukturen hos q-kromatiska grafer • redogöra för kopplingar mellan Tuttes sats, Ford-Fulkersons sats och faktorer i grafer • formulera och bevisa villkor för existensen av långa cykler i grafer • formulera och använda algoritmer för att räkna eulerslingor i grafer • formulera och använda hopplemmat för att visa existensen av långa cykler • formulera, tillämpa och bevisa centrala satser som ingår i kursen
Behörighetskrav
För tillträde till kursen krävs kursen Grafteori (5MA135) eller motsvarande kunskaper. En 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 inlämningsuppgifter och seminarier. På inlämningsuppgifter ges något av betygen Underkänd (U), Godkänd (G) eller Väl godkänd (VG). Vid seminarier 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 Tillgodoräknande prövas alltid individuellt (se universitetets regelsamling och tillgodoräknandeordning).
Litteratur
Litteraturlistan är inte tillgänglig via den webbaserade utbildningskatalogen.
Kontakta aktuell institution.
