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 [Vertr. Felix Schröder]
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 [Vertr. Felix Schröder]
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.