Kursplan för Grafteori

Graph Theory

Det finns en senare version av kursplanen.

Kursplan

  • 5 högskolepoäng
  • Kurskod: 1MA170
  • Utbildningsnivå: Grundnivå
  • Huvudområde(n) och successiv fördjupning: Matematik G1F

    Förklaring av koder

    Koden visar kursens utbildningsnivå och fördjupning i förhållande till andra kurser inom huvudområdet och examensfordringarna för generella examina:

    Grundnivå
    G1N: har endast gymnasiala förkunskapskrav
    G1F: har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav
    G1E: innehåller särskilt utformat examensarbete för högskoleexamen
    G2F: har minst 60 hp kurs/er på grundnivå som förkunskapskrav
    G2E: har minst 60 hp kurs/er på grundnivå som förkunskapskrav, innehåller examensarbete för kandidatexamen
    GXX: kursens fördjupning kan inte klassificeras.

    Avancerad nivå
    A1N: har endast kurs/er på grundnivå som förkunskapskrav
    A1F: har kurs/er på avancerad nivå som förkunskapskrav
    A1E: innehåller examensarbete för magisterexamen
    A2E: innehåller examensarbete för masterexamen
    AXX: kursens fördjupning kan inte klassificeras.

  • Betygsskala: Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
  • Inrättad: 2010-03-18
  • Inrättad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 35, 2010
  • Behörighet: Matematik 35 hp med Linjär algebra II och Sannolikhet och statistik
  • 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 eventuellt kombinerat med inlämningsuppgifter under kursen enligt anvisningar som lämnas vid kursens start.

Versioner av kursplanen

Litteratur

Litteraturlista

Gäller från: vecka 36, 2010

I bibliotekets söktjänst kan du se om en titel finns elektroniskt.

  • Grimaldi, Ralph P. Discrete and combinatorial mathematics : an applied introduction

    5. ed.: Boston, Mass.: Addison-Wesley, 2004

    Se bibliotekets söktjänst

    Obligatorisk

Versioner av litteraturlistan

Skriv ut kursplan och litteraturlista
Skriv ut