Transcript
Graphentheorie 2 – Dr. Schaudt
0. Grundlegende Definitionen • •
Definitionen: Graph, Multigraph, zugrundeliegender Graph, Orientierung, stabil, k-färbbar, chromatische Zahl, Pfad/Weg, Kreis, zusammenhängend Satz 0.1: Bipartit ⟷ alle Kreise sind gerade Beweis
1. Gerichtete Graphen 1.1 Wege in gerichteten Graphen • • • •
•
Definitionen: gerichteter Pfad/Weg/Kreis, erreichbar, starke ZHK, stark zusammenhängend, Turnier, Vorgänger, Nachfolger Satz 1.1: G enthält einen ger. Weg der Länge x(G’)-1 Beweis Korollar 1.2: Turniere besitzen einen Hamiltonweg Beweis Satz 1.3: G hat eine stabile Menge X, sodass jeder Knoten über zwei Knoten erreicht Beweis werden kann Korollar 1.4: Jedes Turnier besitzt eine ‚graue Eminenz’ Beweis
1.2 Kreise in gerichteten Graphen • • • •
Definitionen: Panzyklizität Satz 1.5: Jedes stark-zusammenhängende Turnier ist panzyklisch (und besitzt daher einen Hamiltonkreis) Satz 1.7: Das Hamiltonkreis/-Weg-Entscheidungsproblem ist NP-vollständig Satz 1.9: Hat jeder Knoten n/2 Vorgänger & n/2 Nachfolger, so ist der Graph hamiltonsch
Beweis Beweis Beweis
1.3 Anwendungsbeispiele • • • • • • • •
Beispiele: Job sequencing, Einbahnstraßensysteme Definitionen: (starker) k-Kantenzusammenhang, Adjazenzmatrix, Abstand, Durchmesser, primitive Matrix Satz 1.10: Es gibt eine stark zsh. Orientierung, wenn G 2-zusammenhängend ist Beweis Satz von Nash-Williams: Ein k-kanten-stark-zsh. Graph hat eine k-kanten-stark-zsh. Orientierung Satz & Korollar 1.12/1.13: T stark zmh. ⟷ Adjazenzmatrix primitiv Beweis Satz von Perron-Frobenius: Für jede primitive Matrix existiert eindeutiges Eigenwert/Eigenvektorpaar, sodass die Rangfolgenerstellung konvergiert Verfahren zur Rangfolgenerstellung
2. Flüsse und Zirkulationen 2.1 Gruppenwertige Flüsse • • • • •
Definitionen: Fluss, Bilanz, H-wertiger Fluss, H-Fluss, k-Fluss, Flusszahl φ, Fundamentalkreis Satz & Korollar 2.1/2.2 (Tutte): Jeder Graph besitzt ein Flusspolynom, welches nur Beweis von der Ordnung der Gruppe H abhängt Lemma & Satz 2.3/2.4: G hat einen k-Fluss ⟷ G hat einen Z_k-Fluss Beweis Bemerkung: Orientierung egal! Satz 2.5: Graphen ⟷ Flüsse Beweis
2.2 Flüsse & Färbungen •
Definitionen: planar, dualer Graph G*, Baumordnung, normaler Spannbaum
• •
Satz 2.6: Für planare Graphen gilt: x(G)= φ(G*) Lemma 2.7: Zsh. Multigraphen haben zu jeder Wurzel einen normalen Spannbaum
Beweis Beweis
2.3 Flussvermutungen • • • • • • • •
Definitionen: Minor, Snark Satz 2.8: Jeder Multigraph ohne Schnittkante hat einen k-Fluss, für ein k Vermutung 2.9: Für alle Graphen reicht k≤5 Vermutung 2.10: Ohne einen Petersen-Minor reicht sogar k≤4 Bemerkung: Vermutung 2 = Snark-Satz impliziert den Vier-Farben-Satz Vermutung 2.11: Ohne Schnitt aus 1 oder 3 Kanten reicht sogar k≤3 Satz von Grötzsch: Jeder planare Graph ohne Dreieck ist 3-färbbar Satz 2.13 (Seymour): Jeder Graph ohne Schnittkante hat einen 6-Fluss
Beweis
Beweis
Beweis
3. Graphenfärbungen 3.1 Kritische Graphen • • • • • • •
Definitionen: k-kritisch, (Knoten-)Schnittmenge, (u,v)-Komponente vom Typ 1/2 Satz 3.1: Ist G k-kritisch gilt δ(G)≥k-1 Korollar 3.2: In G k-chromatisch gibt es mind. k Knoten mit Grad mind. k-1 Satz 3.3: Jeder k-kritische Graph ist (k-1)-kantenzsmh. Satz 3.4: In einem kritischen Graphen gibt es keine Schnittmenge, die eine Clique ist Satz 3.5: Hat ein k-kritischer Graph eine Schnittmenge (u,v), so gibt es genau eine Typ1- und eine Typ2-(u,v)-Komponente Korollar 3.6: G k-kritisch mit Schnittmenge u,v dann gilt d(u)+d(v) ≥ 3k-5
Beweis Beweis Beweis Beweis Beweis Beweis
3.2 Die Vermutung von Hadwiger • • • •
Vermutung (Hadwiger): Ein Graph mit x(G)=k enthält einen K_k als Minor Bemerkung: Der Fall k=5 impliziert den Vier-Farben-Satz Satz 3.8: Die Vermutung gilt für k=1,2,3,4 Ex-Vermutung von Hajós: Wie Hadwiger nur mit topol. Minoren
Beweis Beweis
3.3 Färbungen von Graphen auf Flächen • • • • • •
Definitionen: Fläche, geschlossene Fläche, zusammenhängende Summe, Triangulierung, EulerCharakteristik, chromatische Zahl einer Fläche Satz: Jede geschlossene Fläche ist homöomorph zu S^2, einer Summe von T^2 oder einer Summe von RP^2 Satz von Euler-Poincaré: Für G eingebettet auf F gilt m≤3n-3x Satz 3.11: Die chromatische Zahl eines Graphen eingebettet auf F ist beschränkt Beweis durch eine Zahl abhängig von der Euler-Charakteristik Satz 3.12: Sei x≤0, dann ist jeder h-kritscher Graph auf F gleich K_h Beweis Satz 3.13: Die chromatische Zahl von T^2 ist 7 und die von RP^2+RP^2 ist 6. Beweis
3.4 Listenfärbungen • • • • • • • •
Definitionen: k-listenfärbbar, Listenchromatische Zahl, fast-trianguliert, Listenchromatscher Index, Kern, kern-perfekt Bemerkung: Es gibt bipartite Graphen mit beliebig hoher listenchromatischer Zahl Satz 3.15: Hat G einen sehr hohen Durchschnittsgrad, ist auch seine listenchromatische Zahl hoch Satz 3.16 & Lemma 3.17: Jeder planare Graph ist 5-listenfärbbar Beweis Vermutung 3.18: Der listenchromatische Index entspricht immer der listenchromatischen Zahl Satz 3.19: Für bipartite Graphen gilt die Vermutung Beweis Lemma 3.20: Existiert eine bestimmte Orientierung von G, so gibt es eine Beweis Listenfärbung Satz von Gale & Shapley 3.21: Jeder bipartite Graph mit Präferenzlisten besitzt ein stabiles Matching
Fragen: • Satz 3.5: Warum kann es nicht mehr als 2 Komponenten geben?
