Introduktion till grafteori
7.5 hp, Fristående kurs, Umeå universitet
Utbildningsområde: Metoder och beslutsstöd
Typ av utbildning:
Fristående kurs
Nivå:
Grund
Studieform:
Campus
Studietakt:
50%
Utbildningsort:
Umeå
Undervisningstid:
Dag
Omfattning:
7.5 hp
Undervisningsspråk:
Engelska
Kursen startar:
2027-03-25
Sista dag för anmälan:
2026-10-15
Uppgifter om utbildningen hämtas från SUSA-navet som motsvarar innehållet på antagning.se Länk till annan webbplats, öppnas i nytt fönster..
Mer om utbildningen
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.
Mer om kursen
Startperiod
VT-27
Startvecka
Vecka 12 2027
Slutvecka
Vecka 22 2027
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 och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).
Anmälningskod
5800M
Kurskod
5MA146
Lärosäte som anordnar kursen
Umeå universitet erbjuder ett brett utbildningsutbud med särskild fokus på medicin och hälsa, teknik och naturvetenskap, humaniora och samhällsvetenskap, ekonomi och företagande, konst och design, utbildning och lärande samt hållbar utveckling och miljö och erbjuder flera utbildningar och forskningsprojekt som fokuserar på hållbarhet och klimatförändringar.
