Inhaltsverzeichnis

Graphentheorie

Wintersemester 2005/06
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, Mi. 19.10.2005 

   Einleitung
      Warum Graphentheorie?
      Was ist ein Graph? 
        Definitionen
      Graphen als Modell
        Beispiele
2. Vorlesung, Fr. 21.10.2005 
      Färbungsprobleme
      Matrizen und Isomorphie
        zählen von Graphen
      Der Petersen Graph und seine Kreise
   Grade
3. Vorlesung, Mi. 26.10.2005 
      Gleichungen und Ungleichungen mit Graden
      k-reguläre Graphen
      Hyperwürfel
      Charakterisierung von Gradfolgen (Havel-Hakimi)
4. Vorlesung, Fr. 28.10.2005 
      Weitere Beispiele zur Charakterisierung von Gradfolgen
   Wege und Kreise
      Euler-Kreise
      Abstand, zentrale Knoten und Radius
5. Vorlesung, Mi. 2.11.2005 
   Zusammenhang
      Separator (trennende Knotenmenge)
      Schnitt (trennende Kantenmenge)
      Eine Ungleichung für Zusammenhangszahlen
   Wälder und Bäume
6. Vorlesung, Fr. 4.11.2005 
      Charakterisierungen von Bäumen
      Aufspannende Bäume
      Satz von Cyley (zwei Beweise)
7. Vorlesung, Mi. 9.11.2005 
      Bipartite und multipartite Graphen
        Charakterisierung 
   Maximale Kantenzahlen
8. Vorlesung, Fr. 11.11.2005 
      Der Satz von Turán
        Beweise für den Satz von Turán 
       (vergl. Das BUCH der Beweise)
9. Vorlesung, Mi. 16.11.2005 
      Eine Schranke für α
        Beweis 1. Über Algo MAX
        Beweis 2. Über Algo MIN
        Beweis 3. Randomisiert
   Elektrische Netze
10. Vorlesung, Fr. 18.11.2005 
      Kirchhoffsche Gesetze
      Beispiel
      Lösungsstrategie und Eindeutigkeit
      Serien-Parallele Netzwerke
      Flüsse und aufspannende Bäume
11. Vorlesung, Mi. 23.11.2005 
      Die Existenz einer Lösung bei Einheitswiderständen
      Rationale Variablenbelegung in Lösungen
      Squaring the square
        siehe auch PerfectSquareDissection
      Satz von Dehn
      Pflasterungen (Tilings)
12. Vorlesung, Fr. 25.11.2005 
      Drei Beweise für ganzzahlige Seiten
   Kreise, Schnitte und Vektorräume
      Knoten- und Kantenraum
      Zyklenraum
        Charakterisierung von Zyklen
      Schnittraum
13. Vorlesung, Mi. 30.11.2005 
      Orthogonalität von Schnitt- und Zyklenraum
      Dimension von  Schnitt- und Zyklenraum 
        Baumbasen
   Minimal aufspannende Bäume
      Die rote und die blaue Regel (Kreis-Regel und Schnitt-Regel)
      Optimalität des generischen Greedy-Algorithmus
14. Vorlesung, Fr. 02.12.2005 
      Konkrete Instanzen des generischen Greedy-Algorithmus
        Boruvka / Kruskal / Prim
   Matroide
      Axiome für unabhängige Mengen
      Beispiele
15. Vorlesung, Mi. 07.12.2005 
      Der Greedy-Algorithmus für Matroide
      Weitere Begriffe und Axiomensysteme
      Das duale Matroid
16. Vorlesung, Fr. 09.12.2005 
      Lineare Matroide und ihre Duale
      Das fast-Pappus Matroid ist nicht linear
      Graphische Matroide sind linear
      Minoren
17. Vorlesung, Mi. 14.12.2005 
      Schnitt-Matroide, duale von Kreis-Matroiden
   Planare Graphen
      Definitionen und Jordanscher Kurvensatz
      Duale Graphen
      Schnitte und Kreise in G und G*
18. Vorlesung, Fr. 16.12.2005 
      Minoren von Graphen
      Sätze von Wagner und Robertson&Seymour [oB]
      Charakterisierung planarer Graphen über Matroide (Whitney)
      Die Euler Formel
19. Vorlesung, Mi. 4.1.2006 
      Noch zwei Beweise der Euler Formel
      Folgerungen aus der Euler Formel
      Vorbereitungen zum Beweis der Kuratowski Charakterisierung planarer Graphen
20. Vorlesung, Fr. 6.1.2006 
      Ein Lemma ueber kontahierbare Kanten in 3-zush. Graphen
      Erhalt von Kuratowski-Unterteilungen bei Kontraktion
      Streng konvexe Zeichnungen
      Outerplanare Graphen und ihre Charakterisierung
21. Vorlesung, Mi.11.1.2006 
   Graphenfärbungen
      Definition und einfache Beobachtungen
      Untere Schranken
      Greedy Färbungen und k-Degeneriertheit
      Das `Art Gallery Theorem'
      Färbung planarer Graphen
        Heawoods 5-Farben Satz
        Kempes 4-Farben Beweis
22. Vorlesung, Fr.13.1.2006 
        Der Fehler in Kempes 4-Farben Beweis
      Plan für den 4-Farben Satz
        Unvermeidbare Konfigurationen
          Entladung
        Reduzierbarkeit
          Der 4-Ring
23. Vorlesung, Mi.18.1.2006 
      Taits Kantenfärbungssatz
        3-reguläre Hamiltonsche planare Graphen
      Kantenfärbungen - der chromatische Index
        Satz von Vizing
24. Vorlesung, Fr.20.1.2006 
      Graphen auf Flächen
        Die Klassifikation geschlossener Flächen
        2-Zell Einbettungen
        Euler Formel für Graphen auf Sh
        Kantenzahlen
        Der Satz von Heawood
25. Vorlesung, Mi.25.1.2006 
      Satz von Brooks
      Vermutungen von Hadwiger und Hajos
      Das chromatische Polynom
        Zählen von Färbungen
        Die Zählfunktion ist ein Polynom
26. Vorlesung, Fr. 27.1.2006 
        Chromatische Polynom und delete/contract
        Darstellung von Whitney
        Azyklische Orientierungen
     Fraktionale Färbungen
27. Vorlesung, Mi. 1.2.2006 
        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
28. Vorlesung, Fr. 3.2.2006 
        Färbungen und Homomorphismen
        Kneser Graphen
        Fraktionale Färbungszahl von Kneser Graphen
        Satz von Erdos-Ko-Rado
29. Vorlesung, Mi. 8.2.2006 
        Färbungszahl von Kneser Graphen (ein topologisches Argument)
     Perfekte Graphen
        Die Vermutungen von Berge        
        Einige Klassen perfekter Graphen
30. Vorlesung, Fr. 10.2.2006 
        Bipartite Graphen, Vergleichbarkeitsgrapgen und 
           Line Graphen bipartiter - Sätze die aus PGT folgen
        Der perfekte Graphen Satz (ein Beweis mit linearer Algebra)
31. Vorlesung, Mi. 15.2.2006 
        Triangulierte Graphen
           Cliquenseparatoren
           Simpliziale Knoten
           Perfekte Eliminationsordnung
           Baumdarstellung
32. Vorlesung, Fr. 17.2.2006 
           Triangulierte Graphen sind perfekt
           Perfectly orderable graphs


Zurück zur Vorlesungsseite.