Inhaltsverzeichnis
Graphentheorie
Wintersemester 2017/18
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 .
1. Vorlesung, Mo. 16.10.2017
Anstoß: 3 Probleme
Einleitung
Grundsätzliche Definitionen
Isomorphie und Subgraphen
Einige wichtige Graphen
Anwendunggebiete
Matrizen und Graphen
2. Vorlesung, Di. 17.10.2017
Lösung: Problem I
Lösung: Problem II
Geometrische Graphen ohne disjunkte Kanten
Topologische Graphen, Thrackles
Lösung: Problem III
Starre Gitter: Parallelklassen - Zusammenhang
3. Vorlesung, Mo. 23.10.2017
Gradfolgen
Charakterisierung von Havel und Hakimi
Der Übergangsgraph der 2-Switches
Wege und Kreise
Zusammenhang
Knotenzusammenhang
4. Vorlesung, Di. 24.10.2017
Kantenzusammenhang
Κ(G) vs Κ'(G)
Der Satz von Menger
u-v Separatoren
allgemeine Separatoren
8 Varianten des Satzes von Menger
weitere Dualitätssätze
(König-Egervary; Ford-Fulkerson)
5. Vorlesung, Mo. 30.10.2017
Bäume und Wälder
Charakterisierungen von Bäumen
Aufspannende Bäume
Algorithmische Existenzbeweise
Exkurs: Matroide
Bridg-It
Spiel und Gewinnstrategie
6. Vorlesung, Mo. 6.11.2017
Satz von Cayley
Beweis 1. Prüfer,
Beweis 2. Clarke,
Beweis 3. Joyal
7. Vorlesung, Di. 7.11.2017
F2 Vektorräume eines Graphen
Knoten- und Kantenraum
Schnitt- und Zykelraum
F2 Orthogonalität
Fundamentalbasen
Lights-on; eine Anwendung von F2 Vektorräumen
8. Vorlesung, Mo. 13.11.2017
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
9. Vorlesung, Di. 14.11.2017
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, Mo. 20.11.2017
Elektrische Flüsse
Ohmsches und Kirchhoffsche Gesetze
Potenziale
Satz von Kirchhoff: E-Fluss duch Zählen von Bäumen
11. Vorlesung, Di. 21.11.2017
Planare Graphen
Zeichnungen, Kreuzungen und Jordanscher Kurvensatz
K5 und K3,3 sind nicht planar
Duale Graphen
2 Beweise der Euler Formel (duale Bäume,Noahs Arche)
12. Vorlesung, Mo. 27.11.2017
Euler Formel und Winkelsummen
Folgerungen aus der Euler Formel
5-Farbensatz
Das "Art Gallery Problem"
Matroide
Unabhängigkeitsaxiome
Beispiele von Matroiden
13. Vorlesung, Di. 28.11.2017
Begriffe und alternative Axiomensysteme
Der Greedy Algorithmus für Matroide
Optimierung im Durchschnitt von Matroiden
Duale Matroide
Lineare Matroide
Darstellungssatz für duale Matroide
14. Vorlesung, Mo. 4.12.2017
Ein Beispiel aus der Pappus Konfiguration
Minoren von Matroiden
Klassifikationssätze
Planare Graphen
Sätze von Kuratowski und Wagner
15. Vorlesung, Di. 5.12.2017
Beweis Kuratowski
Satz von Whitney (Eindeutige Darstellung)
Satz von Hanani-Tutte (independent odd crossings)
16. Vorlesung, Mo. 11.12.2017
Beweis Hanani-Tutte
Gittereinbettungen
Schnyder-Woods
Die Ti sind Bäume
17. Vorlesung, Di. 12.12.2017
Regionen
Zählen von Flächen in Regionen
Das leere Dreieck einer Kante
Kreuzungsfreiheit
18. Vorlesung, Mo. 18.12.2017
Satz von Koebe
Kreispackungsdarstellung von Triangulierungen
Orthogonale Kreispackungsdarstellungen
19. Vorlesung, Di. 19.12.2017
Separatortheorem für planare Graphen
Beweis über Kreispackungsdarstellungen
Centerpoints
Kappenflächen
Existenz aus probabilistischer Analyse
20. Vorlesung, Mo. 8.1.2018
Die Parameter α, ω, χ und Θ
Extremale Graphentheorie
Satz von Mantel
Satz von Turán
Beweis 1: Mit Optimierung
21. Vorlesung, Di. 9.1.2018
Beweis 2: Kurze Induktion
Beweis 3: Mit dem drei Knoten Lemma
Anzahl Dreiecke in dichten Graphen
ex(n,H) und Erdös-Stone
ex(n,C4) = O(n3/2)
22. Vorlesung, Mo. 15.1.2018
Schranken für α
Die Wei Ungleichung
Turan aus Wei
Beweis. Zufällige Permutation
Beweis. Über Algo MIN
Ramsey Theorie
Monotone Teilfolgen (Erdös Szekeres)
23. Vorlesung, Di. 16.1.2018
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)
24. Vorlesung, Mo. 22.1.2018
Färbungen
Untere Schranken: ω und n/α
Burling Graphen (Quelle: burling.pdf)
Greedy Färbungen und k-Degeneriertheit
25. Vorlesung, Di. 23.1.2018
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
26. Vorlesung, Mo. 29.1.2018
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
27. Vorlesung, Di. 30.1.2018
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)
(Notiz: allgemeine Lage)
28. Vorlesung, Mo. 5.2.2018
Listenfärbungen
Listenfärbungen bipartiter Graphen
Zwei Beispielfamilien mit χL > k
log(n) als obere Schranke
(randomisiert|derandomisiert)
Listenfärbung planarer Graphen
Thomassen χL <= 5
Voigt/Mirzakhani χL >= 5
29. Vorlesung, Di. 6.2.2018
Perfekte Graphen
4 zentrale Klassen perfekter Graphen
Die Berge Vermutungen
Chordale Graphen
Cliquenseparatoren und simpliziale Knoten
Perfekte Eliminationsordnung
30. Vorlesung, Mo. 12.2.2018
Baumdarstellung
Baumzerlegungen und Baumweite
Baumzerlegungen und chordale Graphen
Baumweite und Robber&Cops
31. Vorlesung, Di. 13.2.2018
Algorithmische Anwendungen
Ein FPT Alg. für 3-Färbbarkeit
Berechnen von Baumzerlegungen und Satz von Courcelle
Baumweite und Minoren
Das Graph-Minor-Theorem von Robertson und Seymour
Wohlquasiordnungen
Zurück zur
Vorlesungsseite.