Inhaltsverzeichnis

Graphentheorie

Wintersemester 2019/20
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.2019

    Anstoß: 3 Probleme      
    Einleitung
       Grundsätzliche Definitionen
       Isomorphie und Subgraphen
       Einige wichtige Graphen
       Anwendunggebiete
       Matrizen und Graphen
2. Vorlesung, Mi. 16.10.2019
    Lösung: Problem I
       Kreisfreie Graphen
    Lösung: Problem II
       Geometrische Graphen ohne disjunkte Kanten
       Topologische Graphen, Thrackles
    Lösung: Problem III
       Starre Gitter: Parallelklassen - Zusammenhang
3. Vorlesung, Di. 22.10.2019
      Gradfolgen
         Charakterisierung von Havel und Hakimi
         Der Übergangsgraph der 2-Switches
	 Satz von Erdös-Gallai
      Wege und Kreise
4. Vorlesung, Mi. 23.10.2019
         Distanzen
       Zusammenhang
         Knotenzusammenhang
         Kantenzusammenhang
         Κ(G) vs Κ'(G)
         Der Satz von Menger
           u-v Separatoren
5. Vorlesung, Di. 29.10.2019

allgemeine Separatoren
         8 Varianten des Satzes von Menger
           weitere Dualitätssätze
	   (König-Egervary; Ford-Fulkerson)
     Bäume und Wälder
        Charakterisierungen von Bäumen               
        Aufspannende Bäume
           Algorithmische Existenzbeweise
 
6. Vorlesung, Mi. 30.10.2019
        Exkurs: Matroide
        Bridg-It
           Spiel und Gewinnstrategie
        Satz von Cayley 
        Beweis 1. Prüfer,
7. Vorlesung, Di. 5.11.2019
 
	Beweis 2. Clarke,
	Beweis 3. Joyal
        F2 Vektorräume eines Graphen
           Knoten- und Kantenraum
8. Vorlesung, Mi. 6.11.2019
           Schnitt- und Zyklenraum
           F2 Orthogonalität
           Fundamentalbasen   
         Lights-on; eine Anwendung von F2 Vektorräumen 
9. Vorlesung, Di. 12.11.2019
R Vektorräume gerichteter Graphen
           Zirkulationen und Schnitte
       Matrix Baum Theorem
           Matrix Baum Theorem für gerichtete Graphen
           Arboreszenzen 
           Reduktion auf Graphen mit outdeg(v) = 1
        Euler Kreise
10. Vorlesung, Mi. 13.11.2019
        Euler Kreise
        Memory Wheels 
           Der deBruijn Graph Bn(m)
        BEST Theorem 
           Zählen von Euler-Kreisen in gerichtete Graphen
11. Vorlesung, Di. 19.11.2019 [Vertr. Felix Schröder]
           Eigenwertversion von Matrix Baum
           Eigenwerte von Bn(m)          
        Eigenwerte von Adjazenzmatrizen    
12. Vorlesung, Mi. 20.11.2019 [Vertr. Felix Schröder]
          Memory wheels und Schieberegisterfolgen
	  Einschub: Körpererweiterungen
	            Satz vom primitiven Element
		    Polynome und die Abb. x -> x^p
13. Vorlesung, Di. 26.11.2019
        Elektrische Flüsse
            Ohmsches und Kirchhoffsche Gesetze
            Potenziale
	    Satz von Kirchhoff: E-Fluss duch Zählen von Bäumen
   Planare Graphen
        Zeichnungen, Kreuzungen und Jordanscher Kurvensatz
        K5 und K3,3 sind nicht planar
14. Vorlesung, Mi. 27.11.2019
         Duale Graphen
         Beweise der Euler Formel
	    duale Bäume
	    Induktion (Noahs Arche)
	    Winkelsummen 
	 Folgerungen aus der Euler Formel
15. Vorlesung, Di. 3.12.2019
 	 5-Farbensatz
         Das "Art Gallery Problem"
    Matroide
       Unabhängigkeitsaxiome
       Der Greedy Algorithmus für Matroide
       Duale Matroide
