Inhaltsverzeichnis

Graphentheorie

Wintersemester 2013/14
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, Di. 15.10.2013 

    Anstoß: 3 Probleme      
    Einleitung
       Grundsätzliche Definitionen
       Isomorphie und Subgraphen
    Lösung: Problem I
       Matrizen und Graphen
2. Vorlesung, Di. 15.10.2013 
    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, Di. 22.10.2013 
       Gradfolgen
       Charakterisierung von Havel und Hakimi
         Der Übergangsgraph der 2-Switches
      Wege und Kreise
4. Vorlesung, Di. 22.10.2013 
      Zusammenhang
         Knotenzusammenhang
         Kantendisjunkte u-v Wege 
         Der Satz von Menger
         8 Varianten des Satzes von Menger
            weitere Dualitätssätze
         Kantenzusammenhang
         Κ(G) vs Κ'(G)
5. Vorlesung, Di. 29.10.2013 
     Bipartite und k-partite Graphen
     Bäume und Wälder
        Charakterisierungen von Bäumen               
        Aufspannende Bäume
           Algorithmische Existenzbeweise
        Exkurs: Matroide
6. Vorlesung, Di. 29.10.2013 
        Bridg-It
           Spiel und Gewinnstrategie
        Satz von Cayley 
           Beweise: Prüfer, Clarke und  Joyal
7. Vorlesung, Di. 05.11.2013 
        Euler Kreise
        F2 Vektorräume eines Graphen
           Knoten- und Kantenraum
           Schnitt- und Zykelraum
           F2 Orthogonalität
8. Vorlesung, Di. 05.11.2013 
           Fundamentalbasen   
           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) < 2
        Memory Wheels
9. Vorlesung, Di. 12.11.2013 
           Der deBruijn Graph Bn(m)
        BEST Theorem 
           Zählen von Euler-Kreisen in gerichtete Graphen
           Eigenwertversion von Matrix Baum
10. Vorlesung, Di. 12.11.2013 
           Eigenwerte von Bn(m)
           Memory wheels und Schieberegisterfolgen 
        Eigenwerte von Adjazenzmatrizen
11. Vorlesung, Di. 19.11.2013 
       Extremale Graphentheorie
           Dreiecksfreie Graphen  
       Der Satz von Turán
         Beweis 1: Verschieben von Gewichten
         Beweis 2: Kurze Induktion
         Beweis 3: Mit dem drei Knoten Lemma 
         Beweis 4: Mit Cauchy-Schwarz
12. Vorlesung, Di. 19.11.2013 
       Anzahl Dreiecke in dichten Graphen
       ex(n,H) und Erdös-Stone
       ex(n,C4) 
    Eine Schranke für α
       Vorüberlegung: Wahl von I mit Zufall
       Beweise. Über Algo MAX und Algo MIN
13. Vorlesung, Di. 26.11.2013 
       - Exkurs: diskrete Wahrscheinlichkeit
       Beweis 3. Zufällige Permutation 
    Ramsey Theorie
         Monotone Teilfolgen (Erdös Szekeres) 
      Graphen-Ramsey
         Beweis durch induzierte Färbung
14. Vorlesung, Di. 26.11.2013 
        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
            N(n) < R4(5,n)
15. Vorlesung, Di. 3.12.2013 
         Zwei Beweise für
            N(n) < R3(n,n)
         CAPs und CUPs in Punktmengen
            Die klassische Erdös Szekeres Schranke
16. Vorlesung, Di. 3.12.2013 
      Kreuzungszahlen
           Zarankiewicz Problem
           Gradlinige vs. allgemeine Kreuzungszahl
           Das crossing lemma
        Einheitsabstände in der Ebene
17. Vorlesung, Di. 10.12.2013 
        Die Kreuzungszahl von Kn
      Hamilton Kreise
        Hinreichende Bedingungen
           Satz von Dirac
           Satz von Chvatal-Erdös
        Notwendige Bedingung
18. Vorlesung, Di. 10.12.2013 
        Hamiltonscher Abschluss
    Färbungen
      Untere Schranken
         χ und ω für Zufallsgraphen
      Obere Schranken
         Greedy Färbung
19. Vorlesung, Di. 17.12.2013 
      Greedy Färbungen und k-Degeneriertheit
      Färbungen und Orientierungen
         Satz von Gallai-Roy
      Satz von Brooks
20. Vorlesung, Di. 17.12.2013 
      Die Vermutungen von Hadwiger und Hajos
    Kantenfärbungen - der chromatische Index
       Kantengraphen (Line-Graphs)
       Der Satz von König
          (Line-Graphen bipartiter Graphen sind perfekt)
       Der Satz von König--Egervary
21. Vorlesung, Di. 7.1.2014 
       Der Satz von Vizing
         Umfärbungen in Fächern
    Listenfärbungen
       Listenfärbungen bipartiter Graphen
         Eine Beispielfamilie 
         log(n) als obere Schranke (randomisiert|derandomisiert)
22. Vorlesung, Di. 7.1.2014 
    Listenfärbungen, Orientierungen und Kerne
    Listenkantenffärbungen bipartiter Graphen
        (Satz von Galvin)
    Färbungen, Orientierungen und Polynome
        (Alon-Tarsi)
        Das Graph-Polynom und Färbbarkeit
        Die Koeffizienten und Orientierungen
23. Vorlesung, Di. 14.1.2014 
        Die Standardform und eulersche Untergraphen
        Der Satz von Alon-Tarsi
          Beispielanwendungen
          Kombinatorischer Nullstellensatz
24. Vorlesung, Di. 14.1.2014 
         Anwendung: planar bipartite Graphen
         Anwendung Nullstellensatz: p-reguläre Subgraphen
    Perfekte Graphen        
      Chordale Graphen
        Cliquenseparatoren und simpliziale Knoten
25. Vorlesung, Di. 21.1.2014 
        Perfekte Eliminationsordnung 
        Exkurs: Durchschnittsgraphen und Helly-Eigenschaft
        Baumdarstellung
26. Vorlesung, Di. 21.1.2014 
     Vergleichbarkeits- und Unvergleichbarkeitsgraphen 
     Die Berge Vermutungen 
     Der (kleine) Perfekte-Graphen-Satz
        Gasparians Beweis
27. Vorlesung, Di. 28.1.2014 
    Das Polytop der unabhängigen Mengen STAB(G)
        Gültige Ungleichungen ESTAB und QSTAB
        Knotenmultiplikation und der Perfekt-Graphen-Satz
28. Vorlesung, Di. 28.1.2014 
        Optimierung über STAB und QSTAB
        Konvexe Ecken und Antiblocker
        Die Lovasz Ecke TH(G)
    Baumzerlegungen und Baumweite
29. Vorlesung, Di. 4.2.2014 
    Baumzerlegungen und Baumweite 
        Baumzerlegungen und chordale Graphen
        Baumweite und Rober&Cops 
        Algorithmische Anwendungen
           Ein FTP Alg. für 3-Färbbarkeit
30. Vorlesung, Di. 4.2.2014 
        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
31. Vorlesung, Di. 11.2.2014 
    Planare Graphen
        Zeichnungen, Kreuzungen und Jordanscher Kurvensatz
        K5 und K3,3 sind nicht planar
        Duale Graphen
        3 Beweise der Euler Formel
        Folgerungen aus der Euler Formel
32. Vorlesung, Di. 11.2.2014 
        Der Satz von Kuratowski
Zurück zur Vorlesungsseite.