Inhaltsverzeichnis

Graphentheorie

Wintersemester 2009/10
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 . 32 ,

1. Vorlesung, Mo. 12.10.2009 

    Einleitung
       Grundsätzliche Definitionen
       Anwendungen der Graphentheorie
       Geometrische Graphen
2. Vorlesung, Di. 13.10.2009 
       Geometrische Graphen ohne disjunkte Kanten
       Topologische Graphen, Thrackles
       Weitere Begriffe
       Gradfolgen
3. Vorlesung, Mo. 19.10.2009 
         Charakterisierung von Havel und Hakimi
         Der Übergangsgraph der 2-Switches
      Wege und Kreise
      Zusammenhang
         Knotenzusammenhang
4. Vorlesung, Di. 20.10.2009 
         Kantenzusammenhang
         Κ(G) vs Κ'(G)
         Kantendisjunkte u-v Wege und MaxFlow-MinCut
      Bipartite und r-partite Graphen
5. Vorlesung, Mo. 26.10.2009 
     Bäume und Wälder
        Charakterisierungen von Bäumen
        Aufspannende Bäume
           Matroide
        Satz von Cayley (Beweis Clarke)
6. Vorlesung, Di. 27.10.2009 
        Satz von Cayley (Beweis Joyal)
        Minimal Aufspannende Bäume
           Rote und blaue Regel
           Algorithmen
           Matroid-Greedy Thm.
7. Vorlesung, Mo. 02.11.2009 
        Euler Kreise
        F2 Vektorräume eines Graphen
           Knoten- und Kantenraum
           Schnitt- und Zykelraum
           F2 Orthogonalität
           Fundamentalbasen
8. Vorlesung, Di. 03.11.2009 
        R Vektorräume eines Graphen
           Zirkulationen und Schnitte
        Matrix Baum Theorem
           Noch ein Beweis für den Satz von Cayley
           reduzierte Inzidenzmatrix N
           det(N(F)) für Kantenmengen F mit |F|=n-1
9. Vorlesung, Mo. 09.11.2009 
           Cauchy-Binet
        Matrix Baum Theorem für gerichtete Graphen
           Arboreszenzen 
           Reduktion auf Graphen mit outdeg(v) < 2
        BEST Theorem 
           Zählen von Euler-Kreisen in gerichtete Graphen
10. Vorlesung, Di. 10.11.2009 
        Memory Wheels 
           Der de Bruijn Graph Bn(m)
           Eigenwertversion von Matrix Baum
           Eigenwerte von Bn(m)
        Eigenwerte von Graphen
11. Vorlesung, Mo. 16.11.2009 
        Eigenwerte von Graphen
           Hauptsatz der algebraischen Graphentheorie
           Der zweite Eigenwert
           Spektrallücke
12. Vorlesung, Di. 17.11.2009 
           Expansion und Schnitte
           Expandergraphen
           Anwendungen von Expandergraphen
           Ein Beispiel: Wahrscheinlichkeitsverstärkung
13. Vorlesung, Mo. 23.11.2009 
    Vier wichtige Parameter ω, δ ,α und χ
    Extremale Graphentheorie
       Der Satz von Turán
         Beweis 1: Verschieben von Gewichten
14. Vorlesung, Di. 24.11.2009 
         Beweis 2: Kurze Induktion
         Beweis 3: Mit dem drei Knoten Lemma 
         Beweis 4: Mit Cauchy-Schwarz
       Quantitativ: wie viele Dreiecke?
       ex(n,H) und Erdös-Stone
       ex(n,C4)
15. Vorlesung, Mo. 30.11.2009 
    Eine Schranke für α
       Beweis 1. Über Algo MIN
       Beweis 2. Über Algo MAX
       - Exkurs: diskrete Wahrscheinlichkeit
       Randomisierte Auswahl
16. Vorlesung, Di. 1.12.2009 
       Randomisierte Auswahl mit Löschen
       Beweis 3. Zufällige Permutation 
    Ramsey Theorie
       Schubfachprinzip und Anwendungen
         Bruchlinien
         Monotone Teilfolgen (Erdös Szekeres) 
       Graphen-Ramsey
         Beweis durch induzierte Färbung
