Inhaltsverzeichnis

Graphentheorie

Wintersemester 2015/16
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.2015 

    Anstoß: 3 Probleme      
    Einleitung
       Grundsätzliche Definitionen
       Isomorphie und Subgraphen
       Einige wichtige Graphen
    Lösung: Problem I
2. Vorlesung, Do. 15.10.2015 
       Matrizen und Graphen
    Lösung: Problem II
       Geometrische Graphen ohne disjunkte Kanten
       Topologische Graphen, Thrackles
    Lösung: Problem III
       Starre Gitter: Parallelklassen - Zusammenhang
       Starrheitstheorie einige Resultate
3. Vorlesung, Mo. 19.10.2015 
      Gradfolgen
         Charakterisierung von Havel und Hakimi
         Der Übergangsgraph der 2-Switches
      Wege und Kreise
      Durchmesser und Radius
4. Vorlesung, Do. 22.10.2015 
      Zusammenhang
         Knotenzusammenhang
         Kantenzusammenhang
         Κ(G) vs Κ'(G)
         Der Satz von Menger
           u-v Separatoren
           allgemeine Separatoren
5. Vorlesung, Mo. 26.10.2015 
         8 Varianten des Satzes von Menger
            weitere Dualitätssätze
     Bäume und Wälder
        Charakterisierungen von Bäumen               
        Aufspannende Bäume
           Algorithmische Existenzbeweise
        Exkurs: Matroide
6. Vorlesung, Do. 29.10.2015 
        Bridg-It
           Spiel und Gewinnstrategie
        Satz von Cayley 
           Beweise: Prüfer, Clarke,
7. Vorlesung, Mo. 02.11.2015 
 
           Beweise: Pitman, Joyal 
        F2 Vektorräume eines Graphen
           Knoten- und Kantenraum
           Schnitt- und Zykelraum
           F2 Orthogonalität
           Fundamentalbasen
8. Vorlesung, Do. 05.11.2015 
         Licht-aus; eine Anwendung von F2 Vektorräumen 
         R Vektorräume eines Graphen
           Zirkulationen und Schnitte
       Matrix Baum Theorem
           Matrix Baum Theorem für gerichtete Graphen
           Arboreszenzen 
           Reduktion auf Graphen mit outdeg(v) = 1
9. Vorlesung, Mo. 09.11.2015 
        Euler Kreise
        Memory Wheels 
           Der deBruijn Graph Bn(m)
        BEST Theorem 
           Zählen von Euler-Kreisen in gerichtete Graphen
           Eigenwertversion von Matrix Baum
10. Vorlesung, Do. 12.11.2015 
    Planare Graphen
        Zeichnungen, Kreuzungen und Jordanscher Kurvensatz
        K5 und K3,3 sind nicht planar
        Duale Graphen
        3 Beweise der Euler Formel
        Das "Art Gallery Problem"
11. Vorlesung, Mo. 16.11.2015 
    Matroide
       Unabhängigkeitsaxiome
       Beispiele von Matroiden
       Begriffe und alternative Axiomensysteme
       Der Greedy Algorithmus für Matroide
12. Vorlesung, Do. 19.11.2015 
      Optimierung im Durchschnitt von Matroiden
      Duale Matroide
      Lineare Matroide
        Darstellungssatz für duale Matroide
        Ein Beispiel aus der Pappus Konfiguration
13. Vorlesung, Mo. 23.11.2015 
      Minoren von Matroiden - Klassifikationssätze
      Graphische Matroide
   Planare Graphen
      Folgerungen aus der Euler Formel
      Sätze von Kuratowski und Wagner
14. Vorlesung, Do. 26.11.2015 
        Beweis Kuratowski
      Satz von Whitney (Eindeutige Darstellung)
      Satz von Hanani-Tutte (independent odd crossings)
15. Vorlesung, Mo. 30.11.2015 
        Beweis Hanani-Tutte
      Gittereinbettungen
        Schnyder-Woods
        Regionen
16. Vorlesung, Do. 03.12.2015 
        Zählen von Flächen in Regionen
        Das leere Dreieck einer Kante
        Kreuzungsfreiheit
      Dreieckskontaktdarstellungen
        Zusammenhang mit Schnyder-Woods
        Zeichenalgorithmus
17. Vorlesung, Mo. 07.12.2015 
      Satz von Koebe
        Kreispackungsdarstellung von Triangulierungen
        Orthogonale Kreispackungen
