Matematiska institutionen

Kursplan för Grafteori

Graph Theory

Kursplan

  • 5 högskolepoäng
  • Kurskod: 1MA170
  • Utbildningsnivå: Grundnivå
  • Huvudområd(en) och successiv fördjupning: Matematik G1F
  • Betygsskala: Underkänd (U), 3, 4, 5.
  • Inrättad: 2010-03-18
  • Inrättad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Reviderad: 2013-03-04
  • Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 30, 2013
  • Behörighet: 35 hp matematik inklusive Linjär algebra II och Sannolikhet och statistik eller Sannolikhetsteori I.
  • Ansvarig institution: Matematiska institutionen

Mål

För godkänt betyg på kursen skall studenten kunna

  • redogöra för viktiga klasser av grafteoretiska problem;
  • formulera och bevisa centrala satser om träd, matchningar, konnektivitet, färgläggningar och planära grafer;
  • beskriva och tillämpa några grundläggande algoritmer för grafer;
  • använda grafteorin som verktyg vid modellering.

Innehåll

Grundläggande grafteoretiska begrepp: vägar och cykler, konnektivitet, träd, uppspännande delgrafer, bipartita grafer, Hamilton- och Eulercykler. Algoritmer för kortaste väg och uppspännande träd. Matchning. Planära grafer. Färgläggning. Flöden i nätverk, maxflöde-minsnittsatsen. Slumpgrafer. Strukturegenskaper hos stora grafer: graddistribution, klustringskoefficient, preferential attachment, karakteristiska väglängder och små nätverk. Tillämpningar inom biologi, informationsteknologi och samhällsvetenskap.

Undervisning

Föreläsningar, lektioner och räkneövningar.

Examination

Skriftligt prov vid kursens slut kombinerat med inlämningsuppgifter under kursen enligt anvisningar som lämnas vid kursens start.

Litteratur

Gäller från: vecka 31, 2016

  • Föreläsarens material och anteckningar

    Matematiska institutionen,

    Obligatorisk