17. Vorlesung, Mo. 7.12.2009 
	Untere Schranken für R(n,n)
        Der allgemeine Ramsey; Rk(t;n1,..,nt)
     Anwendung: The Happy End Problem (konvexe Mengen)
         Esther Klein Lemma
         Der Satz von Erdös Szekeres
            I: N(n) < R4(2;5,n)
           II: N(n) < R3(2;n,n)
18. Vorlesung, Di. 8.12.2009 
	 III: N(n) < (2n-4 choose n-2) + 1
         k-Löcher (Leere konvexe k-Teilmengen)
    Hamilton Kreise
       Satz von Dirac
       Notwendige Bedingung und toughness
       Hamiltonscher Abschluss
19. Vorlesung, Mo. 14.12.2009 
    Färbungen
      Untere Schranken
        χ und ω für Zufallsgraphen
      Greedy Färbungen und k-Degeneriertheit
      Satz von Brooks
20. Vorlesung, Di. 15.12.2009 
      Greedy Färbungen weitere Schranken
      Färbungen und Orientierungen
         Satz von Gallai-Roy
21. Vorlesung, Mo. 4.1.2010 
    Kantenfärbungen - der chromatische Index
       Kantengraphen (Line-Graphs)
       Der chromatische Index       
       Der Satz von König
          (Line-Graphen bipartiter Graphen sind perfekt)
       Der Satz von König--Egervary
22. Vorlesung, Di. 5.1.2010 
       Satz von Vizing
         Beweis von Schrijver
         Klassischer Beweis
    Listenfärbungen
       Listenfärbungen bipartiter Graphen
23. Vorlesung, Mo. 11.1.2010 
    Stabile Hochzeiten
    Listenfärbungen, Orientierungen und Kerne
    Listenkantenffärbungen bipartiter Graphen
        (Satz von Galvin)
24. Vorlesung, Di. 12.1.2010 
   Färbungen, Polynome und Orientierungen
      Das Graphpolynom fG
      Orientierungen und die Koeffizienten von fG
      Kombinatorischer Nullstellensatz
      Der Satz von Alon-Tarsi
25. Vorlesung, Mo. 18.1.2010 
   Das chromatische Polynom
      Zählen von Färbungen
      Die Zählfunktion ist ein Polynom
      Chromatisches Polynom und delete/contract
      Darstellung von Whitney
26. Vorlesung, Di. 19.1.2010 
      Koeffizienten, Nullstellen und Berechnung
      Azyklische Orientierungen
  Das Tutte Polynom
      Darstellung als Summe über S⊆E
      Rekursion und Auswertungen
      Interne und externe Aktivität von Bäumen
27. Vorlesung, Mo. 25.1.2010 
      Chordale Graphen
        Cliquenseparatoren und simpliziale Knoten
        Perfekte Eliminationsordnung und Färbungen
        Baumdarstellung
28. Vorlesung, Di. 26.1.2010 
      Der Perfekte Graphen Satz
        Gasparians Beweis
        Das Polytop der unabhängigen Mengen
        Kantenungleichungen und bipartite Graphen
        Cliquenungleichungen
        Beweisskizze fü einen zweiten Beweis des PGS
29. Vorlesung, Mo. 1.2.2010 
    Planare Graphen
        Zeichnungen und Kreuzungen
        Jordanscher Kurvensatz
        K5 und K3,3 sind nicht planar
        Duale Graphen
        Die Euler Formel
30. Vorlesung, Di. 2.2.2010 
        4 Beweise der Euler Formel
        Folgerungen aus der Euler Formel
        Färben planarer Graphen
           Heawoods 5 und Kempes 4-Farbensatz
31. Vorlesung, Mo. 8.2.2010 
    Der Plan für den 4-Farben Beweis
        Unvermeidbare Mengen - Entladung
        Reduzierbarkeit - Unfärbungstechniken
    Satz von Tait
32. Vorlesung, Di. 9.2.2010 
    Planarität: wichtige Tatsachen
        Separator Theorem 
        Charakterisierungen 
          Kuratiwski, Wagner, MacLane, Whitney
        Satz von Steinitz
        Schnyders Charakterisierung
          Dimension von Graphen
          Schnyder woods
Zurück zur Vorlesungsseite.