Inhaltsverzeichnis

Graphentheorie

Wintersemester 2011/12
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. 18.10.2011 

    Einleitung
       Grundsätzliche Definitionen
       Isomorphie und Subgraphen
       Anwendungen der Graphentheorie
       Matrizen und Graphen
2. Vorlesung, Di. 18.10.2011 
       Geometrische Graphen ohne disjunkte Kanten
       Topologische Graphen, Thrackles
       Gradfolgen
       Charakterisierung von Havel und Hakimi
3. Vorlesung, Di. 25.10.2011 
         Der Übergangsgraph der 2-Switches
      Wege und Kreise
      Zusammenhang
         Knotenzusammenhang
         Kantenzusammenhang
         Κ(G) vs Κ'(G)
4. Vorlesung, Di. 25.10.2011 
         Kantendisjunkte u-v Wege 
         Der Satz von Menger
         8 Varianten des Satzes von Menger
            weitere Dualitätssätze
     Bäume und Wälder
        Charakterisierungen von Bäumen
5. Vorlesung, Di. 01.11.2011 
        Aufspannende Bäume
           Algorithmische Existenzbeweise
        Bridg-It
           Spiel und Gewinnstrategie
           Shannon's Switching Game
6. Vorlesung, Di. 01.11.2011 
        Satz von Cayley (Beweis Clarke)
        Satz von Cayley (Beweis Joyal)
        Euler Kreise
        F2 Vektorräume eines Graphen
           Knoten- und Kantenraum
           Schnitt- und Zykelraum
7. Vorlesung, Di. 08.11.2011 
           Schnitt- und Zykelraum
           F2 Orthogonalität
           Fundamentalbasen   
        R Vektorräume eines Graphen
           Zirkulationen und Schnitte
8. Vorlesung, Di. 08.11.2011 
       Matrix Baum Theorem
           reduzierte Inzidenzmatrix N
           det(N(F)) für Kantenmengen F mit |F|=n-1
           Cauchy-Binet
        Matrix Baum Theorem für gerichtete Graphen
           Arboreszenzen 
           Reduktion auf Graphen mit outdeg(v) < 2
9. Vorlesung, Di. 15.11.2011 
        BEST Theorem 
           Zählen von Euler-Kreisen in gerichtete Graphen
        Memory Wheels 
           Der deBruijn Graph Bn(m)
10. Vorlesung, Di. 15.11.2011 
           Eigenwertversion von Matrix Baum
           Eigenwerte von Bn(m)
           Memory wheels und Schieberegisterfolgen             
       Extremale Graphentheorie
           Dreiecksfreie Graphen
11. Vorlesung, Di. 22.11.2011 
    Extremale Graphentheorie
       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. 22.11.2011 
       ex(n,H) und Erdös-Stone
       ex(n,C4) 
    Eine Schranke für α
       Beweis 1. Über Algo MIN
       Beweis 2. Über Algo MAX
       - Exkurs: diskrete Wahrscheinlichkeit
       Beweis 3. Zufällige Permutation
13. Vorlesung, Di. 29.11.2011 
    Hamilton Kreise
       Satz von Dirac
       Notwendige Bedingung und toughness
       Hamiltonscher Abschluss
14. Vorlesung, Di. 29.11.2011 
    Färbungen
      Untere Schranken
        χ und ω für Zufallsgraphen
      Greedy Färbungen und k-Degeneriertheit
15. Vorlesung, Di. 6.12.2011 
      Greedy Färbungen weitere Schranken
      Färbungen und Orientierungen
         Satz von Gallai-Roy
      Satz von Brooks
16. Vorlesung, Di. 6.12.2011 
    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
17. Vorlesung, Di. 13.12.2011 
    Listenfärbungen
       Listenfärbungen bipartiter Graphen
    Stabile Hochzeiten
18. Vorlesung, Di. 13.12.2011 
    Listenfärbungen, Orientierungen und Kerne
    Listenkantenffärbungen bipartiter Graphen
        (Satz von Galvin)
   Das chromatische Polynom
      Zählen von Färbungen
      Die Zählfunktion ist ein Polynom
19. Vorlesung, Di. 3.1.2012 
     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
20. Vorlesung, Di. 3.1.2012 
        Zur Ganzzahligkeitslücke: χ <= (1+ln(α)χf
        Färbungen und Homomorphismen
        Kneser Graphen
        Fraktionale Färbungszahl von Kneser Graphen
        Satz von Erdos-Ko-Rado
        Färbungszahl von Kneser Graphen (ein topologisches Argument)
21. Vorlesung, Di. 10.1.2012 
    Perfekte Graphen
        Die Berge Vermutungen und ihre Geschichte
    Chordale Graphen
        Cliquenseparatoren und simpliziale Knoten
        Perfekte Eliminationsordnung 
        Exkurs: Durchschnittsgraphen und Helly-Eigenschaft
22. Vorlesung, Di. 10.1.2012 
       Baumdarstellung 
       Perfectly orderable graphs
    Der Perfekte Graphen Satz
        Gasparians Beweis
23. Vorlesung, Di. 17.1.2012 
    Das Polytop der unabhängigen Mengen STAB(G)
        Gültige Ungleichungen ESTAB und QSTAB
        Knotenmultiplikation und der Perfekte Graphen Satz
24. Vorlesung, Di. 17.1.2012 
    Aspekte von "Intersection Graphs"
        Intervallgraphen und Intervallordnungen 
           Eigenschaften und Charakterisierungen
        Verallgemeinerungen in 2-d und auf dem Kreis
25. Vorlesung, Di. 24.1.2012 
    Matroide
       Unabhängigkeitssysteme
       Matroide - lineare/graphische/partitions/transversal
       Graphische Matroide sind linear
       Ein nichtlineares Matroid (Pappus)
       Das Fano Matroid
26. Vorlesung, Di. 24.1.2012 
       Der Greedy-Algorithmus für Matroide
       Begriffe und alternative Axiomensysteme
       Das duale Matroid
       Minoren und Charakterisierungssätze
27. Vorlesung, Di. 31.1.2012 
    Planare Graphen
        Zeichnungen und Kreuzungen
        Jordanscher Kurvensatz
        K5 und K3,3 sind nicht planar
        Duale Graphen
28. Vorlesung, Di. 31.1.2012 
        Bond Matroide
        Satz von Whitney (Planarität und Matroide)
        3 Beweise der Euler Formel
29. Vorlesung, Di. 7.2.2012 
        Folgerungen aus der Euler Formel
        Der Satz von Kuratowski
30. Vorlesung, Di. 7.2.2012 
        Konvexe Zeichnungen 3-zusammenhängender planarer Graphen 
        Färben planarer Graphen
           Heawoods 5 und Kempes 4-Farbensatz
31. Vorlesung, Di. 14.2.2012 
    Der Plan für den 4-Farben Beweis
        Unvermeidbare Mengen - Entladung
        Reduzierbarkeit - Umfärbungstechniken
32. Vorlesung, Di. 14.2.2012 
    Satz von Tait
    Hamilton Kreise in 3-regulären Graphen
    Das Tutte Beispiel
Zurück zur Vorlesungsseite.