Inhaltsverzeichnis

Graphentheorie

Wintersemester 2003/04
Stefan Felsner

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 ,

1. Vorlesung, Mi. 22.10.2003 

Einleitung
   Was ist ein Graph? 
      Wesentliche Definitioner
   Das 4-Farben Problem
      Färbungsprobleme
      Färbungen im Netz
2. Vorlesung, Fr. 24.10.2003 
   Graphen und Geometrie
      Geometrische Graphen 
          ohne disjunkte Kanten
      Topologische Graphen ohne disjunkte Kanten
	  Thrackles
Färbungen
   2-Färbbarkeit
3. Vorlesung, Mi. 29.10.2003 
   Färbungskritische Graphen
   Einfache untere Schranken für χ
   Greedy Färbungen
      Registerzuweisung und Intervallgraphen
4. Vorlesung, Fr. 31.10.2003 
      Färbung von Intervallgraphen
   Satz vom Brooks
   ω umd χ in Zufallsgraphen
5. Vorlesung, Mi. 5.11.2003 
    Mycielski Graphen
    Extremale Kantenzahlen bei gegebenem χ
    Maximale Kantenzahl bei gegebenem ω
       Der Satz von Turán
6. Vorlesung, Fr. 7.11.2003 
    Zwei weitere Beweise für den Satz von Turán 
       (vergl. Das BUCH der Beweise)  
    Eine Schranke für α
        Beweise mit Algo MAX und mit Zufall
7. Vorlesung, Mi. 12.11.2003 
    Färbungskritische Graphen
       Einfache Eigenschaften
       Kantenzusammenhang
       Hajos Vermutung
8. Vorlesung, Mi. 19.11.2003 
    Fraktionale Färbungen
       Motivation
       Definition und einfache Beispiele
       Fraktionale Cliquen
9. Vorlesung, Fr. 21.11.2003 
       Ungerade Kreise
       IP Formulierung für χ und ω
       Fraktionale Parameter und LP Dualität
10. Vorlesung, Mi. 26.11.2003 
    Kneser Graphen und Färbungen
       Homomorphismen und Fraktionale Färbungen
       Kneser Graphen, K(t,b)
       Satz von Erdös-Ko-Rado und α(K(t,b))
11. Vorlesung, Fr. 28.11.2003 
       Chromatische Zahl von Kneser Graphen
    Matchings und Kantenfärbungen
       Komplemente bipartiter Graphen
       Satz von König-Egervary
12. Vorlesung, Mi. 3.12.2003 
       Kantenfärbung bipartiter Graphen
       Einfache Schranken für Kantenfärbungen
    Line Graphen
       Obstruktionen und Charakterisierung
Fr. 5.12.2003 
    -- Streik --
    -- Haus gesperrt --
13. Vorlesung, Mi. 10.12.2003 
       Satz von Vizing
    Zählen von Färbungen
       Das chromatische Polynom
       Darstellung und Beispiele
       Rekursion
14. Vorlesung, Fr. 12.12.2003 
       Whitneys Darstellung des chromatischen Polynoms
       Azyklische Orientierungen
15. Vorlesung, Mi. 17.12.2003 
Planare Graphen
       Jordanscher Kurvensatz
       K_5 und K_33
       Dualität
    Euler Formel
       Beweis I: Duale Bäume
       Beweis II: Noahs Arche
Fr. 19.12.2003 
    -- Streik --
    -- Haus gesperrt --
16. Vorlesung, Mi. 7.1.2004 
       Beweis III: Verrechnen von Ladungen
    Folgerungen aus der Euler Formel
    Planare Graphen und Färbungen
       5-Farben Satz
       4-Farben Satz (der "Beweis" von Kempe)
       Satz von Tait
17. Vorlesung, Fr. 9.1.2004 
       Umformulierungen des Satzes von Tait
       Hamiltonsche 3-reguläre Graphen
    Nirgends Null Flüsse
       nN 2-Flüsse   
       nN 3-Flüsse 3-regulärer Graphen
18. Vorlesung, Mi. 14.1.2004 
       nN Flüsse in planaren Graphen
       Das Flusspolynom
       Chromatisches Polynom, Flusspolynom, Tutte Polynom
       Schwierige Vermutungen: nN 5-Fluss Vermutung; Kreisdoppelüberd.
19. Vorlesung, Fr. 16.1.2004 
    Tutte-Polynom und Bäume
       Rekursion für das Tutte Polynom
       Aufspannende Bäume, interne und externe Aktivität
       Inversionen von Bäumen und Permutationen
       Parking Funktionen
20. Vorlesung, Mi. 21.1.2004 
    Matrix-Baum Theorem
       Satz von Cayley
21. Vorlesung, Fr. 23.1.2004 
    Planare Graphen, die klassischen Sätze (bis 1960)
       Satz von Kuratowski (K_5 & K_3,3 Unterteilungen)
       Satz von Wagner  (K_5 & K_3,3 Minoren)   
       Satz von Wagner, Fary, Stein (Gradlinige Darstellungen)
       Satz von Whitney (Eindeutige Darstellung)
       Satz von Whitney (Existenz eines Duals)
22. Vorlesung, Mi. 28.1.2004 
     
       Satz von Tutte (Konvexe Darstellung)
       Satz von Wagner (Skelette von Polytopen)
    Modernere Entwicklungen
       Erkennungsalgorithmen
       Auflösung von Darstellungen
23. Vorlesung, Fr. 30.1.2004 
    Dimension von Graphen     
       Graphen mit Dimension höchstens 2
       Graphen mit Dimension 3 sind planar
       Dimension vollständiger Graphen
       Dimension 4-chromatischer Graphen
    Schnyder Färbungen
       3-Orientierungen
24. Vorlesung, Mi. 4.2.2004 
       Bijektion zwischen Schnyder Färbungen und 3-Orientierungen
       Die Regionen eines Knotens
       Planare Graphen haben Dimension drei
       Der Regionsvektor eines Knotens
25. Vorlesung, Fr. 6.2.2004 
       Zeichnungen auf dem (f-1)x(f-1) Gitter
    Weitere Anwendungen von Schnyder Färbungen
       Wagners Satz über Flips zwischen Triangulierungen
       Zählen von Triangulierungen
       Der Verband der Schnyder Färbungen
       Verbände von α-Orientierungen
       Beispiel: Aufspannende Bäume eines planaren Graphen
26. Vorlesung, Mi. 11.2.2004 
    Kreuzungszahlen
       Kreuzungszahl und gradlinige Kreuzungszahl
       Das Crossing-Lemma
       Kreuzungszahlen vollständiger Graphen
27. Vorlesung, Fr. 13.2.2004 
       Eine bessere Konstante für das Crossing-Lemma
          k-beschränkte Grphen
       Anwendungen des Crossing-Lemmas
          Die Inzidenzschranke von Szemeredi-Trotter
28. Vorlesung, Mi. 18.2.2004 
       Eine Anwendung aus der kombinatorischen Zahlentheorie
       Einheitsabstände
          Exkurs: Die chromatische Zahl der Ebene
    Extremalprobleme in der kombinatorischen Geometrie
       Grundlegendes: Euklidisch, projektiv, Dualität
29. Vorlesung, Fr. 20.2.2004 
       Gewöhnliche Punkte in Arrangements / 
           gewöhnliche Geraden in Punktkonfigurationen
       Existenz und Anzahl
       Dreiecke in Arrangements


Zurück zur Vorlesungsseite.