Inhaltsverzeichnis

Graphentheorie

Wintersemester 2007/08
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 , 30 , 31 .

1. Vorlesung, Mo. 15.10.2007 

    Einleitung
       Geometrische Graphen ohne disjunkte Kanten
       Topologische Graphen, Thrackles
       Graphen in Anwendungen
       Graphen als Modell
2. Vorlesung, Di. 16.10.2007 
         Beispiel: Ramsey(3,3)
         Beispiel: Jobzuordnung und Matching
           Satz von Hall
         Beispiel: Ausschusstermine und Färbung
       Einige wichtige Graphen
3. Vorlesung, Mo. 22.10.2007 
       Matrizen und Isomorphie
         zählen von Graphen
       Homomorphismen
       Reguläre Graphen
4. Vorlesung, Di. 23.10.2007 
    Gradsequenzen
       Charakterisierung von Havel und Hakimi
         Der Übergangsgraph der 2-Switches
5. Vorlesung, Mo. 29.10.2007 
       Charakterisierung von Erdös-Gallai
    Abstand, zentrale Knoten und Radius
       Durchmesser und Girth, verallgemeinerte Polygone
6. Vorlesung, Di. 30.10.2007 
         Exkurs: Endliche projektive Ebenen
    Zusammenhang
       Separatoren
7. Vorlesung, Mo. 5.11.2007 
       Schnitte
       Der 2-Knoten Menger      
       Satz von Menger
       Verschärfung von X.Li
8. Vorlesung, Di. 6.11.2007 
    Der Satz von Turán
       Beweise für den Satz von Turán 
       (vergl. "Das BUCH der Beweise") 
         Verschieben von Gewichten
         Mit dem drei Knoten Lemma
9. Vorlesung, Mo. 12.11.2007 
         Mit der Cauchy-Schwarz Ungleichung
    Eine Schranke für α
       Beweis 1. Randomisiert
       Beweis 2. Über Algo MIN
       Beweis 3. Über Algo MAX
10. Vorlesung, Di. 13.11.2007 
    Ramsey Theorie
       Schubfachprinzip und Anwendungen
         Monotone Teilfolgen (Erdös Szekeres) 
         Bruchlinien
       Der allgemeine Ramsey; Rk(t;n1,..,nt)
         Zwei Beweise für R(n,m)
	 Die untere Schranke
11. Vorlesung, Mo. 19.11.2007 
         Der allgemeine Ramsey (Beweis)
       Anwendung: The Happy End Problem (konvexe Mengen)
         Esther Klein Lemma
         Der Satz von Erdös Szekeres
         Bew I: f(n) < R4(2;5,n)
         Bew II: f(n) < R3(2;n,n)
	 Bew III: f(n) < (2n-4 choose n-2) + 1
12. Vorlesung, Di. 20.11.2007 
         Leere konvexe k-Teilmengen
         Die Bestimmung von R(3,4) und R(3,5)
    Bäume zählen 
       Satz von Cayley
         Bew I: Prüfer-Code
         Bew II: Verfeinert zählen
13. Vorlesung, Mo. 26.11.2007 
         Bew III: Bijektion mit Zykelwäldern (Joyal)
       Matrix Baum Theorem
         Bew IV: Cayley als Folgerung aus MBT
14. Vorlesung, Di. 27.11.2007 
    Euler-Kreise zählen 
       BEST Theorem
       Zählen von Euler-Kreisen in de Bruijn Graphen
15. Vorlesung, Mo. 3.12.2007 
       Zählen von Euler-Kreisen ist #P-vollständig
    Hamilton Kreise
16. Vorlesung, Di. 4.12.2007 
       Satz von Dirac
       Alpha vs. Kappa
       Notwendige Bedingung und toughness
       Hamiltonscher Abschluss
       Satz von Chvátal
17. Vorlesung, Mo. 10.12.2007 
    Färbungen
      Untere Schranken
        χ und ω für Zufallsgraphen
      Greedy Färbungen und k-Degeneriertheit
      Satz von Brooks
18. Vorlesung, Di. 11.12.2007 
    Perfekte Graphen
       Der Satz von König--Egervary
       Komplemente bipartiter Graphen sind perfekt
       Line-Graphen bipartiter Graphen sind perfekt
19. Vorlesung, Di. 18.12.2007 
    Kantenfärbungen - der chromatische Index
       Satz von Vizing
         Beweis von Schrijver
         Klassischer Beweis
20. Vorlesung, Mo. 7.1.2008 
     Fraktionale Färbungen
        b-Färbungen
        Fraktionale Färbungszahl χf
        Ungerade Kreise
        b-Cliquen und fraktionale Cliquenzahl ωf
        Färbungs- und Cliquenzahl über 0-1 Programme
        LP-Relaxation und Dualität 
        χf =  ωf
21. Vorlesung, Di. 8.1.2008 
        Färbungen und Homomorphismen
        Kneser Graphen
        Zur Ganzzahligkeitslücke: χ <= (1+ln(α)χf
        Fraktionale Färbungszahl von Kneser Graphen
        Satz von Erdos-Ko-Rado
22. Vorlesung, Mo. 14.1.2008 
        Färbungszahl von Kneser Graphen (ein topologisches Argument)
      Das chromatische Polynom
        Zählen von Färbungen
        Die Zählfunktion ist ein Polynom
        Chromatisches Polynom und delete/contract
23. Vorlesung, Di. 15.1.2008 
        Darstellung von Whitney
        Chromatisches Polynom und Cliquenseparatoren
        Azyklische Orientierungen
24. Vorlesung, Mo. 21.1.2008 
      Triangulierte Graphen
        Cliquenseparatoren
        Simpliziale Knoten
25. Vorlesung, Di. 22.1.2008 
        Perfekte Eliminationsordnung
        Baumdarstellung
        Triangulierte Graphen sind perfekt
      Perfekte Reihungen
        Vergleichbarkeitsgraphen
           Partielle Ordnungen
           Lineare Erweiterungen
26. Vorlesung, Mo. 28.1.2008 
        Perfekte Reihungen und böse P4
      Der Perfekte Graphen Satz
        Gasparians Beweis
27. Vorlesung, Di. 29.1.2008 
        Struktur minimal imperfekter Graphen
        Das Polytop der unabhängigen Mengen
        Kantenungleichungen und bipartite Graphen
28. Vorlesung, Mo. 4.2.2008 
        Cliquenungleichungen
        Gewichtete Cliquen und Färbungen
        Zweiter Beweis des Perfekte Graphen Satzes
29. Vorlesung, Di. 5.2.2008 
        Zweiter Beweis des Perfekte Graphen Satzes 
        Optimierung über Polytopen
        Die konvexe Ecke TH(G)
30. Vorlesung, Mo. 11.2.2008 
      On-Line Färbungen
        Wälder
        Bipartite Graphen
        Eine untere Schranke für allgemeine Graphen
31. Vorlesung, Di. 12.2.2008 
      On-Line Ordnungen
        Antikettenzerlegungen
        Kettenzerlegungen
Zurück zur Vorlesungsseite.