Grafteori, forskarutbildningskurs HT 1999

Kursbeskrivning

Grafer används ofta både inom och utom matematiken som ett praktiskt sätt att åskådliggöra olika relationer. Många sådana tillämpningar är mycket ytliga, vilket kan ge intryck av att grafteori är ett magert och ganska substanslöst område. Jag vill med denna kurs visa att detta är fel, och att det finns en rik teori med många intressanta (och ibland överraskande) problem och resultat.

Jag kommer att följa valda delar av Bollobás, Modern Graph Theory (Springer 1998), som behandlar både "ren" grafteori och mer tillämpade områden. Ur innehållet:

Plana grafer. Fyrfärgssatsen (utan bevis).
Hamiltonska och Eulerska grafer. Broarna i Köningsberg.
Elektriska nätverk. Kirchoffs lagar.
Slumpvandringar på grafer.
Tuttepolynomet.
Knopar och knoppolynom.
Slumpgrafer.

Kurslitteratur

B. Bollobás, Modern Graph Theory, Springer 1998.

Schema

Föreläsningar måndagar 10.15-12.00 och onsdagar 13.15-15.00 i sal 2215.
Kursstart 6 september.
Sista föreläsning onsdagen den 8 december.

Obligatoriska Inlämningsuppgifter

Chapter 1: 1 valfri övningsuppgift ur boken
Chapter 2: 1 valfri övningsuppgift ur boken
Chapter 3: 2 valfria övningsuppgifter ur boken
Chapter 4: 2 valfria övningsuppgifter ur boken
Chapter 5: 1 valfri övningsuppgift ur boken
Chapter 6: 1 valfri övningsuppgift ur boken
Chapter 7: 1 valfri övningsuppgift ur boken
Chapter 8: 1 valfri övningsuppgift ur boken
Chapter 9: 1 valfri övningsuppgift ur boken
Chapter 10: 1 valfri övningsuppgift ur boken

Tentamen

Hemskrivning (utvidgad inlämningsuppgift) delas ut vid föreläsningen 8 december, och finns även tillgänglig på denna sida efter föreläsningen. Skall lämnas in senast 15 december.

Onsdagen 8/12 1999 dvi postskript

Svante Janson svante.janson@math.uu.se
Senast ändrad: