Graphentheorie Simon

Buffl

Stapelfeld

by Simon M.

Grapheninvariante

Eine Funktion, die Graphen als Argumente hat und isomorphen Graphen gleiche Werte zuordnet

epsilon(G)

|E| / |V|

Kantenzahl durch Eckenzahl

Beziehung epsilon(G) und Durchschnittsgrad

epsilon(G) = 1/2 d(G)

Proposition 0.2.2: Beziehung Minimalgrad, Epsilon

Taillenweite, Umfang

g(G): Länge eines kürzesten Kreises (unendlich, falls kein Kreis)

U(G): Länge eines längsten Kreises (Null, falls kein Kreis)

Zusammenhang Minimalgrad und längste Wege/Kreise

Durchmesser

diam(G): Der größte Abstand zweier Ecken in G, die geringste Länge eines x-y-Weges

zentrale Ecke, Radius

Zusammenhang mit Durchmesser

zentrale Ecke: ihr größter Abstand von anderen Ecken ist möglichst klein. Er heißt Radius: rad(G).

Es gilt rad(G) <= diam(G) <= 2rad(G)

Kantenzug

Nicht leere Folge v0e0v1e1…e(k-1)vk von abwechselnd Ecken und Kanten aus G mit e_i = {v_i, v_i+1} für alle i<k

zusammenhängend

G ist nicht leer,

für je zwei Ecken x, y exisitert ein x-y-Weg

Teilung

Das ungeordnete Paar {A, B}, wenn AuB = V und A von B durch AnB getrennt wird.

Echte Teilung, falls weder A\B noch B\A leer ist

k-zusammenhängend

wenn |G| > k und G-X für jede Eckenmenge X der Mächtigkeit < k zusammenhängend ist.

Korrelation von Minimalgrad, k-Zusammenhang, l-Kantenzusammenhang

Mader (1972)

Jeder Graph mit d(G) >= 4k hat einen (k+1)-zusammenhängenden Teilgraphen H

Äquivalenzen Bäume

0) T ist ein Baum

1) T ist zusammenhängend und kreislos

2) Zwischen je zwei Ecken enthält T genau einen Weg

3) ist minimal zusammenhängend

4) T ist maximal kreislos

Sehnen eines Spannbaums

Baumordnung, Abschluss nach unten, Abschluss nach oben

normaler Spannbaum

Lemma 0.5.5: Trennung zweier Ecken durch Abschluss nach unten in Baumordnung

Proposition 0.5.6.: NST-Existenz

Notation r-partite Graphen

Bezeichnungen topologische Minoren

Bezeichnungen Minoren

Äquivalenz: X ist genau dann Minor von Y, wenn…

Proposition 0.7.3: Unterschied top. Minoren und Minoren

Eulerzug, Eulerkreis, Eulergraph

Eulerzug: eulerscher Kantenzug, nicht geschlossen

Eulerkreis: eulerscher Kantenzug, geschlossen

Eulergraph: eulerscher Graph

Definition Paarung

Definition k-Faktor

alternierender Weg, Verbesserungsweg

Definition Eckenüberdeckung

Satz 1.1.1 (König 1931)

Satz 1.1.2: Heiratssatz (Hall 1935)

Satz 1.1.4 (Gale & Shapley 1962)

Präferenzliste, stabile Paarung

Korollar 1.1.3: Eigenschaft regulärer bipartiter Graph

Jeder reguläre bipartite Graph hat einen 1-Faktor oder ist kantenlos

Präferenzlisten: interessant und zufrieden

Korollar 1.1.5: Eckensplitting, regulärer Graph

Jeder reguläre Graph geraden Grades > 0 hat einen 2-Faktor.

Satz 1.2.1 (Tutte 1947)

schlechte Menge

gerichteter Weg, ter(P), Wegüberdeckung

Satz 1.5.1 (Gallai & Milgram 1960)

Proposition 2.2.1: Ohrenkonstruktion

Definition Block

Lemma 2.2.1 und Lemma 2.2.2: 3-Zusammenhang

Satz 2.2.3 (Tutte 1966): 3-Zusammenhang, Unterdrückung

Satz 2.2.5 (Tutte 1961): Kontraktion

Satz 2.3.1 (Menger 1927)

Definition Fächer, Satz Fächermenger, Beweisskizze

Korollar 2.3.5: Menger für zwei Ecken in G, Beweisskizze

2.3.6: Globaler Menger

Satz 3.1.1 Jordanscher Kurvensatz für Polygone

Definition ebener Graph

Proposition 2.3.6: Gebiete in einem 2-zsh., ebenen Graphen

Proposition 3.2.7: Gebiete in einem 3-zsh., ebenen Graphen

Proposition 3.2.8: Maximaler ebener Graph, ebener Dreiecksgraph

Ein ebener Graph der Ordnung >= 3 ist genau dann maximal eben, wenn er ein ebener Dreiecksgraph ist.

Satz 3.2.9: Eulersche Polyederformel für die Ebene

Korollar 3.2.10: Ecken und Kanten in ebenen Dreiecksgraphen

Lemma 3.4.2: Minor und topologischer Minor für K^5 und K_3,3

Lemma 3.4.3. Kuratowski füt 3-zsh. Graphen

Lemma 3.4.5 Wie erhalten wir Kuratowski für weniger als 3-zsh.?

Satz 3.4.6 (Kuratowski 1930, Wagner 1937)

Zusammenhang (ecken)chromatische Zahl und kantenchromatische Zahl:

Kantengraph

chi ‘ (G) = chi(L(G))

Die Bestimmung der kantenchromatischen Zahl ist also ein Spezialfall der Bestimmung der eckenchromatischen Zahl.

Satz 4.1.3 (Grötzsch 1959)

Jeder ebene Graph, der kein Dreieck enthält, ist 3-färbbar.

Proposition 4.2.1: Abschätzung chromatische Zahl durch Kantenanzahl

Greedy-Algorithmus: Funktionsweise

Ausgehend von einer festen Eckenaufzählung färbe die Ecken v_i nacheinander jeweils mit der kleinstmöglichen Farben, also mit der kleinsten Farbe, die kein Nachbar v_j von v_i mit j<i bereits trägt.

Somit ist G stets mit Delta(G) + 1 vielen Farben färbbar.

Reihenzahl col(G)

Proposition 4.2.2

Greedy in schlauerer Eckenaufzählung: Wir wählen v_n als eine Ecke mit minimalem Grad in G, als v_n-1 eine Ecke mit minimalem Grad in G - v_n und so weiter.

v_i hat dann jeweils minimalen Grad in G[v1, …, vi].

Lemma 4.2.3: Untergraphen von k-chromatischen Graphen

Jeder k-chromatische Graph hat einen k-chromatischen Untergraphen mit Minimalgrad mindestens k-1

Satz 4.2.4 (Brooks 1941)

Satz 4.2.5 (Erdös 1959)

Implikationen des Satzes von Erdös (schlecht greifbarer Charakter der chromatischen Zahl)

k-konstruierbare Graphen

(inkl. Erklärung, warum die chromatische Zahl der konstruierten Graphen größer gleich die der ursprünglichen ist)

Satz 4.2.6 (Hajós 1961)

Proposition 4.3.1 (König 1916)

Satz 4.3.2 (Vizing 1964)

Definitionen Listenfärbungen, offensichtliche Abschätzungen

Satz 4.4.1 (Alon 1993)

Satz 4.4.2 (Thomassen 1994)

Jeder ebene Graph ist 5-listenfärbbar

Listenfärbungsvermutung

Kern einer Eckenmenge D (zum Beispiel D = V)

Satz 4.4.4 (Galvin 1995)

Flüsse: Mengen orientierter Kanten in G

f(X,Y)

Definition Rundfluss

Proposition 5.1.1 und Korollar 5.1.2:

Konsequenzen der Definition von Rundflüssen

Netzwerk, Kapazitätsfunktion

Definition Fluss

Schnitt in einem Netzwerk, Kapazität des Schnittes

Proposition 5.2.1: Schnitte in N

Definition: Stärke von f

Satz 5.2.2: max-flow min-cut theorem (Ford & Fulkerson 1956)

magere Graphen, dichte Graphen

Kantendichte

Graphen, deren Kantenzahl größenordnungsmäßig höchstens linear in ihrer Eckenzahl ist, heißen mager.

Graphen, deren Kantenzahl größenordnungsmäßig quadratisch in der Anzahl ihrer Ecken ist, nennt man dicht.

Die Zahl ||G|| / (|G| über 2), die tatsächlich vorhandene Anteil seiner potentiellen Kanten, ist die Kantendichte von G.

Lemma 2.5.1: Wie erzwingen wir jeden gewünschten Minor?

extremal

ex(n, H)

Ein Graph mit maximaler und größtmöglicher Kantenzahl mit der Eigenschaft “H ist nicht Teilgraph von G”. Wir bezeichnen seine Kantenzahl mit ex(n, H).

Extremalität ist allgemein eine stärkere Eigenschaft als Kantenmaximalität, weil sie “größtmöglich” inkludiert.

Turángraph

Satz 6.1.1 (Turán 1941)

Verdopplung einer Ecke v in G

Abschätzung für t_r-1(n)

Satz 6.1.2 (Erdös & Stone 1946)

Korollar 6.1.3: Zusammenhang von chromatischer Zahl und ex(n, H)

Proposition 6.2.1: Durchschnittsgrad erzwingt K^r-Minor

Satz 6.2.4: Senkung der Schranke aus Proposition 6.2.1

Proposition 6.2.2: Durchschnittsgrad erzwingt K^r als topologischen Minor.

Satz 6.2.3: Senkung der Schranke aus Proposition 6.2.2

Hadwiger-Vermutung

Proposition 6.3.1: Äquivalenz zu “kantenmaximal ohne K^4-Minor”

Satz 6.3.4 (Wagner 1937)

Hieraus wird dann die Hadwiger-Vermutung für r=5 aus dem Vierfarbensatz hergeleitet (also deren Äquivalenz damit).

Satz 7.1.1 (Ramsey 1930)

Ramseyzahl

Abschätzung Ramseyzahl

Lemma 7.1.3 (Königs Unendlichkeitslemma)

Ramseyzahl r(l, m)

Hamiltonkreis

Hamiltonweg

hamiltonsch

Satz 8.1.1 (Dirac 1952)

Trenner-Eigenschaft Hamiltonkreise

Proposition 8.1.2: Wie erzwingen wir einen Hamiltonkreis durch die Beziehung zweier Invarianten zueinander?

Satz 8.1.3 (Asratian & Khachatrian 1990)

Gradsequenz, hamiltonsches Tupel, punktweise größer

Satz 8.2.1 (Chvátal 1972)

Weg-hamiltonisch,

Korollar 8.2.2: Satz 8.2.1 (Chvátal 1972) für Hamilton-Wege

p und q

Elementarereignis {G_0}

Lemma 9.1.2: Wahrscheinlichkeit, dass G in G(n, p) eine unabhängige Eckenmenge der Mächtigkeit k enthält

Zusammenhang von Wahrscheinlichkeit für Cliquenzahl und Unabhängigkeitszahl mit der Ramsey-Zahl

Satz 9.1.3 (Erdös 1947)

Zufallsgröße, Erwartungswert

Der Erwartungswert ist linear: E(X+Y) = E(X) + E(Y) und E(kX) = kE(X)

Erwartete Anzahl von Kreisen der Länge k in einem

Graphen G in G(n, p)

Lemma 9.1.5: Markov-Ungleichung

Korollar 9.2.3: Erdös für Zusammenhang, Durchschnittsgrad, Minimalgrad

Lemma 4.2.3: chi treibt Minimalgrad (indirekt durch Teilgraph) nach oben

Minimalgrad treibt Durchschnittsgrad nach oben

Satz 0.4.3 (Mader 1972) Durchschnittsgrad treibt Zusammenhang nach oben

Grapheneigenschaft, fast alle, fast kein

Proposition 9.3.1: Wahrscheinlichkeit für H Untergraph von H für n gegen unendlich

Anmerkung aus dem ∞-Kapitel:

Die Wahrscheinlichkeit, dass ein zufällig generierter Graph auf ∞ vielen Ecken einen Kreis enhält, ist wegen des Rado-Graphen =1. Trotzdem gibt es Graphen, z.B. unendliche Bäume, die keine Kreise enthalten.

Eigenschaft P_i,j, damit verbunden: Lemma 9.3.2

Korollar 9.3.3: k-Zusammenhang für n gegen unendlich

Satz von Cantor-Bernstein

∞-zsh.

Satz dazu mit topologischem Minor

Wir können den TK^∞ sogar als aufspannenden Teilgraphen von G konstruieren, indem wir uns bei der im Beweis verwendeten Konstruktion an einer festen Eckenaufzählung entlanghangeln. Dann werden alle Ecken letztlich in den TK^∞ eingebaut.

kantendisjunkte Spannbäume in unendlichen Graphen

Ein abzählbarer ∞-kantenzsh. Graph hat immer ∞ viele kantendisjunkte Spannbäume

∞-kantenzsh.

Äquivalenz dazu

Sei Y beliebige Kantenmenge. G ist ∞-kantenzsh, falls G-Y für jedes endliche Y zusammenhängend ist.

∞-kantenzsh. <=> zwischen je zwei Ecken existieren ∞ viele kantendisjunkte Wege

∞-zsh. und Taillenweite

lokal finit

Strahl

Doppelstrahl

Satz ∞.4.2 (Aharoni & Berger 2009)

Satz ∞.1.3 (de Bruijn & Erdös 1951)

unfreundliche Bipartition

unfeundliche-Partition-Vermutung

Wir nennen eine Bipartition der Eckenmenge eines Graphen unfreundlich, falls jede Ecke mindestens so viele Nachbarn in der anderen Klasse hat, wie in der eigenen.

Vermutung: Jeder abzählbare Graph hat eine unfreundliche Eckenpartition

Die Vermutung ist gezeigt für endliche und lokal endliche Graphen;

sie ist widerlegt für überabzählbare Graphen.

universaler Graph