Introduktion till grafteori 7,5 hp

Om kursen

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.