Grafteori
Forår 2012
Lærer: Leif Kjær Jørgensen

Litteratur: Reinhard Diestel, Graph Theory, 4. udgave.

Skema.

Projekt/kursus-eksamen, den 28. juni:
Efter projektpræsentation: ½ time for hver eksaminant, uden forberedelse.
Der trækkes et af nedenstående eksamensspørgssmål fra kurset.
Efter gennemgang af spørgsmålet diskuteres projektet.

Eksamensspørgsmål:
Pensum: alt som er gennemgået ifølge nedenstående oversigt:

Oversigt over de enkelte kursusgange:

15. gang, onsdag den 9. maj. Start 8.45.
Afsnit 8.1: Kun side 209 og 211: Königs lemma 8.1.2, Sætning 8.1.3 med første bevis, unfriendly partition conjecture.

14. gang, onsdag den 2. maj.
Afsnit 7.5, Anvendelse af Szemerédis regularitets lemma.
Opgaver i kap. 7:

13. gang, onsdag den 11. april.
Afsnit 7.4, Szemerédis regularitets lemma.
Opgave: Sæt epsilon=¼.  Beregn den værdi af M der kan benyttes i Lemma 7.4.1 ifølge beviset.
Opgaver i kap. 7: 35, 36

12. gang, onsdag den 4. april.
Resten af afsnit 10.2.
Afsnit 7.3.
Måske en introduktion til 7.4.
Opgaver i kap. 7:   25, 26, 28, 29, 31, 32

11. gang, onsdag deen 28. marts. Start 8.45
Resten af afsnit 10.2.
Afsnit 10.3.

10. gang, onsdag den 21. marts.
Afsnit 10.1 og 10.2: Hamilton kreds.
På bogens hjemmeside: http://www.diestel-graph-theory.com/  er der en trykfejlsliste, bl.a. med følgende rettelse til Sætning 10.1.3: N({u,v,w}) skal ændres til N(u) \cup N(v) \cup N(w).
Ekstraopgave: find et modeksempel til Sætning 10.1.3, som den formuleret i bogen.
Opgaver i kap. 10: 1, 3, 7, 8, 5, 6.

9. gang, onsdag den 14. marts. Start 8.45
Afsnit 7.2: Carsten Thomassens sætning.
Afsnit 9.1, især Ramseys sætning (9.1.1), kun side 270-271.
Afsnit 11.1: kun sætning 11.1.3.
Opgave i kap. 9: 1
Opgaver i Rosen, Discrete mathematics and its application, afsnit 5.2 (lån eventuelt lærerens bog): 24, 25 (også med 9 i stedet for 10), 26 (med 18 i stedet for 20), 27, 28.

8. gang, mandag den 12. marts, eftermiddag.
Afsnit 7.1.
Afsnit 7.2.
Opgaver i kap. 7: 1, 3, 4, 23.

7. gang, torsdag den 8. marts, eftermiddag.
Afsnit 4.4: Kuratowskis sætning.
Opgaver i kap. 4:  22, 20, 15, 17, 18

6. gang, onsdag den 7. marts.
Afsnit 4.1 og 4.2 om planare grafer. Vi går måske lidt mindre i detaljer med de topologiske begreber end han gør i bogen.
Opgave til kap. 3 og 4: Tegn en 5-regulær planar graf G, hvor to regioner er afgrænset af kreds af længde 4 og alle andre regioner er afgrænset af trekanter. Hvor mange punkter skal en sådan graf have.
                                     (G er også 5-sammenhængende.) Find punkter s1 , s2 , t1 , t2 i G så G ikke har to disjunkte veje fra s1 til t1 og fra s2 til t2. Altså G ikke 2-lænket.
Opgaver i kap. 4: 2, 5, 6, 7, 1.

5. gang, onsdag den 29. februar. Start 8.45
Afsnit 3.3 (mindst ét bevis for Mengers sætning).
Afsnit 3.5 kun til øverst side 76.
Opgave til kap. 3: Find ved hjælp af sætning 3.2.3 alle kubiske, 3-sammenhængende grafer med 6 eller 8 punkter.
Opgaver i kap. 3: 25, 19, 18, 17

4. gang, onsdag den 22. februar
Afsnit 3.1 (2-sammenhængende grafer)
Afsnit 3.2 (3-sammenhængende grafer), dog ikke Theorem 3.2.6.
Måske når vi også første bevis for Mengers sætning i afsnit 3.3.
Opgaver i kap. 2: 20
Opgave til kap.3: Definer en relation ~ på E(G) ved e~f hvis e=f eller e og f ligger på en fælles kreds. Vis at ~ er en ækvivalensrelation. Vis at ækvivalensklasserne er grafens blokke.
Opgaver i kap. 3: 6, 7, 8

3. gang, onsdag den 15. februar
Afsnit 2.1 undtagen side 40.
Afsnit 2.2.
Om parringer (matchings) in hhv. todelte og generelle grafer.
Opgaver i kap. 2: 1, 3, 5, 16, 19.

2. gang, onsdag den 8. februar, formiddag.
Afsnit 1.5 (træer), 1.6 (todelte grafer), 1.7 (minors), 1.8 (Euler tur).
Opgaver i kap. 1: 15, 17, 19, 22, 26, 28, 29.

1. gang, torsdag den 2. februar, eftermiddag.
Introduktion.
Afsnit 1.1 (graphs), 1.2 (degree), 1.3 (paths and cycles), 1.4 (connectivity), 1.10 (other notions of graphs) i Diestels bog.
Opgaver: 1, 2, 4, 5, 10, 11, 14  (opgavenumre fra 3. udgave, i 2. udgave har opgaverne numre 1,2,4,5,8,9,13)