Kursen behandlar grafteoretiska begrepp och problemställningar, både teoretiskt 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ö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).
Urval
Platsgaranti
Studieavgift
Gäller endast medborgare utanför EU, ESS och Schweiz.
Anmälningsavgift: 900 kr.
Studieavgift, första inbetalningen: 17 850 kr.
Total studieavgift: 17 850 kr.
Anmälnings- och studieavgifter
Anmälningskod
UMU-58119
Anmälan
Sista anmälningsdag var den
15 oktober 2024.
Du kan inte längre anmäla dig.