18. Vorlesung, Do. 10.12.2015 
          Die Parameter α, ω, χ und Θ
       Extremale Graphentheorie          
           Dreiecksfreie Graphen  
       Der Satz von Turán
         Beweis 1: Kurze Induktion
         Beweis 2: Mit dem drei Knoten Lemma 
         Beweis 3: Mit Cauchy-Schwarz
       Anzahl Dreiecke in dichten Graphen
19. Vorlesung, Mo. 14.12.2015 
       ex(n,H) und Erdös-Stone
    Eine Schranke für α
       Beweis. Über Algo MIN
       Beweis. Zufällige Permutation 
    Ramsey Theorie
         Monotone Teilfolgen (Erdös Szekeres)
20. Vorlesung, Do. 17.12.2015 
      Graphen-Ramsey
        Beweis durch induzierte Färbung
        Untere Schranke für R(n,n)
     Allgemeiner Ramsey; Rk(t;n1,..,nt)
     Anwendung: The Happy End Problem (konvexe Mengen)
         Esther Klein Lemma
         Der Satz von Erdös Szekeres
            N(n) < R4(5,n)
21. Vorlesung, Mo. 4.1.2016 
      Kreuzungszahlen
         Zarankiewicz Problem
         Die Kreuzungszahl von Kn
         Gradlinige vs. allgemeine Kreuzungszahl
         Crossing Lemma
22. Vorlesung, Do. 7.1.2016 
    Färbungen
      Untere Schranken
         χ und ω für Zufallsgraphen
      Obere Schranken
         Greedy Färbung
     Greedy Färbungen und k-Degeneriertheit
23. Vorlesung, Mo. 11.1.2016 
       Färbungen und Orientierungen
         Partielle Ordnungen, Ketten und Antiketten
           Vergleichbarkeits- und Unvergleichbarkeitsgraphen sind perfekt
         Satz von Gallai-Roy
      Satz von Brooks
      Die Vermutungen von Hadwiger und Hajos
24. Vorlesung, Do. 14.1.2016 
    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
25. Vorlesung, Mo. 18.1.2016 
        Zur Ganzzahligkeitslücke: χ <= (1+ln(α)χf
        Färbungen und Homomorphismen
        Kneser Graphen
        Fraktionale Färbungszahl von Kneser Graphen
        Satz von Erdös-Ko-Rado
        Färbungszahl von Kneser Graphen (ein topologisches Argument)
26. Vorlesung, Do. 21.1.2016 
    Listenfärbungen
       Listenfärbungen bipartiter Graphen
         Zwei Beispielfamilien mit  χL > k
         log(n) als obere Schranke
         (randomisiert|derandomisiert)
       Listenfärbung planarer Graphen
27. Vorlesung, Mo. 25.1.2016 
       (Vertretung Linda Kleist)
       Färbungen planarer Graphen (4-Farben Satz)
          Geschichtliches -- Kempes (fehlerhafter) Beweis
          Grundlegende Ideen zum (Computer-)Beweis
            Unvermeidbare Mengen/Entladungsmethode
            Reduzible Konfigurationen
28. Vorlesung, Do. 28.1.2016 
    Färbungen, Orientierungen und Polynome
        Das Graph-Polynom und Färbbarkeit
        Die Koeffizienten und Orientierungen 
        Die Standardform und eulersche Untergraphen
        Der Satz von Alon-Tarsi
          Beispielanwendungen
          Kombinatorischer Nullstellensatz
29. Vorlesung, Mo. 1.2.2016 
          Listenfärbungszahl planarer bipartiter Graphen
    Perfekte Graphen  
      4 zentrale Klassen perfekter Graphen      
      Die Berge Vermutungen 
      Chordale Graphen
        Cliquenseparatoren und simpliziale Knoten
30. Vorlesung, Do. 4.2.2016 
        Perfekte Eliminationsordnung 
        Exkurs: Durchschnittsgraphen und Helly-Eigenschaft
        Baumdarstellung 
     Der (kleine) Perfekte-Graphen-Satz
        Gasparians Beweis
31. Vorlesung, Mo. 8.2.2016 
    Baumzerlegungen und Baumweite 
        Baumzerlegungen und chordale Graphen
        Baumweite und Robber&Cops 
        Algorithmische Anwendungen
           Ein FPT Alg. für 3-Färbbarkeit
32. Vorlesung, Do. 11.2.2016 

        Berechnen von Baumzerlegungen und Satz von Courcelle
        Baumweite und Minoren
        Das Graph-Minor-Theorem von Robertson und Seymour
        Wohlquasiordnungen
           Binäre Bäme sind WQO mit der Teilgraph-Relation







Zurück zur 
Vorlesungsseite.