16. Vorlesung, Mi. 4.12.2019
      Lineare Matroide
        Darstellungssatz für duale Matroide
        Ein Beispiel aus der Pappus Konfiguration
      Minoren von Matroiden 
      Klassifikationssätze
17. Vorlesung, Di. 10.12.2019
   Planare Graphen
      Sätze von Kuratowski und Wagner
           Beweis Kuratowski
18. Vorlesung, Mi. 11.12.2019
     Satz von Whitney (Eindeutige Darstellung)
     Satz von Koebe
       Kreispackungsdarstellung von Triangulierungen
19. Vorlesung, Di. 17.12.2019
       Orthogonale Kreispackungsdarstellungen
     Separatortheorem für planare Graphen
       Beweis über Kreispackungsdarstellungen
         Centerpoints
         Kappenflächen
         Existenz aus probabilistischer Analyse
20. Vorlesung, Mi. 18.12.2020
      Die Parameter α, ω, χ und Θ
  Extremale Graphentheorie          
      Satz von Mantel
      Satz von Turán
         Beweis 1: Mit Optimierung
         Beweis 2: Kurze Induktion
         Beweis 3: Mit dem drei Knoten Lemma 
         Beweis 4: Mit Wei Ungl. und Cauchy-Schwarz
      Anzahl Dreiecke in dichten Graphen
 
21. Vorlesung, Di. 7.1.2020
     ex(n,H)
     Die Sätze von Erdös-Stone und Erdös-Simonovits
     ex(n,C4) = O(n3/2)
   Schranken für α
       Die Wei Ungleichung
       Beweis. Zufällige Permutation
22. Vorlesung, Mi. 8.1.2020
       Beweis. Über Algo MAX
       Beweis. Über Algo MIN
   Ramsey Theorie
       Monotone Teilfolgen (Erdös Szekeres) 
    Graphen-Ramsey
        Beweis durch induzierte Färbung
23. Vorlesung, Di. 14.1.2020
        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)
            N(n) < R3(n,n)
24. Vorlesung, Mi. 15.1.2020
         CAPs und CUPs in Punktmengen
            Die klassische Erdös Szekeres Schranke
      Hamilton Kreise
        Hinreichende Bedingungen
           Satz von Dirac
           Satz von Chvatal-Erdös
        Notwendige Bedingung
           Hamiltonscher Abschluss
25. Vorlesung, Di. 21.1.2020
Färbungen
       Untere Schranken: ω und n/α
          Mycielski Graph
       Greedy Färbungen und k-Degeneriertheit
26. Vorlesung, Mi. 22.1.2020
       Färbungen und Orientierungen
         Partielle Ordnungen, Ketten und Antiketten
         Satz von Gallai-Roy
      Satz von Brooks
      Die Vermutungen von Hadwiger und Hajos
27. Vorlesung, Di. 28.1.2020
  Fraktionale Färbungen
  (Buch: Fractional Graph Theory von Scheinerman und Ullman)
        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, Mi. 29.1.2020
        Zur Ganzzahligkeitslücke: χ <= (1+ln α)χf
        Färbungen und Homomorphismen
        Kneser Graphen
        Fraktionale Färbungszahl von Kneser Graphen
        Färbungszahl von Kneser Graphen (ein topologisches Argument)
29. Vorlesung, Di. 4.2.2020
    Perfekte Graphen  
      4 zentrale Klassen perfekter Graphen      
      Die Berge Vermutungen 
      Chordale Graphen
        Cliquenseparatoren und simpliziale Knoten
        Perfekte Eliminationsordnung
	Baumdarstellungen
 
30. Vorlesung, Mi. 5.2.2020
    Das Polytop der unabhängigen Mengen STAB(G)
        Gültige Ungleichungen ESTAB und QSTAB
	Schwacher Perfekte-Graphen-Satz
        Optimierung über STAB und QSTAB
31. Vorlesung, Di. 11.2.2020
    Baumzerlegungen und Baumweite 
        Baumzerlegungen und chordale Graphen
        Baumweite und Robber&Cops 
 

Zurück zur Vorlesungsseite.