Graphentheorie Lukas

Buffl

Stapelfeld

by Simon M.

Beziehung epsilon(G) und Durchschnittsgrad hhh

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

Durchmesser

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

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)

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

Proposition 0.2.2: Beziehung Minimalgrad, Epsilon

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

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)

Mader (1972)

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

epsilon(G)

|E| / |V|

Kantenzahl durch Eckenzahl

Baumordnung, Abschluss nach unten, Abschluss nach oben

k-zusammenhängend

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

Ä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

Grapheninvariante

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

zusammenhängend

G ist nicht leer,

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

Bezeichnungen topologische Minoren

Korrelation von Minimalgrad, k-Zusammenhang, l-Kantenzusammenhang

Notation r-partite Graphen

Satz 1.1.2: Heiratssatz (Hall 1935)

Präferenzliste, stabile Paarung

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

Definition Eckenüberdeckung

Satz 1.5.1 (Gallai & Milgram 1960)

Korollar 1.1.3: Eigenschaft regulärer bipartiter Graph

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

Eulerzug, Eulerkreis, Eulergraph

Eulerzug: eulerscher Kantenzug, nicht geschlossen

Eulerkreis: eulerscher Kantenzug, geschlossen

Eulergraph: eulerscher Graph

Zusammenhang Minimalgrad und längste Wege/Kreise

Präferenzlisten: interessant und zufrieden

Satz 1.2.1 (Tutte 1947)

schlechte Menge

gerichteter Weg, ter(P), Wegüberdeckung

Definition Paarung

Korollar 1.1.5: Eckensplitting, regulärer Graph

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

Proposition 0.7.3: Unterschied top. Minoren und Minoren

Satz 1.1.1 (König 1931)

Definition Block

Satz 2.2.5 (Tutte 1961): Kontraktion

Lemma 2.2.1 und Lemma 2.2.2: 3-Zusammenhang

2.3.6: Globaler Menger

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

alternierender Weg, Verbesserungsweg

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

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

Proposition 0.5.6.: NST-Existenz

Satz 3.1.1 Jordanscher Kurvensatz für Polygone

Definition Fächer, Satz Fächermenger, Beweisskizze

Definition ebener Graph

Satz 3.2.9: Eulersche Polyederformel für die Ebene

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.

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].

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

Definitionen Listenfärbungen, offensichtliche Abschätzungen

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

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)

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

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

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 2.3.1 (Menger 1927)

Satz 4.3.2 (Vizing 1964)

Proposition 4.3.1 (König 1916)

Proposition 2.2.1: Ohrenkonstruktion

Satz 3.4.6 (Kuratowski 1930, Wagner 1937)

Satz 1.1.4 (Gale & Shapley 1962)

Lemma 4.2.3: Untergraphen von k-chromatischen Graphen

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

Netzwerk, Kapazitätsfunktion

Definition Fluss

Flüsse: Mengen orientierter Kanten in G

Kern einer Eckenmenge D (zum Beispiel D = V)

Schnitt in einem Netzwerk, Kapazität des Schnittes

Proposition 5.2.1: Schnitte in N

Definition: Stärke von f

Satz 4.4.1 (Alon 1993)

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.

Listenfärbungsvermutung

Korollar 3.2.10: Ecken und Kanten in ebenen Dreiecksgraphen

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.

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.

f(X,Y)

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

Turángraph

Satz 4.2.4 (Brooks 1941)

Bezeichnungen Minoren

Satz 4.2.5 (Erdös 1959)

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

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

normaler Spannbaum

Satz 4.4.2 (Thomassen 1994)

Jeder ebene Graph ist 5-listenfärbbar

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

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).

Lemma 7.1.3 (Königs Unendlichkeitslemma)

Ramseyzahl r(l, m)

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

Satz 7.1.1 (Ramsey 1930)

Ramseyzahl

Abschätzung Ramseyzahl

Gradsequenz, hamiltonsches Tupel, punktweise größer

Satz 8.1.1 (Dirac 1952)

Weg-hamiltonisch,

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

Trenner-Eigenschaft Hamiltonkreise

Satz 8.1.3 (Asratian & Khachatrian 1990)

Satz 8.2.1 (Chvátal 1972)

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.

Hamiltonkreis

Hamiltonweg

hamiltonsch

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