Grafteori


Lærer:   Leif Kjær Jørgensen  

Litteratur: 

Graph Theory, Reinhard Diestel. 3rd edition, 2005. Springer Verlag.
En elektronisk udgave af bogen findes på forfatterens hjemmeside.
Bemærk at hvis man vælger den tyske udgave af bogen kan numereringen af kapitler afvige fra den engelske udgave.

Eksamensspørgsmål:

  1. Parring i grafer
  2. Sammenhæng
  3. Planare grafer
  4. Farvning
  5. Ekstremal grafteori
  6. Ramsey teori
  7. Hamiltonkredse
  8. Ordningsrelationer: Dilworths sætning eller vel-kvasi ordning.

Eksamenspensum: De gennemgåede afsnit af Diestels bog.

Spørgetime: Torsdag den 3. juni, kl. 9.00 i G5-109. 

Oversigter over de enkelte kursusgange:


1. kursusgang, tirsdag den 2. februar.
Vi mødes i G5-109 kl. 8.15.
Introduktion til kurset.
Jeg gennemgår afsnit 1.1, 1.2, 1.3 og 1.4 i Diestels bog.


2. kursusgang, tirsdag den 9. februar.
Afsnit 1.5, 1.6, 1.7, 1.8.

3. kursusgang, tirsdag den 16. februar.
Afsnit 2.1 og 2.2. Om parringer.
Opgaver i kap. 2: 3, 14, 15

4. kursusgang, tirsdag den 23. februar.
Maria og Majken vil fortælle om:
Afsnit 3.3: Kun Mengers sætning (sætning 3.3.1) med ét af beviserne. (De vælger nok det nemmeste (first proof).)
Desuden (noget af) afsnit 3.1 og 3.2 (dog ikke sætning 3.2.3, som ikke er pensum).

5. kursusgang, tirsdag den 2. marts.
Jeg gennemgår:
Afsnit 3.3, Korollar 3.3.5, Sætning 3.3.6.
Afsnit 3.5 til midt på side 71.
Måske lidt mere fra afsnit 2.1 og 2.2.

6. kursusgang, tirsdag den 9. marts.
Janne og Sally gennemgår
Afsnit (4.1 og) 4.2.

7. kursusgang, tirsdag den 16. marts.
Henning og Sanne gennemgår Afsnit 4.4.

8. kursusgang, torsdag den 18. marts.
Tina og Charlotte gennemgår
Afsnit 5.1
Afsnit 5.2 til side 117, midt.

9. kursusgang, tirsdag den 30. marts.
Anders og Rune gennemgår
Afsnit 5.2 fra side 117
Afsnit 5.3.

10. kursusgang, tirsdag den 6. april.
Afsnit 7.1 og 7.2

11. kursusgang, tirsdag den 13. april.
Måske lidt mere om afsnit 7.2. Desuden afsnit 7.3, sætning 9.1.1 og sætning 11.1.3.

12. kursusgang, tirsdag den 20. april.
Ronni gennemgår afsnit 10.1 og
jeg gennemgår afsnit 10.2.

13. kursusgang, tirsdag den 27. april.
Afsnit 8.1: Kun
Afsnit 9.1: Vi har tidligere set på Sætning 9.1.1. Dennne gang: resten af afsnittet.
Introduktion til afsnit 12.1.

14. kursusgang, tirsdag den 4. maj.
Afsnit 12.1 og 12.2.

15. kursusgang, tirsdag den 11. maj.
Afsnit 2.5 og 12.2.