Graphen und Algorithmen I

Wintersemester 2007/08

Mitschrift von Yves Radunz

Inhaltsverzeichnis

1 Grundlegende Definitionen und Eigenschaften 7 1.1 Wiederholung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Weitere Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Darstellung von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Tiefensuche und Breitensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Kürzeste Wege 13 2.1 Kürzeste Wege in ungewichteten Graphen . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Kürzeste Wege in gewichteten Graphen . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Fibonacci-Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Graphen mit negativem Kantengewicht . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 Minimale Spannbäume (bei gewichteten Kanten) . . . . . . . . . . . . . . . . . . . 19

3 Unabhängigkeitssysteme und Matroide 21 3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Greedy-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Flüsse 27 4.1 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Maximale Flüsse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5 Matching 35 5.1 Größte Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2 Schwerstes Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.3 Satz von Hall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.4 Satz von König . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.5 Sätze von Berge und Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6 Eulertouren, Hamiltonkreise 45 6.1 Eulertouren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2 Hamiltonkreis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3 TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.4 Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

7 Färbungen 51 7.1 Färbungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.2 Färbungen von 3-chromatische Graphen . . . . . . . . . . . . . . . . . . . . . . . . 54 7.3 Approximationsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.4 Kantenfärbungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.5 Perfekte Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 8 Planare Graphen 61

8.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 8.2 Färbungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 8.3 Eigenschaften 3-zusammenhängender Graphen . . . . . . . . . . . . . . . . . . . . 63 8.4 Satz von Kuratowski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Index 67

Vorlesung am 17.10.2007

5 6

Kapitel 1

Grundlegende Definitionen und Eigenschaften

1.1 Wiederholung

Bemerkung

1. Wenn nicht anderes angegeben wird, sind Graphen durch G = (V, E) mit |V | = n < ∞ Knoten und E ⊆ \binom{V}{2} Kanten definiert, d.h. einfach. Schlaufen, d.h. Kanten der Form {v, v} = {v}, sowie Multikanten treten dabei nicht auf. Es gilt |E| ≤ \frac{n(n−1)}{2}.

2. Gerichtete Graphen sind durch D = (V, A) mit |V | < ∞ und A ⊆ V^{2} definiert. Es gilt |A| ≤ n^{2}.

3. Ein Tournament T = (V, A) ist ein gerichteter Graph, in welchem die Kanten (v_{1}, v_{2}) und (v_{2}, v_{1}) nicht gleichzeitig auftreten. Es gilt |A| ≤ \frac{n(n−1)}{2}.

4. Für G = (V, E) und v ∈ V ist N(v) = {u ∈ V |{u, v} ∈ E} die Menge der Nachbarn von v.

5. d(v) = d_{G}(v) = |N(v)| ist der Grad des Knoten v.

Es gilt ∑_{v∈V} d(v) = 2|E| und damit auch |{v|d(v) ≡_{2} 1}| ≡_{2} 0.

6. In einem gerichteten Graphen D = (V, A) sind N_{+}(v) = {u ∈ V |(v, u) ∈ A} die ausgehenden und N_{−}(v) = {u ∈ V |(u, v) ∈ A} die eingehenden Nachbarn. Weiterhin definieren wir d_{±} = |N_{±}(v)|. Es gilt ∑_{v∈V} d_{+}(v) = ∑_{v∈V} d_{+}(v).

7. Zu S ⊆ V definieren wir N(S) = ⋃_{v∈S} N(v) und N^{∗}(S) = N(S) \ S.

8. Δ(G) = max_{v} ∈ V {d(v)} und δ(G) = min_{v} ∈ V {d(v)} sind der Maximal- bzw. Minimalgrad von G. Weiterhin ist \overline{d}(G) = ^{\frac{∑_{v∈V} d(v)}{|V |}} = \frac{2|E|}{|V |} der Durchschnittsgrad.

9. Ein Weg der Länge l ∈ ℕ ist eine Knotenfolge (v_{0}, ..., v_{l}) ∈ V^{l+1} mit {v_{i}, v_{i+1}} ∈ E und i = 0, ..., l − 1.

10. Ein Pfad ist ein Weg mit paarweise verschiedenen Knoten.

11. Ein Zykel ist ein Weg mit v_{0} = v_{l}.

12. Ein Kreis ist ein Weg mit v_{0} = v_{1} und paarweise verschiedenen Knoten v_{0}, ..., v_{l−1}.

1.1. WIEDERHOLUNG

KAPITEL 1. GRUNDLEGENDE DEFINITIONEN UND EIGENSCHAFTEN

13. Es gilt:

∀G = (V, E), δ(G) ≥ 2 : ∃ Kreis C ⊆ G : der Länge mindestens δ(G) + 1. Beweis:

Sei P = (v_{0}, ..., v_{l}) ein längster Pfad in G. Damit folgt N(v_{0}) ∈ {v_{0}, ..., v_{l}}.

⇒ ∃k : v_{k} ∈ N(v_{0}) : k ≥ d(v) ≥ δ(v)

Wir erhalten also den Kreis (v_{0}, ..., v_{k}, v_{0}) mit der Länge k + 1.

Vorlesung am 19.10.2007

14. ω(G) = max{k|G enthält K_{k}} ist die Cliquenzahl. Dabei bezeichnet K_{k} den vollständigen Graphen mit k Knoten (und damit auch mit \binom{k}{2} Kanten).

15. H ist ein Teilgraph von G (H ⊆ G), falls V (H) ⊆ V (G) und E(H) ⊆ E(G) ∩ \binom{V (H)}{2} gilt. Dabei bezeichnen V (·) und E(·) die Knoten- bzw. die Kantenmenge eines Graphen.

16. Zwei Graphen sind isomorph ((V (H), E(H)) = H ≅ H′ = (V (H′), E(H′))) genau dann, wenn eine Bijektion f : V (H) → V (H′) mit {x, y} ∈ E(H) ⇔ {f(x), f(y)} ∈ E(H′) existiert.

17. Sei G = (V, E) ein Graph und U ⊆V. Dann ist G[U] = (U, E ∩ \binom{U}{2}) der induzierte Teilgraph auf U.

18. Sei G = (V, E) ein Graph. Dann ist α(G) = max{|U||U ⊆ V, E(G[U]) = ∅} die Stabilitätszahl. U wird dabei auch als stabile Menge bezeichnet.

19. Sei G = (V, E) ein Graph. Eine Funktion f : V → ℕ ist eine k-Färbung von G, wenn ∀{x, y} ∈ E : f(x) ≠ f(y) und f(V) ≤ k. Die chromatische Zahl ist χ(G) = min{k|∃k-Färbung}.

20. Es gilt ω(G) − 1 ≤ Δ(G).

21. ω(G) ≤ χ(G)

22. |V (G)| = n ≤ χ(G) · α(G) Beweis:

Sei f : V → [k] eine k-Färbung von G. Dann gilt n = ∑_{i=1}^{k} \underbrace{|f^{−1}(i)|}_{≤α(G)} ≤ k · α(G), weil jede

Farbklasse f^{−1}(i) eine stabile Menge bildet.

23. n ≤ α(G)(1 + Δ(G)) Beweis:

Sei S ⊆ V stabile Menge mit |S| = α(G).

Dann gilt N(S) = V (G) \ S und |N(S)| ≤ |S| · Δ(G) ≤ α(G) + α(G) · Δ(G).

24. Ein Graph G = (V, E) ist zusammenhängend, wenn für alle x, y ∈ V ein x − y-Pfad existiert.

25. Ein Wald ist ein kreisfreier Graph. Ein Baum ist ein zusammenhängender Wald.

26. Sei F = (V, E) ein Wald. v ∈ V ist ein Blatt, falls d(v) ≤ 1 gilt.

27. H ⊆ G = (V, E) ist ein spannender Teilgraph, wenn V (H) = V gilt.

28. G = (V, E) ist genau dann zusammenhängend, wenn G einen spannenden Baum enthält.

29. Mit κ(G) bezeichnen wir die Zusammenhangszahl des Graphen G, d.h. κ(G) ist die minimale Anzahl an Knoten, die entfernt werden muss, um den Graphen in mehrere Komponenten zerfallen zu lassen oder alle Knoten zu entfernen.

KAPITEL 1. GRUNDLEGENDE DEFINITIONEN UND EIGENSCHAFTEN

1.2. WEITERE GRUNDLAGEN

1.2 Weitere Grundlagen

Proposition 1.1. Bäume sind eindeutig 2-färbbar. In der 2-Färbung eines Baumes haben zwei Knoten x und y genau dann die gleiche Farbe, wenn ihr Abstand, d.h. die Länge eines kürzesten x − y-Pfades gerade ist.

Beweis: Induktion über n = |V |.

1. n = 1, 2 ⇒ √

2. Sei T = (V, E) ein Baum mit n = |V | > 2 Knoten.

⇒ Es existiert ein Blatt v ∈ V und T − v = (V \ {v}, E \ {{x, v}|x ∈ V }) ist wieder ein Baum. Durch die Induktionsvoraussetzung existiert eine eindeutige 2-Färbung f von T − v, die sich auf T nur dadurch erweitern lässt, dass v eine andere Farbe als sein Nachbar erhält. Damit hat v die selbe Farbe wie alle Knoten, die von seinem Nachbarn ungeraden abstand haben. Somit hat v die gleiche Farbe wie alle Knoten, die von v geraden Abstand haben.

Definition (k-partit) Ein Graph ist k-partit (bipartit im Fall von k = 2), falls es eine k-Färbung des Graphen gibt.

Proposition 1.2. Ein Graph G = (V, E) ist genau dann bipartit, wenn G keinen ungeraden Kreis enthält.

Beweis:

1. ⇒

Falls G einen ungeraden Kreis enthält, folgt χ(G) ≥ 3.

2. ⇐

O.B.d.A. ist G zusammenhängend. Sei T ein Spannbaum von G und f eine eindeutige 2-Färbung von T, wobei f(x) = f(y) ⇔ dist(x, y) ∈ 2ℤ. Angenommen, f ist keine 2-Färbung von G.

⇒ ∃{x, y} ∈ E : f(x) = f(y).

⇔ dist_{T} (x, y) ∈ 2ℤ

Sei (x = x_{0}, ..., x_{l} = y) der Pfad in T gerader Länge. Damit ist (x = x_{0}, x_{1}, ..., x_{l} = y, x) ist ein Kreis ungerader Länge in G.

1.3 Darstellung von Graphen

Definition (Adjazenzmatrix) Wir stellen den Graphen G = (V, E) mit |V | = n durch eine Matrix (a_{ij})_{0≤i,j<n}A(G) ∈ ℝ^{n×n} dar,

wobei Zeilen und Spalten mit den Knoten indiziert sind. Damit gilt α_{ij} = \{ \begin{matrix}1 & \{i, j\} ∈ E \\ 0 & \{i, j\} ∉ E \end{matrix} .

Definition (Adjazensliste) Wir verwenden zur Darstellung des Graphen eine Liste der Knoten, wobei für jeden Knoten zusätzlich eine Liste der Nachbarknoten gespeichert wird.

1.4. TIEFENSUCHE UND BREITENSUCHE

KAPITEL 1. GRUNDLEGENDE DEFINITIONEN UND EIGENSCHAFTEN

1.4 Tiefensuche und Breitensuche

Vorlesung am 24.10.2007

Definition (DFS - Tiefensuche) DFS(G = (V, E), s){

for(v ∈ V)

v.besucht = false; DFS visit(G, s);

} DFS visit(G, v){

v.besucht = true; for(w ∈ N(v))

if(w.besucht == false) DFS visit(G, w);

}

Satz 1.1. Sei G zusammenhängend. Dann durchläuft DFS alle Kanten und Knoten von G in O(|E(G)|).

Beweis: Sei v ∈ V ein knoten, der nicht besucht wurde. Da G zusammenhängend ist, existiert ein s−v-Pfad (s = x_{0}, x_{1}, ..., x_{l} = v) in G. Sei k der größte Index, so dass x_{k} besucht wurde. k existiert, da x_{0} = s besucht wurde. Da x_{k+1} ∈ N(x_{k}) ist, wurde DFS visit(G, x − k + 1) aufgerufen und x_{k+1} besucht. Damit müssen alle Knoten einmal besucht werden. Weil alle Knoten einmal besucht werden, wird die for-Schleife in DFS-visit für jeden Knoten v ∈ V ausgeführt und somit betrachten wir alle Kanten. Damit wird jede Kante genau zweimal betrachtet. Laufzeit:

1. Die for-Schleife in DFS wird in O(n) durchlaufen.

2. Jeder Knoten wird genau einmal besucht. Damit werden die Zuweisungen in DFS visit in O(n) ausgeführt.

3. In der for-Schleife von DFS visit betrachten wir jede Kante zweimal und die folgenden Anweisungen lassen sich in O(1) ausführen.

4. Damit hat die for-Schleife in DFS visit einen Gesamtaufwand von O(m).

Damit erhalten wir eine Laufzeit von O(n + n + m) = O(m) wegen n ≤ m + 1 (G ist zusammenhängend).

Definition (2-Färber) 2COL(G = (V, E)){ //G ist ungerichteter Graph 2COL findet 2-Färbung f oder erkennt, dass χ(G) ≥ 3.

for(v ∈ V)

v.f = −1; select s ∈ V; s.f = 0; 2COLvisit(G, s);

} 2COLvisit(G, v){

for (w ∈ N(v))

if(w.f == −1){

w.f = 1 − v.f;

KAPITEL 1. GRUNDLEGENDE DEFINITIONEN UND EIGENSCHAFTEN

1.4. TIEFENSUCHE UND BREITENSUCHE

2COLvisit(G, w); }else if(w.f == v.f)

System.out.println(χ(G) ≥ 3);

}

Satz 1.2. Sei G zusammenhängend. Der Algorithmus 2COL finden eine 2-Färbung von G falls es eine gibt in O(n).

Definition (BFS - Breitensuche) BFS(G = (V, E), s){

besucht = {s}; Q.add(s); while(Q ≠ ∅){

v = Q.head;

for(w ∈ N(v) \ besucht){

Q.add(v);
besucht = besucht ∪ {w};

} }

}

Satz 1.3. BFS besucht alle Knoten und Kanten in einem zusammenhängenden Graphen in O(m).

Beweis: Wie Beweis für DFS.

1.4. TIEFENSUCHE UND BREITENSUCHE KAPITEL 1. GRUNDLEGENDE DEFINITIONEN UND EIGENSCHAFTEN

Kürzeste Wege

2.1 Kürzeste Wege in ungewichteten Graphen

Definition Sei G = (V, E) ein Graph. Für alle x, y ∈ V sei dist(x, y) die Länge des kürzesten x − y-Pfades in G. Wenn kein solcher Pfad existiert, dann sei dist(x, y) = ∞. Falls G ungerichtet ist, gilt dist(x, y) = dist(y, x). Für s, v ∈ V setzen wir dist_{s}(v) = dist(s, v).

Frage Wie berechnen wir dist(·, ·)? APSP-Problem (All-Pairs-Shortest-Path): Finde dist(·, ·) SSSP-Problem (Single-Source-Shortest-Path): Gegeben s ∈ V: Finde dist_{s}(·)

Definition Abstände(G, s){ //Berechne dist_{s}(·) in einem ungewichteten Graphen G.

besucht = {s}; Q.add(s); \overline{dist_{s}}(s) = 0; while(Q ≠ ∅){

v = Q.head;

for(w ∈ N(v) \ besucht){

Q.add(v);
besucht = besucht ∪ {w};
\overline{dist_{s}}(w) = \overline{dist_{s}}(v) + 1;

} }

}

Satz 2.1. Der Algorithmus Abstände berechnet dist_{s}(·) für gegebenen s ∈ V eines ungerichteten Graphen G = (V, E) in O(m).

Beweis: Laufzeit: siehe BFS Beobachtung: Zu jedem Zeitpunkt gilt: Sei Q = (x_{0}, ..., x_{l}), dann gilt: \overline{dist_{s}}(x_{0}) ≤ ... ≤ \overline{dist_{s}}(x_{i}) ≤ \overline{dist_{s}}(x_{i+1}) ≤ ... ≤ \overline{dist_{s}}(x_{l}) ≤ \overline{dist_{s}}(x_{0}) + 1

Vorlesung am 26.10.2007

2.2. KÜRZESTE WEGE IN GEWICHTETEN GRAPHEN KAPITEL 2. KÜRZESTE WEGE

Beweis dieser Beobachtung durch Induktion über die Anzahl der Knoten, die in Q eingefügt wurden:

1. Induktionsanfang:

Wenn s eingefügt wird, gilt die Behauptung.

2. Induktionsschritt:

Sei Q = (x_{0}, ..., x_{k}). Neue Knoten werden nur hinzugefügt, nachdem x_{0} entfernt wurde, und wenn x_{0} noch enbesuchte Nachbarn y_{0}, ..., y_{l} hat. y_{0}, ..., y_{l} werden in Q eingetragen mit \overline{dist_{s}}(y_{i}) = \overline{dist_{s}}(x_{0}) + 1.

⇒ Für die neue Warteschlange (x_{1}, ..., x_{k}, y_{0}, ..., y_{l}) gilt: \overline{dist_{s}}(x_{1}) ≤ ... ≤ \overline{dist_{s}}(x_{k}) ≤ \overline{dist_{s}}(x_{0}) + 1 = \overline{dist_{s}}(y_{0}) = ... = \overline{dist_{s}}(y_{l}). Es bleibt also noch \overline{dist_{s}}(x) = dist_{s}(x) zu zeigen. Für x = s ist dies klar. Zunächst zeigen wir nun \overline{dist_{s}}(x) ≥ dist_{s}(x): Für einen Knoten v ∈ V \ \{s\} sei p(v) der Knoten u ∈ V, als dessen Nachbar v in Q eingefügt wurde. Dann gilt \overline{dist_{s}}(v) = dist_{s}(p(v)) + 1. Sei x ∈ V \ {s} fest. ⇒ ∃y_{0}, ..., y_{k} : y_{0} = s, y_{i} = p(y_{i+1}), y_{k} = x ⇒ (y_{0}, ..., y_{k}) ist ein s − x-Pfad ⇒ \overline{dist_{s}}(x) = k = Länge des Pfades (y_{0}, ..., y_{k}) Nun zeigen wir \overline{dist_{s}}(x) ≤ dist_{s}(x): Sei x ∈ V \ {s} beliebig und (y_{0}, ..., y_{l}) ein kürzester s − x-Pfad. Wir beweisen nun die Ungleichung durch Induktion über dist_{s}(x).

1. Induktionsanfang: x = s

Wir erhalten dist_{s}(x) = \overline{dist_{s}}(x) = 0.

2. Induktionsschritt:

Wir haben \overline{dist_{s}}(y_{l−1}) = dist_{s}(y_{l−1}) = dist_{s}(x) − 1.

(a) : Fall 1 y_{l} = x wird als Nachbar von y_{l−1} in Q eingefügt. ⇒ \overline{dist_{s}}(x) = \overline{dist_{s}}(y_{l−1}) + 1 = dist_{s}(x)

(b) Fall 2 Falls x bereits in Q ist, wenn y_{l−1} aus Q entfernt wird, dann folgt aus der Beobachtung: \overline{dist_{s}}(x) ≤ \overline{dist_{s}}(y_{l−1}) + 1 = dist_{s}(x)

2.2 Kürzeste Wege in gewichteten Graphen

Gegeben ist ein gewichteter Graph G = (V, E), w : E → ℝ_{≥0} und ein Startknoten s ∈ V. Gesucht ist dist_{s}(·), wobei dist_{s}(x)=∑_{i=0}^{l−1} w(y_{1}, y_{i+1})|(y_{0}, ..., y_{l}) ist ein s−x-Pfad} und w(x, y)=w({x, y}).

Bemerkung

1. Falls w ≡ 1 gilt, dann löst der Algorithmus für ungewichtete Graphen das Problem.

2. Im Fall w : E → ℝ beliebig ist das Problem NP -Schwer.

3. Falls w : E → ℝ mit der Einschränkung gegeben ist, dass keine negativen Kreise existieren, so ist das Problem weiterhin in P.

4. Für den Dijkstra-Algorithmus ist w : E → ℝ_{>0} = ℝ_{+} nötig.

KAPITEL 2. KÜRZESTE WEGE 2.2. KÜRZESTE WEGE IN GEWICHTETEN GRAPHEN

Definition (Dijkstra) Dijkstra(G = (V, E), s, w){

for(v ∈ V \ {s})

\overline{dist_{s}}(v) = ∞;
\overline{dist_{s}}(s) = 0;
Q = V;
while(Q ≠ ∅){
select x ∈ \{a ∈ Q|∀y ∈ Q : \overline{dist_{s}(a)} ≤ \overline{dist_{s}}(y)\};
Q = Q \ {x};
for(y ∈ N(x) ∩ Q)
\overline{dist_{s}}(y) = min\{\overline{dist_{s}}(y), \overline{dist_{s}}(x) + w(x, y)\};
}

} Für gerichtete Graphen verwenden wir A statt E und N_{+} statt N.

Satz 2.2. Der Dijkstra-Algorithmus berechnet dist_{s}(·) in O(n^{2}).

Beweis: Laufzeit: O(n) + O(1) + n · O(n) + ∑_{x∈V} d(x) = O(n^{2} + m) = O(n^{2}) Laufzeit (rev.): Sei Q eine Datenstruktur, welche die folgende Operationen unterstützt:

1. init

2. insert

3. extractMin

4. decreaseKey

⇒ Laufzeit von Dijkstra: O((init + insert) · n + n · (extractMin) + m · (decreaseKey)) Listen ⇒ O(n^{2}), MinHeap ⇒ O((n + m) log n) ⇒ MinHeaps sind besser, falls m = o(\frac{n^{2}}{log n}) gilt.

Vorlesung am 31.10.2007

Es fehlt also noch der Beweis, dass wirklich dist_{s}(·) berechnet wird. Sei also x ∈ U. Dass dist_{s}(x) ≤ \overline{dist_{s}}(x) gilt, folgt direkt aus der letzten Zeile des Algorithmus’, denn wenn \overline{dist_{s}}(x) geändert wird, existiert auch ein Weg der entsprechenden Länge. Es bleibt also noch \overline{dist_{s})}(x) ≤ dist_{s}(x) zu zeigen. Wir führen den Beweis durch Induktion über die Knoten, die aus Q entfernt wurden.

1. Induktionsanfang: s wird als erstes aus Q entfernt und hier gilt auch die entsprechende Ungleichung.

2. Sei x der nächste Knoten, der Q verlässt und s = y_{0}, ..., y_{k} = x) der kürzeste s − x-Pfad. Sei i der maximale Index, sdass y_{i} bereits aus Q entfernt wurde. Mit der Induktionsvoraussetzung gilt \overline{dist_{s}}(y_{i}) ≤ dist_{s}(y_{i}).

⇒ \overline{dist_{s}}(y_{i+1}) ≤ dist_{s}(y_{i}) + w(y_{i}, y_{i+1}).

Da x der nächste Knoten ist, der aus Q entfernt wird, gilt

\overline{dist_{s}}(x) ≤ \overline{dist_{s}}(y_{i+1}) ≤ dist_{s}(y_{i}) + w(y_{i}, y_{i+1}) ≤ dist_{s}(x),

weil w(y_{i}, y_{i+1}) ≥ 0 gilt.

Damit ist der Satz bewiesen.

2.3. FIBONACCI-HEAPS  KAPITEL 2. KÜRZESTE WEGE

Definition (Armortisierte Laufzeit) Sei D_{0} eine Startkonfiguration und op_{1}, ..., op_{n} eine Folge von Operationen mit jeweiliger Laufzeit t_{1}, ..., t_{n}. Damit haben wir eine Gesamtlaufzeit ∑_{i=1}^{n} t_{i}. Die amortisierte Laufzeit (pro Operation) ist \frac{1}{n} ∑_{k=1}^{n} t_{k} = a. Eine Datenstruktur Q hat amortisierte Laufzeit a für die Operation OP, falls für jede Sequenz von m Ausführungen von OP die Gesamtlaufzeit O(m · a) ist.

Beispiel (Zählen) Wir zählen von 0 bis n in binärer Darstellung und als Laufzeit pro Operation wählen wir die Anzahl der Bits, die beim Zählen von k nach k + 1 geändert werden müssen. In diesem Fall haben wir eine amortisierte Laufzeit von 2. Beweis: Wir erhalten als Gesamtlaufzeit O(∑_{i=1}^{log n} i\frac{n}{2^{i}}). Weiterhin haben wir ∑_{i=1}^{log n} i\frac{n}{2^{i}} ≤ \frac{n}{2} ∑_{i=1}^{∞} \frac{i}{2^{i−1}} = 2n. Zweite Beweismöglichkeit(Potentialfunktion): Wir betrachten eine Potentialfunktion ψ :Konfigurationen→ ℝ. Weiterhin sei D_{0}, ... eine Folge von Konfigurationen, die durch die Operationen aus D_{0} erreicht werden und es gelte ψ(D_{i}) ≥ ψ(D_{0}) für alle i = 1, .... Jetzt setzen wir t_{i}^{∗} = t_{i} + \underbrace{ψ(D_{i}) − ψ(D_{i−1})}_{Potenzialdifferenz}.

⇒ ∑_{i=1}^{n} t_{i}^{∗} = ∑_{i=1}^{n} t_{i} + ∑_{i=1}^{n} ψ(D_{i}) − ψ(D_{i−1}) ≥ ∑_{i=1}^{n} t_{i} In unserem Fall setzen wir ψ(D_{i}) auf die Anzahl der Einsen von D_{i}. Damit haben wir ψ(D_{0}) = 0 ≤ ψ(D_{i}). Es gilt also t_{i}^{∗} = t_{i} + ψ(D_{i}) − ψ(D_{i−1}). Weiterhin haben wir ψ(D_{i}) − ψ(D_{i−1}) = −l_{i} + 1, wobei l_{i} die Anzahl der Einsen am Ende von D_{i−1} ist. Wegen t_{i} = l_{i} + 1 erhalten wir t_{i}^{∗} = l_{i} + 1 − l_{i} + 1 = 2.

2.3 Fibonacci-Heaps

Definition (Heap) Ein (Min-)Heap H ist ein Baum, wo jeder Knoten x einen Eintrag (x.key) hat sodass für alle Kinder y von x die Ungleichung x.key ≤ y.key gilt.

Definition (Fibonacci-Heap) Wir betrachten einen Heap, wo jeder Knoten x die folgenden Einträge hat:

x.right siblingZeiger auf den rechten Nachbarn von x x.left sibling Zeiger auf den linken Nachbarn von x x.first child Zeiger auf ein Kind von x x.parent Zeiger auf den Vater von x x.num child Anzahl der Kinder von x x.key Das Gewicht, das x zugeordnet ist x.marked Eine Markierung.

Warum dieser Heap (mit den darauf definierten Operationen) Fibonacci-Heap heißt, werden wir später sehen (oder auch nicht *g*).

Definition (Operationen) Zu den Operationen auf den Fibonacci-Heaps sehe man sich diverse Skripte, Bücher etc. oder einfach die Theoretische Informatik III an.

Vorlesung am 02.11.2007

KAPITEL 2. KÜRZESTE WEGE  2.3. FIBONACCI-HEAPS

Lemma 2.1. (1) Sei x ein Element des Heaps mit Kindern y_{1}, ..., y_{n} (entsprechend der Einfügereihenfolge durchnummeriert). Dann hat y_{i} mindestens i − 2 Kinder für i ≥ 2.

Beweis: Nur in Consolidate wird ein Element zu einem Kind von einem anderen Knoten. Zum Zeitpunkt, wo y_{i} Kind von x wird, hat x bereits i − 1 Kinder, nämlich y_{1}, ..., y_{i−1}. Damit hat y_{i} genau i − 1 Kinder. Am Schluss hat y_{i} ≥ i − 2 Kinder.

Satz 2.3. (von Binet 1843) Für die n-te Fibonacci-Zahl gilt f_{n} = \frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^{n} − (\frac{1−\sqrt{5}}{2})^{n}) = ⌊\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n} + \frac{1}{2}⌋.

Beweis: Wir machen den folgenden Ansatz:

F (x) = ∑_{k=0}^{∞} f_{k}x^{k} = f_{0} = f_{0} + f_{1}x + ∑_{k=2}^{∞} f_{k}x^{k}

= \underbrace{f_{0}}_{=0} + \underbrace{f_{1}}_{=1} x + ∑_{k=2}^{∞} f_{k−1}x^{k} + ∑_{k=2}^{∞} f_{k−2}x^{k}

= 0 + x + x ∑_{k=0}^{∞} f_{k}x^{k} + x^{2} ∑_{k=2}^{∞} f_{k}x^{k}

= x + xF (x) + x^{2}F (x) ⇒ F (x) = \frac{x}{1−x−x^{2}} = \frac{A_{1}}{1−α_{1}x} + \frac{A_{2}}{1−α_{2}x} mit A_{1} = \frac{1}{α_{1}−α_{2}} = \frac{1}{\sqrt{5}}, A_{2} = −\frac{1}{\sqrt{5}}

⇒ \frac{x}{1−x−x^{2}} = \frac{1}{\sqrt{5}} (\frac{1}{1−α_{1}x} − \frac{1}{1−α_{2}x})

Mit \frac{1}{1−α_{1}x} = 1 + α_{1}x + α_{1}^{2}x^{2} + ... und \frac{1}{1−α_{2}x} = 1 + α_{2}x + α_{2}^{2}x^{2} + ....

Da f_{n} der Vorfaktor der Summanden vor x^{n} ist, erhalten wir f_{n} = \frac{α_{1}^{n}−α_{2}^{n}}{\sqrt{5}} .

Korollar 2.1. Jedes Element im Heap mit n Elementen hat maximal log_{α_{1}} n Kinder.

Beweis: Folgt direkt aus dem Lemma 1.

Bemerkung (Laufzeitanalyse)

1. Die Laufzeiten von Insert und min sind offensichtlich O(1).

2. Extract min hat eine Laufzeit von O(log n). Init von A hat eine Laufzeit von O(log n) und die While-Schleife eine Laufzeit von O(log n + w(H)).

Zum Nachweis der amortisierten Laufzeit betrachten wir wieder eine Potentialfunktion, gegeben durch ψ(H_{i}) = w(H_{i}) + 2m(H_{i}) mit w als der Größe der Wurzelliste und m als der Anzahl der markierten Knoten, und setzen t_{i}^{∗} = t_{i} + ψ(H_{i}) − ψ(H_{i−1}).

Potentialänderung bei Consolidate:

Elemente können nur an einer Stelle dieser Methode ihre Markierung verlieren. Die Wurzelliste hat zu Anfang w(H) Elemente, danach maximal o(log n).

⇒ Die amortisierte Laufzeit ist O(log n).

3. Decrease key hat eine Laufzeit von O(c), wobei c die Anzahl der Aufrufe von cut ist.

Die Potentialänderung ist:

In jedem Aufruf von cut wird eine Markierung zurückgenommen, bis auf den letzten Aufruf, wo eine neue Markierung entstehen kann. In der Wurzelliste können wir c neue Elemente haben.

Damit führt dies zu einer amortisierten Laufzeit von O(c)−𝔠·c+4 ∈ O(1), weil die Konstante 𝔠 bei der Wahl des Potentials so gewählt werden kann, dass sie das O(c) aufhebt.

Vorlesung am 09.11.2007

2.4. GRAPHEN MIT NEGATIVEM KANTENGEWICHT KAPITEL 2. KÜRZESTE WEGE

Bemerkung (Minimale Laufzeit von Dijkstra) Der Dijkstra-Algorithmus hat eine minimale Laufzeit von O(n log n + m), weil sich mit diesem Algorithmus n − 1 Zahlen sortieren lassen:

[figure: n; 1; 2; 3; ...; n − 3; n − 2; n − 1]

Damit haben wir eine minimale Laufzeit von Ω(n log n).

2.4 Graphen mit negativem Kantengewicht

Wir betrachten zunächst ungerichtete Graphen. Um kürzeste Wege zu finden, nutzen wir den Bellmann-Moore-Algorithmus (mit Hilfe dynamischer Programmierung), welcher jedoch nur funktioniert, wenn der Graph keine negativen Kreise enthält. Es bleibt dabei noch erlaubt, auf einer Kante mit negativem Gewicht hin- und herzulaufen. Kreise seien also Kreise mit mindestens 3 verschiedenen Knoten.

Definition (Bellman-Moore-Algorithmus) boolean Bellmann-Moore(G, l : E → ℝ, s){

for(x ∈ V \ {s})

d_{i}(x) = ∞; for(i = 0, ..., n)

d_{i}(s) = 0; for(i = 1, ..., n)

for((x, y) ∈ E)

d_{i}(y) = min{d_{i−1}(y), d_{i−1}(x) + l(x, y)};

for(x ∈ V)

if(d_{n}(x) ≠ d_{n−1}(x)) return false;

else

x.abstand = d_{n}(x); return true;

}

Satz 2.4. In Graphen ohne negative Kreise arbeitet der Algorithmus von B.-M. korrekt und hat eine Laufzeit von O(nm).

Beweis:

1. Laufzeit:

Diese ist durch die vorkommenden Schleifen offensichtlich gegeben.

2. Korrektheit:

Wir zeigen dist(s, x) ≤ d_{i}(x) für i = 0, ..., n und x ∈ V durch Induktion über i.

(a) Für i = 0 ist dies offensichtlich (∞ ≥ dist(s, x) bzw. dist(s, s) = 0 = d_{0}(s) der Fall.

(b) Sei i > 0. Annahme: dist(s, x) > d_{i}(x) Laut Induktionsvoraussetzung haben wir dist(s, x) ≤ d_{i−1}(x) ⇒ d_{i}(x) < d_{i−1}(x). Wegen d_{i}(x) = min{d_{i−1}(x), min_{(v,l)∈E}{d_{i−1}(v)+l(v, x)}} erhalten wir die Existenz von v ∈ V mit d_{i−1}(v) + l(v, x) = d_{i}(x). Weiterhin haben wir dist(s, v) + l(v, x) ≥ dist(s, x) > d_{i}(x), was einen Widerspruch darstellt.

KAPITEL 2. KÜRZESTE WEGE

2.5. MINIMALE SPANNBÄUME (BEI GEWICHTETEN KANTEN)

Nun bleibt noch zu zeigen, dass wirklich dist(s, x) = d_{i}(x) gilt. Wir betrachten hierfür einen kürzesten s − x-Pfad s = v_{0}, v_{1}, ..., v_{k} = x. Nun zeigen wir d_{i}(v_{i}) = d_{i+1}(v_{i}) = ... = d(v_{i}) = dist(v_{i}). Wir beweisen dies per Induktion über i.

(a) i = 0 Hier haben wir ∀j = 0, ..., k : dist(s, v_{0}) = 0 = d_{0}(s) = d_{j}(s).

(b) i > 0 Wir haben d_{i−1}(v_{i−1}) = dist(s, v_{i−1}). Zu zeigen ist nun d_{i}(v_{i}) = dist(s, v_{i}). Wegen des ersten Teils haben wir dist(s, v_{i}) = dist(s, v_{i−1}) + l(v_{i−1}, v_{i}) ≥ d_{i}(v_{i}) ≥ dist(s, v_{i}). ⇒ d_{i}(v_{i}) = dist(s, v_{i}) Die übrigen Gleichheiten folgen aus der Monotonie von d_{i}(x) (in i).

Falls es negative Kreise gibt, so gibt es bei zusammenhängenden Graphen Knoten x mit beliebig kleinem Abstand. Damit wäre d_{n}(x) ≠ d_{n−1}(x).

2.5 Minimale Spannbäume (bei gewichteten Kanten)

Die Verfahren DFS und BFS funktionieren nicht mit Kantengewichten. Wir werden uns daher mit zwei anderen Algorithmen befassen:

1. Kruskal: O(m log m)

2. Prim: O(n log n + m)

Definition (Kruskal-Algorithmus) Gegeben ist ein ungerichteter Graph mit positiven Kantengewichten, in dem ein minimaler Spannbaum gesucht wird. void Kruskal(G, l){

sort(E, l(e_{1}) ≤ ... ≤ l(e_{m})); T = V (G); for (i = 1, ..., m)

if(kreisfrei(T + e_{i}))

T = T + e_{i};

}

Satz 2.5. Der Algorithmus von Kruskal ist korrekt und läuft in O(m log m).

Beweis:

1. Kreisfreiheit ist durch die Kosntruktion gegeben.

2. Spannbaumeigenschaft ist gegeben, weil der Graph zusammenhängend ist.

3. Minimalität:

Sei T^{∗} ein minimaler Spannbaum so gewählt, dass i, der kleinste Index mit e_{i} ∈ T und e_{i} ∉ T^{∗}, maximal wird. Falls i nicht existiert, so gilt T = T^{∗}. Betrachten wir nun T^{∗} + e_{i}. Dieser Graph enthält einen Kreis K. Weil T kreisfrei ist, gibt es e_{j} auf K mit e_{j} ∉ T. Auf Grund der Arbeitsweise des Algorithmus’ folgt l(e_{i}) ≤ l(e_{j}). Im Fall der Gleichheit ist auch T^{∗} − e_{j} + e_{i} ein minimaler Spannbaum, womit wir der Wahl von T^{∗} (mit i maximal) widersprechen. Im Fall der Ungleichheit haben wir einen Widerspruch, weil T^{∗} dann kein minimaler Spannbaum ist.

2.5. MINIMALE SPANNBÄUME (BEI GEWICHTETEN KANTEN)

KAPITEL 2. KÜRZESTE WEGE

4. Laufzeit:

Zunächste zeigen wir, dass der Kreisfreiheitstest schnell möglich ist.

Wir fügen nur Kanten ein, die nicht in einer Zusammenhangskomponente liegen. Dies überprüfen wir, indem wir jeder Zusammenhangskomponente eine Nummer zuweisen und bei der Vereinigung jedem Knoten der kleineren Komponente die Nummer der größeren Komponente zuweisen. Zum Größenvergleich der Zusammenhangskomponenten wählen wir eine simultane Breitensuche in beiden Zusammenhangskomponenten. Die Komponente, wo die Breitensuche zuerst abgeschlossen ist, ist die kleinere.

Damit wird die Zusammenhangskomponentennummer jedes Knoten höchstens log_{2} n mal aktualisiert.

Das Sortieren der Kanten ist (z.B. mit Mergesort) in O(m log m) möglich.

Definition (Algorithmus von Prim) Die Idee ist, einen Baum stückweise aufzubauen, indem man bei einem Knoten beginnt. Anschließend wird in jedem Schritt die Kante zu dem Baum hinzugenommen, welche einen neuen Knoten mit dem Baum verbindet und minimales Gewicht hat. void Prim(G, l){

T = {s} //s beliebig gewählt for(i = 1, ..., n − 1){

select(e = {x, y}|x ∈ V (T), y ∉ V (T), l(e) minimal); T = T + y + e;

} }

Satz 2.6. Der Algorithmus von Prim ist korrekt und hat einen Zeitaufwand von O(n log n + m). Wir zeigen induktiv, dass T ein Teilbaum eines minimalen Spannbaums von G ist.

1. Zu Beginn ist dies offensichtlich der Fall.

2. Es sei T im Baum enthalten. Zu zeigen ist, dass T + y + e weiterhin ein Teilbaum eines minimalen Spannbaums ist.

T + y + e ist offensichtlich ein Baum. Es bleibt also noch die Enthaltenheit zu zeigen.

Annahme: T + y + e ist nicht Teil eines minimalen Spannbaums.

Sei T^{∗} ein minimaler Spannbaum von G. Damit hat T^{∗} + e einen Kreis K.

Es gibt also eine Kante f auf K zwischen V (T) und V (G) \ V (T) mit l(e) ≤ l(f) (Arbeitsweise des Algorithmus’). Es ist also T^{∗} − f + e ein minimaler Spannbaum für G, was einen Widerspruch darstellt.

Die Laufzeit O(m + n log n) erhalten wir mit Fibonacci-Heaps bei der Suche nach der minimalen Kante, die hinzugefügt wird.

Vorlesung am 14.11.2007

Unabhängigkeitssysteme und Matroide

3.1 Definition

Beispiel

1. Stabile Menge in G = (V, E).

Wir setzen S = V, I = {F ⊆ V |F ist stabile Menge}.

2. Minimal spannender Baum im zusammenhängenden Graphen G = (V, E). Wir setzen S = E, I = {F ⊆ E|F enthält keinen Kreis}.

3. Matching in G = (V, E).

Wir setzen S = E, I = {F ⊆ E| keine 2 Kanten in F haben gemeinsame Knoten}.

4. Kürzeste Pfade in G.

Wir setzen S = {zyklenfreie von u ∈ V ausgehenden Pfade} und I = {F ⊆ S|keine 2 Pfade haben gleiche Endknoten}.

5. Matrix.

Sei S = Spaltenvektoren einer Matrix und I = {F ⊆ S| die Vektoren in F sind lin. unabhängig}.

Definition (Unabhängigkeitssystem, Matroid) Ein Unabhängigkeitssystem ist ein Paar M = (S, I), dass folgende Bedingungen erfüllt:

1. S ist endlich und nichtleer.

2. I ist eine Familie von Teilmengen von S mit der Eigenschaft: ∀A ∈ I, B ⊆ A : B ∈ I. Falls zusaätzlich die Austauscheigenschaft (3.) ∀A, B ∈ I, |A| < |B| : ∃x ∈ B \ A : A ∪ {x} ∈ I gilt, so heißt M Matroid.

Beispiel Für die obigen Beispiele gilt durch diese Definition:

3.1. DEFINITION  KAPITEL 3. UNABHÄNGIGKEITSSYSTEME UND MATROIDE

1. 1. und 2. sind erfüllt, 3. nicht:

x  y  z

Hier sind {y} und {x, z} stabile Mengen, aber weder {x, y} noch {y, z}.

Demnach ist dies ein Unabhängigkeitssystem, aber kein Matroid.

2. Hier sind die ersten beiden Eigenschaften offensichtlich erfüllt. Die dritte Eigenschaft gilt ebenfalls, weil:

Seien A, B ⊆ E, |A| < |B|. Demnach sind G_{A} und G_{B} zwei Wälder, wobei G_{A} aus |V | − |A| und G_{B} aus |V | − |B| Zusammenhangskomponenten.

⇒ G_{B} hat weniger Zusammenhangskomponenten als G_{A}, damit gibt es eine Kante e in G_{B}, die zwei Zusammenhangskomponenten aus G_{A} miteinander verbindet. Damit kann diese Kante keinen Kreis schließen und es gilt G_{A} ∪ {e} ∈ I.

Dieses Beispiel beschreibt also ein Matroid, welches auch graphisches Matroid genannt wird.

3. Die ersten beiden Eigenschaften sind erfüllt, jedoch nicht die Dritte:

• _{a} • _{b} • _{c} •

Hier gilt {b} ∈ I und {a, c} ∈ I, jedoch weder {a, b} ∈ I, noch {b, c} ∈ I. Damit ist dieses Beispiel ein Unabhängigkeitssystem, aber kein Matroid.

4. Hier sind alle Eigenschaften erfüllt, womit dieses Beispiel ein Matroid ist.

5. Hier sind alle Eigenschaften erfüllt, wobei die dritte Eigenschaft mit Hilfe des Austauschsatzes von Steinitz folgt. (→ Lineare Algebra I/II) Also handelt es sich hierbei um ein Matroid (auch Matrixmatroid).

Definition Sei M = (S, I) ein Matroid. A ∈ I heißt maximal unabhängige Menge oder Basis, falls ∀x ∈ S \ A : A ∪ {x} ∉ I (keine echte Obermenge von A ist in I enthalten).

Proposition 3.1. In einem Matroid haben alle maximal unabhängigen Mengen die gleiche Größe.

Beweis: Angenommen, es gibt zwei maximal unabhängige Mengen A, B ∈ I mit |A| < |B|. Mit der dritten Eigenschaft erhalten wir jedoch ∃x ∈ B \ A : A ∪ {x} ∈ I, was einen Widerspruch zur Maximalität von A darstellt.

Beispiel Im graphischen Matroid sind die maximalen unabhängigen Mengen Bäume im Graphen. Diese haben alle die Größe n − 1.

Definition (gewichtetes Matroid) Ein gewichtetes Matroid ist ein Matroid M = (S, I) mit Gewichtsfunktion w : S → ℝ_{>0} mit ∀A ∈ I : w(A) = ∑_{x∈A} w(x).

Ziel Wir wollen in einem gewichteten Matroid nach einer unabhängigen Menge maximalen Gewichts suchen. In einem Matroid können auch Mengen mit minimalem Gewicht gesucht werden, indem man die Gewichte w′(x) = C − w(x) betrachtet.

KAPITEL 3. UNABHÄNGIGKEITSSYSTEME UND MATROIDE

3.2. GREEDY-ALGORITHMUS

3.2 Greedy-Algorithmus

Definition (Greedy-Algorithmus) void Greedy(M = (S, I), w : S → ℝ_{>0}){

sort(S, w(s_{1}) ≥ ... ≥ w(s_{n})); A = ∅; for(i = 0, ..., n)

if(A ∪ {s_{i}} ∈ I)

A = A ∪ {s_{i}};

}

Lemma 3.1. (30) Sei M = (S, I) mit w : S → ℝ_{>0} ein gewichtetes Matroid. Falls der Greedy-Algorithmus als erstes Element ein x ∈ S wählt, so gibt es auch eine unabhängige Menge größten Gewichts, die x enthält.

Beweis: Falls Greedy kein x ∈ S wählt, so ist ∅ ∈ I die einzige unabhängige Menge. Ansonsten: Sei B eine beliebige unabhängige Menge größten Gewichts mit x ∉ B. Da für alle y ∈ B die Menge {y} ein Element von I ist, haben wir ∀y ∈ B : w(y) ≤ w(x), weil der Greedy-Algorithmus das größte Element zuerst auswählt. Am Ende gilt: Alle Elemente von B bis auf ein y ∈ B sind zu A hinzugefügt worden. ⇒ A = (B \ {y}) ∪ {x} ⇒ w(A) ≥ w(B)

Definition Sei M = (S, I) mit w : S → ℝ^{+} ein gewichtetes Matroid. Wir definieren M_{x} =(S_{x}, I_{x}), w_{x}:S_{x} →ℝ^{+} mit S_{x} = {y ∈ S|{x, y} ∈ I}, I_{x} = {B ⊆ S \ {x}|B ∪ {x} ∈ I} und w_{x} = w|_{S_{x}}. Dann ist auch M_{x} wieder ein Matroid.

Lemma 3.2. (31) Seien M = (S, I) mit w : S → ℝ^{+} ein gewichtetes Matroid und x ∈ S das erste vom Greedy-Algorithmus gewählte Element und A′ eine unabhängige Menge größten Gewichtes in M_{x}. Dann ist auch A = A′ ∪ {x} eine unabhängige Menge größten Gewichts in M.

Beweis: Sei A′ eine beliebige unabhängige Menge größten Gewichts in M_{x}. Dann ist A = A′ ∪ {x} eine unabhängige Menge in M. Es gilt w(A) = w(A′) + w(x).

Satz 3.1. (32) Der Greedy-Algorithmus findet in O(n log n + nf(n)) eine unabhängige Menge größten Gewichts in einem Matroid M = (S, I) und w : S → ℝ^{+}. Dabei bezeichnet f(n) die

Laufzeit des Tests auf A ∪ {x} ∈^{?} I.

Beweis:

1. Laufzeit:

Wir benötigen O(n log n) zum sortieren. Die for-Schleife wird n-mal durchlaufen, also haben wir eine Laufzeit von O(nf(n)) für die Schleife.

2. Korrektheit:

Existiert eine unabhängige Menge ≠ ∅ in M, so wählt Greedy ein x im ersten Schritt. Mit Lemma 30 existiert also eine unabhängige Menge größten Gewichts, die x enthält. Nach Wahl von x kann die Fortsetzung des Algorithmus’ auf M als die Anwendung des Algorithmus’ auf M_{x} interpretiert werden.

3.2. GREEDY-ALGORITHMUS KAPITEL 3. UNABHÄNGIGKEITSSYSTEME UND MATROIDE

Mit Lemma 31 erhalten wir dann, dass die in M_{x} gefundene maximale unabhängige Menge größten Gewichts mit {x} zu einer maximalen unabhängigen Menge größten Gewichts in M erweitert werden kann. Rekursiv folgt (mit Anwendung von Lemma 30 und Lemma 31), dass in M_{x} eine maximale unabhängige Menge gefunden wird. Somit erhalten wir auch in M eine maximale unabhängige Menge.

Satz 3.2. (33) Sei M = (S, I) ein Unabhängigkeitssystem. Falls der Greedy-Algorithmus für beliebige Gewichte w : S → ℝ^{+} eine unabhängige Menge größten Gewichts findet, dann ist M ein Matroid.

Beweis: Angenommen, M sei kein Matroid, d.h. ∃A, B ∈ I, |A| < |B| : ∀x ∈ B \ A : A ∪ {x} ∉ I.

Wir definieren nun die Gewichtsfunktion w(x) = \frac{1}{|B|−|A|} · \{ \begin{matrix}|B| + 1 & , falls x ∈ A \\ |A| + 1 & , falls x ∈ B \ A \\ \frac{1}{|S|} & , sonst \end{matrix} .

⇒ w(A) = \frac{|A|(|B|+1)}{|B|−|A|} < \frac{|B|(|A|+1)}{|B|−|A|} ≤ w(B) ⇒ A ist keine unabhängige Menge größten Gewichts. Greedy wählt zunächst alle Elemente aus A, weil diese am schwersten sind. Anschließend darf er kein Element aus B hinzunehmen, weil dann A ∪ {x} ∉ I gilt (Annahme). Also können nur noch Elemente aus S \ B hinzugefügt werden. Diese haben ein Gesamtgewicht, das kleiner als \frac{1}{|B|−|A|} ist. Damit erhält der Greedy-Algorithmus eine Menge mit einem Gewicht von höchstens w(A) + \frac{1}{|B|−|A|} < w(B) und findet also nicht die Menge maximalen Gewichts. ⇒ Der Greedy-Algorithmus ist nicht korrekt, was einen Widerspruch zur Voraussetzung darstellt. Also muss M ein Matroid sein.

Vorlesung am 16.11.2007

Definition (Abhängige Menge, Kreis) Sei M = (S, I) ein Matroid, dann heißt X ⊆ S abhängige Menge, falls X ∉ I. Ein Kreis C is eine minimale abhängige Menge, d.h. C ∉ I und ∀x ∈ C : C \ {x} ∈ I.

Satz 3.3. (34) Sei M = (S, I) ein Matroid und A ∈ I. Für x ∈ S \ A ist A ∪ {x} ∈ I oder A ∪ {x} enthält einen eindeutig bestimmten Kreis.

Beweis: Sei A ∪ {x} ∉ I. Wir definieren C = {c ∈ S|(A ∪ {x}) \ {c} ∈ I}. Dann gilt C ∉ I: Angenommen es gelte C ∈ I. Wir betrachten D ∈ I mit C ⊆ D ⊆ A ∪ {x}, wobei D eine maximal unabhängige Menge ist. Da A ∈ I ist A eine maximal unabhängige Menge in A∪{x}. Damit haben wir |D| = |A|. Dann muss es ein d ∈ A∪{x} geben, sodass D = (A∪{x})\{d}. Wegen D ∈ I und der Definition von C gilt d ∈ C. Wir erhalten also einen Widerspruch und damit C ∉ I. Nach Definition von C ist ∀c ∈ C : C \ {c} ∈ I. Somit ist C ein Kreis. Zu zeigen ist noch, dass es keinen anderen Kreis in A∪{x} gibt. Sei D ein beliebiger weiterer Kreis in A ∪ {x}. Falls es ein c ∈ C \ D gibt, so haben wir D ⊆ (A ∪ {x}) \ {c} ∈ I. Also wäre D kein Kreis. Wir erhalten also D ⊆ C. Weil C minimal ist, kann D nur ein Kreis sein, wenn D = C gilt.

Definition (Rang) Sei N = (S, I) ein Unabhängigkeitssystem und S′ ⊆ S.

1. Der Rang ist die Größe der größten unabhängigen Menge in S′: r(S′)=max{|Y ||Y ⊆S′, Y ∈I}.

2. Der untere Rang ϱ(S′) von S′ ist die Größe einer kleinsten maximalen unabhängigen Menge in S′: ϱ(S′) = min{|Y ||Y ⊆ S′, Y ∈ I, ∀x ∈ S′ \ Y : Y ∪ {x} ∈ I}.

KAPITEL 3. UNABHÄNGIGKEITSSYSTEME UND MATROIDE

3.2. GREEDY-ALGORITHMUS

3. Der Rangquotient ist q(N) = min_{S′⊆S} = \frac{ϱ(S′)}{r(S′)}.

Satz 3.4. (36) Sei N = (S, I) ein Unabhängigkeitssystem. Wenn für jedes A ∈ I und jedes x ∈ S gilt: A ∪ \{x\} hat höchstens p Kreise, so ist q(N) = \frac{1}{p}.

Beweis: Sei S′ ⊆ S und J, K zwei Basen von S′. Wir zeigen \frac{|J|}{|K|} ≥ \frac{1}{p}: Sei J \ K = {e_{1}, e_{2}, ..., e_{t}}. Wir konstruieren eine Sequenz K = K_{0}, K_{1}, ..., K_{t} von Teilmengen von J ∪ K, sodass

1. K_{i} ∈ I

2. J ∩ K ⊆ K_{i}

3. K_{i} ∩ {e_{1}, ..., e_{t}} = {e_{1}, ..., e_{i}}

4. |K_{i−1} \ K_{i}| ≤ p

für alle i = 0, ..., t gilt. K_{i} ∪ {e_{i+1}} enthält höchstens p Kreise. Jeder dieser Kreise muss K_{i} \ J schneiden, denn J ∈ I. ⇒ ∃X ⊆ K_{i} \ J : |X| ≤ p, (K_{i} \ X) ∪ {e_{i+1}} ∈ I (Für jeden Kreis entfernen wir ein Element dieses Kreises aus K_{i} und zerstören damit die Kreiseigenschaft.) Wir setzen K_{i+1} = (K_{i} \ X) ∪ {e_{i+1}}. Damit erhalten wir unduktiv J ⊆ K_{t} ∈ I. Da J eine Basis von S′ ist, gilt J = K_{t}. Wir haben also |K \ J| = ∑_{i=1}^{t} |K_{i−1} \ K_{i}| ≤ pt = p · |J \ K|. ⇒ |K| = |K \ J| + |K ∩ J| ≤ p|J \ K| + p|K ∩ J| = p|J| Wir haben also für beliebige Basen J und K von S′ die Ungleichung \frac{|J|}{|K|} ≥ \frac{1}{p}. Also gilt dies insbesondere dann, wenn J eine kleinste maximale unabhängige Menge und K eine größte unabhängige Menge in S′ ist. Damit folgt auch \frac{ϱ(S′)}{r(S′)} ≥ \frac{1}{p}. Weil dies für jedes S′ ⊆ S gilt, erhalten wir q(N) ≥ \frac{1}{p}. (Die Umkehrung (q(N) ≤ \frac{1}{p}) haben wir in der Vorlesung nicht gezeigt.)

Satz 3.5. Sei N = (S, I) ein Unabhängigkeitssystem. Für eine Gewichtsfunktion w : S → ℝ^{+} bezeichne G(N, w) das Gewicht der Lösung des Greedy-Algorithmus und OP T (N, w) das Gewicht einer größten unabhängigen Menge. Dann gilt q(N) ≤ \frac{G(N,w)}{OP T (N,w)} ≤ 1.

Beweis: Sei S = {s_{1}, s_{2}, ..., s_{n}} und w(s_{1}) ≥ w(s_{2}) ≥ ... ≥ w(s_{n}). Die Lösung des Greedy-Algorithmus auf dieser Sortierung bezeichnet G_{n} und die unabhängige Menge größten Gewichtes O_{n}. Weiterhin setzen wir S_{j} = {s_{1}, ..., s_{j}}, G_{j} = G_{n} ∩ S_{j} und O_{j} = O_{n} ∩ S_{j}. Da O_{j} ∈ I muss |O_{j}| ≤ r(S_{j}) gelten. Weiterhin ist G_{j} eine Basis von S_{j} und somit gilt |G_{j}| ≥ ϱ(S_{j}). Wir setzen d_{j} = w(s_{j}) − w(s_{j+1}) für j = 1, ..., n − 1 und d_{n} = w(s_{n}).

w(G_{n}) = ∑_{j=1}^{n}(|G_{j}| − |G_{j−1}|)w(s_{j}) = ∑_{j=1}^{n} |G_{j}|d_{j} ≥ ∑_{j=1}^{n} ϱ(S_{j})d_{j}
≥ q(N) ∑_{j=1}^{n} r(S_{j})d_{j} ≥ q(N) ∑_{j=1}^{n} |O_{j}|d_{j} = q(N) ∑_{j=1}^{n}(|O_{j}| − |O_{j−1}|)w(s_{j})
= q(N) · w(O_{n})

Vorlesung am 21.11.2007 26

Flüsse

4.1 Definitionen

Definition (Netzwerk) Ein Tupel (V, A, s, t, c) mit einem Digraphen (V, A), s ≠ t ∈ V und c : A → ℝ_{+} ist ein Netzwerk. O.B.d.A. sei A = V × V. (Den Fall A ⊂ V × V kann man simulieren, indem man c(x, y) = 0 für alle (x, y) ∉ V setzt.)

Definition (Fluss) Sei N = (V, A, s, t, c) ein Netz und f : A → ℝ_{+}. f ist ein (s − t)-Fluss in N, wenn:

1. ∀(x, y) ∈ A : f(x, y) ≤ c(x, y)

2. ∀x ∈ V \ {s, t} : ∑_{y∈N^{+}(x)} f(x, y) = ∑_{y∈N^{−}(x)} f(y, x)

Definition (Wert eines Flusses) Wir bezeichnen mit val(f) = ∑_{x∈N^{+}(s)} f(s, x) − ∑_{x∈N^{−}(s)} f(x, s) den Wert eines Flusses.

4.2 Maximale Flüsse

Unser Ziel: Maximale Flüsse Gegeben ist ein Netzwerk N. Gesucht ist ein maximales f, d.h. ein Fluss f mit der Eigenschaft val(f) ≥ val(f′) für alle Flüsse f′.

Definition (Schnitt, Kapazität) Sei N = (V, A, s, t, c) ein Netzwerk und x ⊆ V, s ∈ X, t ∉ X. Dann ist X ein s − t-Schnitt. Wir definieren cap(X) = ∑_{x∈X,y∈N^{+}(x)\X} c(x, y) als die Kapazität des Schnittes.

Lemma 4.1. (Fluss ≤ Kapazität) Sei N = (V, A, s, t, c) ein Netzwerk, f ein Fluss und X ein s − t-Schnitt. Dann gilt val(f) ≤ cap(X).

Beweis:

\begin{aligned}val(f) & = ∑_{x∈N^{+}(s)} f(s, x) − ∑_{x∈N^{−}(s)} f(x, s) =^{t∉X} ∑_{y∈X}(∑_{x∈N^{+}(y)} f(y, x) − ∑_{x∈N^{−}(y)} f(x, y)) \\ & = ∑_{y∈X,x∈N^{+}(y)} f(x, y) − ∑_{y∈X,x∈N^{−}(y)} f(y, x) \end{aligned}

Alle Kanten (a, b) ∈ X × X erscheinen in ∑_{y∈X,x∈N^{+}(y)} f(x, y) (im Fall von y = a, x = b) als auch in ∑_{y∈X,x∈N^{−}(y)} f(y, x) (im Fall von y = b, x = a). ⇒ f(a, b) hebt sich in der letzten Gleichung für alle (a, b) ∈ X × X auf.

4.2. MAXIMALE FLÜSSE  KAPITEL 4. FLÜSSE

\begin{aligned}⇒ val(f) & = ∑_{y∈X,x∈N^{+}(y)\X} f(y, x) − ∑_{y∈X,x∈N^{−}(y)\X} f(x, y) \\ & ≤ ∑_{y∈X,x∈N^{+}(y)\X} f(y, x) ≤ ∑_{y∈X,x∈N^{+}(y)\X} c(y, x) = cap(X) \end{aligned}

Bemerkung (LP-Dualität) Gegeben sind c ∈ ℝ^{n}, A ∈ ℝ^{m×n}, b ∈ ℝ^{m}. Gesucht ist x ∈ ℝ^{n} mit ∀i = 1, ..., m : (Ax)_{i} ≤ b_{i}, sodass ⟨c, x⟩ maximal ist. Angewendet auf unser Problem wollen wir val(f) = ∑_{x∈N^{+}(s)} f(s, x) − ∑_{x∈N^{−}(s)} f(x, s) maximieren, sodass f ein Fluss ist. Die Fluss-Eigenschaft stellen wir durch eine Matrix A dar, welche wie folgt definiert ist:

A = ( \begin{matrix}+1 & +1 & +1 & & & & −1 & −1 & −1 \\ −1 & −1 & −1 & & & & +1 & +1 & +1 \\ ⋮ & ⋮ & ⋮ & & ⋮ & & ⋮ & ⋮ & ⋮ \\ 1 & & & & & & & & 0 \\ . & . & . \\ . & . & . \\ & & & . & . & . \\ . & . & . \\ . & . & . \\ 0 & & & & & & & & 1 \end{matrix} )  Die Spaltenindizes sind Elemente aus V × V. Mit dem oberen Teil der Matrix sorgen wir für die Flusserhaltung, d.h. in jeden Knoten fließt genau so viel hinein, wie aus dem Knoten her- aus fließt. Dabei wird jeder Knoten durch zwei Zeilen dargestellt. In der ersten Zeile schreiben wir für jede eingehende Kante eine 1, für jede ausgehende Kante eine −1 und für alle ande- ren Kanten eine 0 in die Matrix. In der zweiten Zeile schreiben wir die negierten Einträge der ersten Zeile. Mit dem unteren Teil legen wir die Kapazität der Kanten fest. Hier schreiben wir einfach die Einheitsmatrix hinein.

Weiterhin definieren wir b durch b^{t} = (0, ..., 0|c) wobei c die Beschränkung der Kanten aus der Definition des Netzwerks ist.

Definition (Restnetzwerk) Sei N = (V, A, s, t, c) ein Netzwerk, o.B.d.A. A = V ×V. Sei f : A → ℝ_{+} ein Fluss auf N. O.B.d.A. setzen wir f(y, x) = 0, wenn f(x, y) > 0 gilt. Beispiel:

\xymatrix{x \ar[r]^{5} & y \ar[l]^{3} & ↝ & x \ar[r]^{2} & y \ar[l]^{0}}

Das entstehende f′ ist ein Fluss mit val(f′) = val(f). Dann ist N_{f} = (V, A, s, t, c_{f}) mit

c_{f}(x, y) = \{ \begin{matrix}c(x, y) & , falls f(x, y) = f(y, x) = 0 \\ c(x, y) − f(x, y) & , falls f(x, y) > 0 \\ c(x, y) + f(x, y) & , falls f(y, x) > 0 \end{matrix} das Restnetzwerk von N bezüglich f.

Beispiel (Restnetzwerk) Gegeben sei das folgende Netzwerk:

\xymatrix{ & • \ar[r]^{3} \ar[dr]^{4/5} & • \ar[dr]^{2} \\ s• \ar[ur]^{4/4} \ar[r]_{2} & • \ar[r]_{3} \ar[ur]^{5} & • \ar[r]_{4/4} & t}

Das Restnetzwerk ist dann:

\xymatrix{ & • \ar[r]^{3} \ar[dr]^{1} & • \ar[dr]^{2} \\ s• \ar[ur]^{0} \ar[r]_{2} & • \ar[r]_{3} \ar[ur]^{5} & • \ar[r]_{0} & t}

KAPITEL 4. FLÜSSE  4.2. MAXIMALE FLÜSSE

Vorlesung am 23.11.2007 Lemma 4.2. Sei N = (V, A, s, t, c) ein Netzwerk und f ein Fluss. Sei P ein Pfad im Restnetzwerk N_{f} mit δ = min_{e∈P} c_{f}(e) > 0. Dann kann f entlang P um δ erhöht werden.

Beweis: O.B.d.A. f(x, y) > 0 ⇒ f(y, x) = 0. Wir definieren einen neuen Fluss f′ durch:

1. (x, y), (y, x) ∉ P ⇒ f′(x, y) = f(x, y), f′(y, x) = f(y, x)

2. (x, y) ∈ P, f(y, x) > δ ⇒ f′(x, y) = 0, f′(y, x) = f(y, x) − δ

3. (x, y) ∈ P, f(y, x) ≤ δ ⇒ f′(x, y) = f(x, y) + δ − f(y, x), f′(y, x) = 0

Zu zeigen: f′ ist ein Fluss:

1. Zulässigkeit

Nachrechnen und Definition eines Restnetzwerks.

2. Flusserhaltung

Die Flusserhaltung ist für alle v ∈ V \ V (P) trivial, da f ein Fluss ist.

∀v ∈ V (P) \ {s, t}∃x, y ∈ V (P) : (x, v) ∈ P, (v, y) ∈ P

Sowohl entlang (x, v) als auch entlang (v, y) wurde der Fluss um δ erhöht. Damit ist die Flusserhaltung gegeben.

Definition (Algorihtmus: Ford-Fulkerson) Sei N = (V, A, s, t, c). void FordFulkerson(N = (V, A, s, t, c)){

f = 0;

while(∃s − t-Pfad P in N_{f})

augmentiere f entlang P um δ; }

Satz 4.1. (FordFulkerson terminiert) Für ganzzahlige Kapazitäten terminiert FordFulkerson nach höchstens O(∑_{(x,y)∈A} c(x, y)) vielen Iterationen.

Beweis: Wenn c und f ganzzahlig sind, dann gilt δ = min_{e∈P} c(e) ∈ ℕ für jeden s − t-Pfad in N_{f}. Dann ist f′, der entlang um δ augmentierte Fluss, ebenfalls ganzzahlig. ⇒ In im Augmentationsschritt des Algorithmus’ wird in jeder Iteration der Fluss um mindestens 1 augmentiert. Frage: Terminiert FF mit einem maximalen Fluss?

Es wird sich später zeigen: Ja!! ☺

Satz 4.2. (Max-Flow-Min-Cut) Sei N = (V, A, s, t, c) ein Netzwerk. Dann gilt: max_{f istFluss} val(f) = min_{X ist s−t−Schnitt} cap(X).

Beweis:

1. ≤ wurde bereits gezeigt.

2. ≥

N_{f} ist nicht zusammenhängend, es existiert kein s − t-Pfad.

Sei X = {v ∈ V |v ist in der selben Komponente wie s in N_{f}}, d.h. X ist s − t-Schnitt.

Behauptung: f(x, y) = c(x, y) > 0 für alle (x, y) ∈ A mit x ∈ X und y ∉ X (⇒ O.B.d.A. f(y, x) = 0).

Beweis: Falls f(x, y) < c(x, y), dann wäre (x, y) ∈ A_{f} bzw. c_{f}(x, y) > 0.

⇒ y ∈ X ⇒↯

Behauptung: ∀(y, x) ∈ A, y ∉ X, x ∈ X : f(y, x) = 0

Beweis: ✓

Behauptung: ∀ Flüsse und X ⊆ V, s − t-Schnitt

val(f) = ∑_{(x,y)∈A,x∈X,y∉X} f(x, y) − ∑_{(x,y)∈A,x∈X,y∉X} f(y, x).

Beweis: Induktion über |X|

(a) |X| = 1 ⇒ X = {s} ⇒ Behauptung gilt nach Definition

(b) X = X′ ∪ {x}, x ≠ t

[figure: •; •; •; •; •; •; •; •; X; •x; −; a; −; a; b; b; X ∪ {x}; •x; a; a; +; b; +; b; •; +; d; •; c; •; d; •; −; c; •; +; d; •; c; •; d; •; −; c]

Durch die Flusserhaltung haben wir a + b = c + d, d.h. d − a = b − c. Hieraus folgt sofort die gewünschte Gleichheit.

Satz 4.3. FordFulkerson löst das Max-Flow-Problem für ganzzahlige Kapazitäten in O(|A| ∑_{(x,y)∈A} c(x, y)).

Beweis: Laufzeit: Wir haben maximal ∑_{(x,y)∈A} c(x, y) Iterationen. Eine Iteration benötigt O(|A|) für die Berechnung des Restnetzwerks, O(|A|) für die Bestimmung eines s − t-Pfades und O(|A|) für die Erhöhung des Flusses entlang dieses Pfades. Korrektheit: FF terminiert, wenn N_{f} keinen s − t-Pfad enthält. Dann ist X = {v ∈ V |v ist in der selben Komponente wie s} ein Schnitt mit cap(X) = val(f). ⇒ f ist ein maximaler Fluss.

Bemerkung

1. Der Algorithmus kann sehr leicht sehr langsam werden: Zum Beispiel im Netzwerk

\xymatrix{ & • \ar[dd]^{1} \ar[dr]^{1000} \\ s• \ar[ur]^{1000} \ar[dr]_{1000} &  & •t \\  & • \ar[ur]_{1000}}

können wir immer den augmentierenden Pfad mit der 1 auswählen und damit 2000 Iterationen erreichen.

2. Edmonds und Karp haben gezeigt, dass FF für ganzzahlige Kapazitäten eine Laufzeit von O(nm^{2}) hat, wenn man entlang kürzester (Anzahl der Kanten) Pfade augmentiert.

3. Es existieren Natzwerke mit realen Kapazitäten für die der FF-Algorithmus nicht terminiert und nicht gegen den maximalen Fluss konvergiert.

4. Anmerkung des Autors:

Der Algorithmus funktioniert auch bei nicht-ganzzahligen Kantenkapazitäten, wenn eine positive reelle Zahl x existiert, sodass jede Kapazität ein ganzzahliges Vielfaches von x ist. (Für x ≠ 0 multiplizieren wir einfach jede Kantenkapazität mit x^{−1} und erhalten ganzzahlige Kantengewichte. Bei x = 0 ist sowieso jede Kapazität 0, d.h. der Null-Fluss ist auch gleichzeitig der maximale Fluss.)

Vorlesung am 28.11.2007

Definition (geschichtetes Restnetzwerk) Sei N = (V, A, s, t, c) ein Netzwerk und f ein Fluss. GN_{f} = (V′, GA_{f}, s, t, c_{f}) ist ein geschichtetes Restnetzwerk, mit V′ = V_{0} ˙∪... ˙∪V_{k}, wobei V_{0} = {s}, V_{k} = {t} und V_{i} = {v ∈ V |dist(s, v) = i}. dist bezeichnet dabei die ungewichtete, gerichtete Distanz von s nach v in N_{f}. Weiterhin ist GA_{f} die Menge {(x, y)|x ∈ V_{i}, y ∈ V_{i+1}, (x, y) ∈ A_{f}, i = 0, ..., k − 1}. (Es gilt (x, y) ∈ A_{f} ⇔ c_{f}(x, y) > 0.)

Definition (Durchsatz) Sei GN_{f} ein geschichtetes Restnetzwerk und v ∈ V′ \ {s, t}. Der Durchsatz von v ist min{∑_{x∈N_{GN_{f}}^{+} (v)} c_{f}(v, x), ∑_{y∈N_{GN_{f}}^{−} (v)} c_{f}(y, v)}.

Der Durchsatz von s ist ∑_{x∈N_{GN_{f}}^{+} (s)} c_{f}(s, x) und der Durchsatz von t ist ∑_{y∈N_{GN_{f}}^{−} (t)} c_{f}(y, t).

Definition (Algorithmus: Dinic (1)) Fluss MaxFlow(GN_{f} = (V′, GA_{f}, s, t, c_{f})){

g = 0;

while(∃s − t-Pfad in GN_{f}){ v = Knoten geringsten Durchsatzes; pushFlow(v); pullFlow(v); g = g + v.Durchsatz; aktualisiere Kapazitäten in GN_{f}; entferne rekursiv Knoten mit Durchsatz 0 und Kanten mit Kapazität 0;

}

return g; }

void PushFlow(v){ (Queue) Q = {v}; for(x ∈ V′)

x.push = 0 v.push = v.Durchsatz; while(Q ≠ {t}){

u = Q.first;

for((u, x) ∈ GA_{f}){

if(c_{f}(u, x) > u.push){
x.push = x.push + u.push;
u.push = 0;

}else{ x.push = x.push + c_{f}(u, x); u.push = u.push − c_{f}(u, x);

} if(x ∉ Q)

Q = Q + x; if(u.push == 0)

break; }

} }

void PullFlow(v){ (Queue) Q = {v}; for(x ∈ V′)

x.pull = 0 v.pull = v.Durchsatz; while(Q ≠ {s}){

u = Q.first; for((x, u) ∈ GA_{f}){

if(c_{f}(x, u) > u.pull){ x.pull = x.pull + u.pull; u.pull = 0;

}else{ x.pull = x.pull + c_{f}(x, u); u.pull = u.pull − c_{f}(x, u);

} if(x ∉ Q)

Q = Q + x; if(u.pull == 0)

break; }

} }

Lemma 4.3. MaxFlow berechnet einen maximalen Fluss in GN_{f}.

Beweis: Sei e eine Kante, die bei der Berechnung von g aus GN_{f} entfernt wird.

1. e wird saturiert:

⇒ Restkapazität von e ist 0.

⇒ Es gibt keinen Fluss, der über e mehr schickt, als g.

2. Einer der Endknoten v von e hat Durchsatz 0:

⇒ ∄ augmentierender s − t-Pfad, der v und somit e benutzt.

MaxFlow terminiert, falls es keinen s − t-Pfad mehr in GN_{f} gibt. ⇒ ∄ g-augmentierender Pfad in gegebenem GN_{f}.

Definition (Dinic (2)) Fluss Dinic(N){

f ≡ 0;

while(∃s − t-Pfad in GN_{f})

f = f+MaxFlow(GN_{f}); return f;

}

Lemma 4.4. Nach jeder Durchführung der while-Schleife im Dinic-Algorithmus vergrößert sich der s − t-Abstand in GN_{f}.

Beweis: GN_{f} enthält alle kürzesten Pfade zwischen s und t. Ist g ein maximaler Fluss in GN_{f}, dann existiert kein g-augmentierender s − t-Pfad in GN_{f} (der nur Kanten aus GN_{f} benutzt) und ein augmentierender s − t-Pfad in GN_{f+g} hat daher größere Länge.

Satz 4.4. Der Dinic-Algorithmus hat eine Laufzeit von O(n^{3}).

Beweis: Nach letztem Lemma gibt es höchstens n Iterationen der while-Schleife in Dinic. Es reicht also zu zeigen, dass MaxFlow in O(n^{2}) ausgeführt werden kann. Da in jeder Iteration der while-Schleife in MaxFlow mindestens ein Knoten entfernt wird, kann es höchstens n Iterationen geben. In PushFlow/PullFlow werden in der for-Schleife alle bis auf höchstens eine Kante saturiert. ⇒ O(m) für die saturierten Kanten und O(n · n) = O(n^{2}) für partiell saturierte Kanten. ⇒ Gesamtlaufzeit von MaxFlow ist O(m + n^{2}) = O(n^{2}).

Korollar 4.1. Bei 0 − 1-Kapazitäten erreichen wir eine Laufzeit von O(nm).

Beweis: Es gibt keine partiell saturierten Kanten in PushFlow und PullFlow.

Bemerkung Analyse für Dnic mit 0 − 1-Kapazitäten lässt sich verbessern. ⇒ O(n^{\frac{2}{3}} m)

Vorlesung am 30.11.2007 34

Matching

5.1 Größte Matchings

Gegeben: G = (V, E) Gesucht: Größtes Matching

Definition

1. M ⊆ E ist ein Matching, falls ∀e, f ∈ M : e ∩ f = ∅.

2. M ist maximal, falls es kein größeres Matching gibt, welches M enthält.

3. M ist ein größtes Matching, falls |M| ≥ |M′| für alle Matchings M′ in G gilt.

4. Wir definieren ν(G) = |M|, wobei M ein größtes Matching ist.

Beobachtung Sei M ein maximales Matching. ⇒ \frac{ν(G)}{2} ≤ |M| ≤ ν(G). Beweis: Sei M^{∗} ein größtes Matching. ⇒ ∀e ∈ M^{∗} : |e ∩ V (M)| ≥ 1 ⇒ |M^{∗}| ≤ 2|M|

Bemerkung Ein maximales Matching lässt sich mit dem Greedy-Algorithmus in O(m + n) finden.

Satz 5.1. In einem bipartiten Graphen G = (A ˙∪B, E) kann ein größtes Matching in O(n^{2}m) gefunden werden.

Beweis: Wir betrachten das Netzwerk N = (V, F, s, t, c) mit der Kapazität c = 1 auf allen Kanten, V = A ∪ B ∪ {s, t} und F = {(s, a)|a ∈ A} ∪ {(b, t)|b ∈ B} ∪ {(a, b)|{a, b} ∈ E, a ∈ A, b ∈ B}. Sei f ein ganzzahliger Fluss in N. Da der Durchsatz von jedem Knoten in A ˙∪B eins ist, gilt: Für alle x ∈ A ˙∪B existiert höchstens eine Kante (y, z) ∈ A × B, die x enthält und f(x, y) > 0. Damit ist {{a, b} ∈ E|f(a, b) = 1} ein Matching in G → M_{f}. Weiterhin ist |M_{f}| = val(f). Auf der anderen Seite definiert jedes Matching M in G einen Fluss f_{M} in N:

f(x, y) = \{ \begin{matrix}1 & , falls x = s, y ∈ V (M) \\ 1 & , falls \{x, y\} ∈ M \\ 1 & , falls y = t, x ∈ V (M) \\ 0 & , sonst \end{matrix}

5.1. GRÖSSTE MATCHINGS  KAPITEL 5. MATCHING

Es gilt wieder val(f_{M}) = |M|.

\xymatrix{ & • \ar[r] \ar[dr] \ar[ddr] \ar[dddr] & • \ar[dddr] \\  & • \ar[ur] \ar[r] \ar[ddr] \ar[dddddr] & • \ar[ddr] \\  & • \ar[uur] \ar[dr] \ar[dddr] \ar[ddddr] & • \ar[dr] \\ S• \ar[uuur] \ar[uur] \ar[ur] \ar[r] \ar[dr] \ar[ddr] \ar[dddr] & • \ar[r] \ar[uur] \ar[dr] \ar[dddr] & • \ar[r] & t \\  & • \ar[r] \ar[dr] \ar[uur] \ar[uuuur] & • \ar[ur] \\  & • \ar[ur] \ar[dr] \ar[uur] \ar[uuur] & • \ar[uur] \\  & • \ar[r] \ar[ur] \ar[uuuur] \ar[uuuuuur] & • \ar[uuur] \\  & A & B}

Definition Sei M ein Matching in G.

1. Ein Pfad in P in G heißt alternierend, falls die Kanten von P abwechselnd zu M und E \ M gehören:

[figure: •; •; •; •; •]

2. Ein alternierender s − t-Pfad heißt (M-)augmentierend, falls seine Länge mindestens 1 ist und s, t ∉ V (M) gilt.

Satz 5.2. (Berge (1957)) M ist genau dann ein größtes Matching, wenn es keinen M-augmen-tierenden Pfad gibt.

Beweis: Sei M^{∗} ein größtes Matching. ⇒ Δ(H) = Δ(M^{∗} △ M) ≤ 2 ⇒ H ist die kantendisjunkte Vereinigung von Kreisen und Kanten. Weil M^{∗} ein größtes Matching ist, gilt |M| ≤ |M^{∗}|. Daher existieren |M^{∗}|−|M| M-augmentierende Pfade in G. (Dies sind gerade die maximalen ungerade Pfade in H.) ⇒ Falls M kein größtes Matching ist, dann existiert ein M-augmentierender Pfad in G.

Definition (Meta-Matching-Algorithmus) void MetaMatch(){

M = ∅;

while(∃M-augmentierender Pfad P)

augmentiere M entlang P; }

KAPITEL 5. MATCHING  5.1. GRÖSSTE MATCHINGS

Frage Wie

1. finden wir augmentierende Pfade?

2. verifizieren wir, dass keine augmentierende Pfade mehr existieren?

Definition Sei M ein Matching in G = (V, E), sei F ⊆ G Wald. F heißt ungarischer Wald, falls für alle Bäume B in F gilt:

1. Die Wurzel w jedes Baumes ist nicht von M überdeckt, d.h. m ∉ V (M).

2. Jeder Pfad von w zu einem Blatt in B ist alternierend.

3. Alle Blätter haben in B geraden Abstand zur Wurzel w.

Definition (Bipartites Matching) void BipartMatch(){

M = ∅

while(P = AugBipMatching(G, M))

augmentiere M entlang P; }

Path AugBipMatching(G, M){ F = V \ V (M); F.even = F, F.odd = ∅; while(∃{x, y} ∈ E, x ∈ F.even, y ∉ F.odd)

if(y ∉ F.even){ erweitere F um {x, y}, {y, z} ∈ M; F.odd = F.odd ∪ {y}; F.even = F.even ∪ {z};

}else

return augmentierender Pfad(Wurzel(Baum(x)), Wurzel(Baum(y))); return 0;

}

Vorlesung am 05.12.2007

Bemerkung Der Aufwand des Algorithmus ist O(nm): AugBipMatch, was einen Aufwand von O(m) hat, wird nur \frac{n}{2} mal aufgerufen.

Lemma 5.1. (Korrektheit des Algorithmus’) BipartMatch ist korrekt.

Beweis: Sei F ein ungarischer Wald und M^{∗} ein Matching in G. ⇒ |V \ V (M^{∗})| ≥ |F.even| − |F.odd|, da am Ende von AugBipMatch alle Nachbarn von Knoten aus F.even in F.odd liegen. Zu zeigen ist |V \ V (M)| ≤ |F.even| − |F.odd|, wobei M das Matching ist, welches der Algorithmus BipartMatch zurückgibt. Die Anzahl der ungematchten Knoten in M ist gleich der Anzahl der Bäume im ungarischen Wald F, da in jedem Baum nur die Wurzel nicht von M überdeckt ist und M auf V \ (F.even ∪ F.odd) zu jedem Zeitpunkt alle Kanten überdeckt. ⇒ Für alle Bäume T gilt |F.even ∩ V (T)| − |F.odd ∩ V (T)| = 1. ⇒ |V \ V (M)| ist gleich der Anzahl der Bäume in F und diese ist gleich |F.even| − |F.odd|.

Hopcroft-Karp-Algorithmus Wir wollen nun versuchen, einen schnelleren Algorithmus zu konstruieren, indem wir kürzeste Pfade augmentieren.

Definition Sei G ein Graph und M ein Matching in G. Wir definieren l(M) als die Länge des kürzesten M-augmentierenden Pfades in G, falls dieser existiert. Wenn dieser nicht existiert, setzen wir l(M) = ∞.

Lemma 5.2. Sei G ein Graph mit Matching M und P_{1}, ..., P_{t} eine inklusionsmaximale Familie von knotendisjunkten M-augmentierenden Pfaden der Länge l(M). Dann gilt für M′ = M△P_{1}△P_{2}△...△P_{t} die Ungleichung l(M′) > l(M).

Beweis: Sei Q ein M′-augmentierender Pfad in G. Wenn kein solches Q existiert, gilt l(M′) = ∞ > l(M) und wir sind fertig. Sei also M′ kein größtes Matching, d.h. Q existiert. Dann gilt |M′△Q| = t + 1 + |M|. ⇒ Mit Hilfe des Lemmas von Berge erhalten wir die Existenz knotendisjunkter Pfade Q_{1}, ..., Q_{t+1}, sodass M′△Q = M△Q_{1}△...△Q_{t+1}. Die Q_{i} sind dabei sogar augmentierende Pfade in M. ⇒ (t+1)·l(M) ≤ |E(Q_{1})|+...+|E(Q_{t+1})| ≤ |M△(M′△Q)|, da Q_{1}, ..., Q_{t+1} in der symmetrischen Differenz von M und M′△Q enthalten sind. Wir haben weiterhin |M△(M′△Q)| = |E(P_{1})△...△E(P_{t})△E(Q)| wegen M′ = M△P_{1}△...△P_{t}. Schließlich gilt

|E(Q)△ △_{k=1}^{t} E(P_{k})| = |E(Q)△ ⋃_{k=1}^{t} E(P_{k})| = ∑_{k=1}^{t} |E(P_{k})| + |E(Q)| − 2 |E(Q) ∩ ⋃_{k=1}^{t} E(P_{k})| .

1. Fall: Q ist knotendisjunkt von P_{1}, ..., P_{t}.

Wir erhalten aus der Annahme sofort |E(Q)| > l(M) (anderenfalls wäre die Familie P_{1}, ..., P_{t} nicht maximal, da man Q hinzunehmen könnte).

2. Fall: ∃i : V (P_{i}) ∩ V (Q) ≠ ∅

Dann müssen beide Pfade eine Matchingkante in M′ gemeinsam haben, d.h. E(Q)∩E(P_{i}) ≠ ∅.

⇒ |E(Q)| ≥ l(M) + 2

Definition (Hopcroft-Karp-Algorithmus) Matching HopcroftKarp(G = (A ˙∪B, E)){

M = ∅;

while(l(M) < ∞){ S = A \ V (M); T = {v ∈ B|∃ alternierender Pfad von S nach v mit Länge l(M)}; bestimme inklusionsmaximale Menge augmentierender Pfade der Länge l(M); augmentiere entlang dieser Pfade;

}

return M; }

Satz 5.3. Der HK-Algorithmus findet ein größtes Matching in G in O(\sqrt{n}m).

Beweis: Die Korrektheit ist klar. Also zur Laufzeit:

KAPITEL 5. MATCHING  5.2. SCHWERSTES MATCHING

1. Wir haben höchstens O(\sqrt{n}) Iterationen der while-Schleife:

Nach \sqrt{n} Iterationen gilt nach dem obigen Lemma l(M) ≥ \sqrt{n}.

⇒ jeder M-augmentierende Pfad hat mindestens die Länge \sqrt{n}.

Weil es nach dem Korollar zum Berge-Lemma ν(G)−|M| knotendisjunkte M-augmentierende Pfade in G gibt, gilt ν(G) − |M| ≤ \frac{n}{\sqrt{n}} = \sqrt{n}. Daher kann M nur noch \sqrt{n}-mal augmentiert werden.

2. Eine Iteration ist in O(m) realisierbar.

Berechnung von l(M):

void modBFS{ Füge S in die Warteschlange Q ein. while(v ∈ Q.head){

besuche v; for(w ∈ N(v))

if(w ∈ V \ V (M))

l(w) = dist(v) + 1; else

Q.add(w); for(w ∈ N(v) unbesucht, {x, w} ∈ M)

dist(x) = dist(v) + 2; }

}

Die Berechnung von S ist recht einfach und T kann mit der selben modifizierten Breitensuche wie l(M) berechnet werden.

Nun zu den letzten Schritten:

Wir starten in jedem Knoten von T eine Tiefensuche entlang alternierender Pfade, wobei immer der Nachbar gewählt wird, welcher dist(·) verringert und löschen anschließend alle Knoten, die auf dem gefundenen Pfad liegen.

Damit kann dann die gewünschte Laufzeit erreicht werden.

Vorlesung am 07.12.2007

5.2 Schwerstes Matching

Gegeben sei ein Graph G = (V, E) und w : E → ℝ_{+}. Gesucht ist max_{M ist Matching} w(M), wobei das Gewicht von M durch w(M) = ∑_{e∈M} w(e) definiert ist.

Definition c : V → ℝ_{+} ist eine zulässige Knotengewichtung für (G, w), wenn für alle {x, y} ∈ E(G) gilt: w(x, y) ≤ c(x) + c(y).

Lemma 5.3. Sei M ein Matching in G und c eine zulässige Knotengewichtung mit

1. ∀{x, y} ∈ M : w(x, y) = c(x) + c(y)

2. ∀x ∈ V \ V (M) : c(x) = 0

Dann ist M ein schwerstes Matching in (G, w).

5.2. SCHWERSTES MATCHING  KAPITEL 5. MATCHING

Beweis: Sei M′ ein weiteres Matching in G. Dann gilt:

w(M′) = ∑_{e∈M′} w(e) ≤ ∑_{{x,y}∈M′} c(x) + c(y)
≤ ∑_{v∈V} c(v) = ∑_{{x,y}∈M} c(x) + c(y)
= ∑_{{x,y}∈M} w(x, y)
= w(M)

Definition (Algorithmus für schwerstes bipartites Matching) Matching SchwBipMatch(G = (A ˙∪B, E), w){

M = ∅;

for(x ∈ B)

c(x) = 0; for(x ∈ A)

c(x) = max_{e∈E} w(e); repeat

berechne G′ = (A ˙∪B, E′), E′ = {{a, b} ∈ E|w(a, b) = c(a) + c(b)}; augmentiere M zu größtem ungewichteten Matching in G′; berechne entsprechenden ungarischen Wald F in G′; ε = min{c(x) + c(y) − w(x, y)|{x, y} ∈ E, x ∈ A ∩ F.even, y ∈ B \ F.odd}; δ = min{c(x)|x ∈ A ∩ F.even}; for(x ∈ A ∩ F.even)

c(x) = c(x) − min{δ, ε}; for(x ∈ B ∩ F.odd)

c(x) = c(x) + min{δ, ε}; until(δ ≤ ε); return M;

}

Satz 5.4. Der obige Algorithmus findet ein schwerstes Matching in einem bipartiten Graphen in O(n^{\frac{3}{2}} m).

Beweis:

1. Laufzeit

Wir haben höchstens \frac{n}{2} Iterationen und jede Iteration kann mit dem Karp-Algorithmus in O(n^{\frac{1}{2}} m) realisiert werden. Der ungarische Wald kann bei der abgeänderten Breitensuche berechnet werden, wenn wir feststellen, dass l(M) = ∞ gilt.

2. Korrektheit

Ziel:

(a) c ist am Ende der Schleife (bzw. beim Eintritt in dieselbe) immer zulässig.

(b) Weiterhin wird die erste Eigenschaft der Voraussetzung des Lemmas immer erfüllt.

(c) Wenn δ ≤ ε gilt, dann erfüllt c auch die zweite Voraussetzung.

Beweis dieser Eigenschaften:

(a) Induktion über die Iterationen der Schleife.

Bei der ersten Definition von c ist die Eigenschaft zwangsläufig gegeben. Damit ist der Induktionsanfang erledigt und es verbleibt der Induktionsschritt: Kanten {x, y} ∈ E, die bei der Neudefinition von c Probleme bereiten könnten, sind von der Form x ∈ A ∩ F.even, y ∈ B \ F.odd. Nach der Wahl von ε bereiten diese Kanten jedoch keine Probleme mehr.

KAPITEL 5. MATCHING  5.3. SATZ VON HALL

(b) Wir führen wieder eine Induktion durch. Zu Beginn ist diese Eigenschaft erfüllt. Wir haben M ⊆ E′. Im augmentierten Matching M′ gibt es nur Kanten zwischen F.even und F.odd oder zwischen A\F.even und B\F.odd. Für beide Typen von Kanten hat sich nichts an der Summe c(x)+c(y) geändert: Für {x, y} ∈ M′ \E gilt w(x, y) = c(x)+c(y) zu Beginn der Schleife. Nach Neudefinition von c gilt w(x, y) = c(x) + c(y) + min{δ, ε} − min{δ, ε} = c(x) + c(y) bzw. w(x, y) = c(x) + c(y) (weil sich im zweiten Fall nichts an der Definition von c ändert).

(c) Zunächst stellen wir fest, dass jedes x ∈ V, das irgendwann überdeckt wurde, für den Rest des Algorithmus’ überdeckt bleibt. Falls x ∈ B mit c(x) > 0, dann lag x irgendwann in B ∩ F.odd. ⇒ x wurde von dem Matching von F überdeckt. ⇒ x ∈ V (M) am Ende des Algotithmus’. ⇒ ∀x ∈ B \ V (M) : c(x) = 0 Sei x ∈ A \ V (M). ⇒ x ∈ F.even in jeder Iteration, da F.even alle unüberdeckten Knoten aus A enthält und überdeckte Knoten überdeckt bleiben. ⇒ x wurde in jeder Iteration um min{δ, ε} erniedrigt. Wenn δ ≤ ε gilt, dann existiert ein x ∈ A ∩ F.even mit δ = c(x) und c′(x) = 0 (c′ bezeichne die Knotengewichtung nach dem Schleifendurchlauf). Da c(x) = c(y) für alle x, y ∈ A zu Beginn des Algorithmus’ und alle x ∈ A \ V (xM) in jeder Iteration um den selben Wert erniedrigt werden, gilt am Ende des Algorithmus’ c(x) = c(y) für alle x, y ∈ A \ V (M). ⇒ ∃x ∈ A \ V (M) : c(x) = 0, wenn δ ≤ ε ⇒ c(x) = 0 für alle x ∈ A \ V (M).

Mit dem vorhergehenden Lemma erhalten wir, dass das Matching ein schwerstes Matching ist.

5.3 Satz von Hall

Frage: Wann gibt es perfekte Matchings in balancierten bipartiten Graphen G = (A ˙∪B, E)? (Ein Matching heißt perfekt, wenn alle Knoten überdeckt sind.) Allgemeiner: Sei G = (A ˙∪B, E) mit |A| ≤ |B| gegeben. Wann gibt es in diesem Fall ein Matching der Größe \frac{|A|}{2}? Sei M ein Matching, welches A überdeckt. Dann gilt ∀A′ ⊆ A : |N(A′)| ≥ |A′|. (Dies folgt daraus, dass Nachbarn von Knoten aus A wegen V (G) = A ˙∪B nicht in A liegen dürfen. Weil jedoch jeder Knoten aus A vom Matching überdeckt ist, existiert eine Kante, die diesen Knoten als Endpunkt hat. Also hat jeder Knoten aus A mindestens einen Nachbarn, der nicht in A liegt. Weiterhin kann kein Nachbar durch das Matching doppelt überdeckt sein, womit die Behauptung folgt.)

Satz 5.5. (Satz von Hall) Sei G = (A ˙∪B, E) ein bipartiter endlicher Graph und |A| ≤ |B|. Dann gilt die Hallbedingung (|N(A′)| ≥ |A′| für alle A′ ⊆ A) genau dann, wenn ν(G) = |A|, d.h. es existiert ein perfektes Matching.

Beweis:

1. ⇐ ist trivial.

5.4. SATZ VON KÖNIG  KAPITEL 5. MATCHING

2. ⇒

Wir führen eine Induktion über |E|:

Im Fall von |E| = 1 sind wir fertig.

Sei |E| > 1. Dann unterscheiden wir zwei Fälle:

(a) ∀A′ ⊆ A : |N(A′)| > |A′| Sei {x, y} ∈ E. Dann erfüllt G \ {x, y} die Hall-Bedingung und wir sind nach Induktionsvoraussetzung fertig.

(b) ∃A′ ⊆ A : |N(A′)| = |A′|

Sei A′ ≠ ∅ die kleinste solche Menge.

⇒ G[A′, N(A′)] erfüllt die Hall-Bedingung und enthält nach Induktionsvoraussetzung ein Matching der Größe |A′|. Da |N(A′)| = |A′|, gilt G^{∗} = G[A \ A′, B \ N(A′)] erfüllt ebenfalls die Hall-Bedingung. ⇒ ∃ Matching in G^{∗}, welches A \ A′ überdeckt.

5.4 Satz von König

Wir bezeichnen mit τ(G) = min_{S⊆V} {|S||∀e ∈ E : |e ∩ S| ≥ 1} die Überdeckungszahl, d.h. τ(G) ist die Größe der kleinsten Teilmenge von Knoten, mit der Eigenschaft, dass jede Kante des Graphen G (mindestens) einen Knoten aus S enthält.

Bemerkung (Beobachtungen)

1. τ(G) = |V (G)| − α(G)

2. ν(G) ≤ τ(G) ≤ 2ν(G)

Die erste Ungleichung gilt, weil S mindestens einen Knoten jeder Matchingkante enthalten muss.

Die zweite Ungleichung gilt, weil V (M) alle Kanten überdeckt, wenn M ein größtes Matching ist.

Bei bipartiten Graphen gilt links die Gleichheit (siehe Satz von König).

Vorlesung am 12.12.2007

Satz 5.6. (König) Sei G = (A ˙∪B, E) bipartit. Dann gilt ν(G) = τ(G).

Beweis: Sei M ein größtes Matching. Wir definieren U = A \ V (M) und S = {v ∈ A|∃u ∈ U und alternierender u − v-Pfad}. Damit gilt U ⊆ S. Analog zu S definieren wir T = {v ∈ B|∃u ∈ U und alternierender u − v-Pfad} für Knoten v ∈ B. Wir wollen nun zeigen, dass C = (A \ S) ∪ T eine Überdeckung ist. Dafür zeigen wir ∄{x, y} ∈ E : x ∈ S, y ∈ B \ T. Annahme: Eine derartige Kante existiert. Wir unterscheiden nun die folgenden Fälle:

1. {x, y} ∈ M

⇒ x ∈ S \ U

Weil der Pfad, der die Aufnahme von x in die Menge S bedingt hat, über eine Matchingkante zu x führen muss, muss y gerade der Knoten vor x auf diesem Pfad sein.

⇒ y ∈ T ⇒ ↯

KAPITEL 5. MATCHING  5.5. SÄTZE VON BERGE UND TUTTE

2. {x, y} ∈ E \ M

⇒ x ∈ S ⇒ ∃u ∈ U und alternierender u − x-Pfad

⇒ ∃ alternierender u − y-Pfad

(x wird am Ende einer Matchingkante auf dem alternierenden u − x-Pfad besucht. Also können wir diesen Pfad zu einem alternierenden u − y-Pfad verlängern, wenn y noch nicht in diesem Pfad enthalten ist. Wenn y bereits in diesem Pfad enthalten ist, sind wir jedoch sowieso schon fertig.)

⇒ y ∈ T ⇒ ↯

Damit war die obige Annahme falsch und C ist eine Überdeckung. Nun zeigen wir |C| ≤ ν(G). Wir beweisen hierfür ∀e ∈ M : |e ∩ C| ≤ 1: Sei e = {x, y} ∈ M, so dass |e ∩ C| = 2. ⇒ x ∈ A \ S und y ∈ T ⇒ ∃u ∈ U, alternierender u − y-Pfad, sodass die letzte Kante nicht in M ist. Damit existiert auch ein alternierender u − x-Pfad und es gilt x ∈ S, was einen Widerspruch darstellt. Somit folgt die Behauptung |C| ≤ ν(G).

5.5 Sätze von Berge und Tutte

Wir definieren q(G) als die Anzahl der ungeraden Komponenten in G = (V, E). Sei S ⊆ V. q(G−S)−|S| ist dann eine untere Schranke an |V \V (M)| für alle Matchings M: In jeder ungeraden Komponente bleibt zunächst ein Knoten unüberdeckt. Er kann nur überdeckt werden, wenn er mit einem Knoten aus S durch eine Matchingkante verbunden ist. Dies ist jedoch nur möglich, wenn für jede ungerade Komponente auch ein Knoten in S zur Verfügung steht.

Definition Für einen Graphen G = (V, E) definieren wir den Defekt durch def(G) = max_{S⊆V} {q(G\S)−|S|}.

Bemerkung Es gilt 2ν(G) ≤ |V (G)| − def(G): Die untere Schranke, die durch q(G \ S) − |S| gegeben ist, gilt für alle Teilmengen S ⊆ V, also insbesondere für die Teilmenge S, wo q(G \ S) − |S| maximal wird. Für ein größtes Matching muss die Anzahl der unüberdeckten Knoten also ebenfalls mindestens so groß wie diese untere Schranke sein, womit sich die angegebene Abschätzung ergibt.

Satz 5.7. (Berge (1958)) Sei G = (V, E) ein Graph. Dann gilt 2ν(G) = |V (G)| − def(G).

Beweis: Sei S ⊆ V eine größte Menge mit q(G \ S) − |S| = def(G).

1. Behauptung: Alle Komponenten in G \ S sind ungerade.

Wenn K eine gerade Komponente von G \ S ist, dann können wir S vergrößern, indem wir einen Knoten x aus K entfernen: Wir vergrößern S um 1 und erhalten (mindestens) eine weitere ungerade Komponente, weil die Anzahl der Knoten in K \ x ungerade ist.

Also existiert gar kein solches K, wenn S nach dem obigen Kriterium gewählt wurde.

Damit sind alle Komponenten in G \ S ungerade.

2. Behauptung: Sei K eine ungerade Komponente in G \ S und x ∈ V (K). Dann gibt es ein perfektes Matching in K \ x.

Wir beweisen diese Behauptung durch Induktion über |V |:

5.5. SÄTZE VON BERGE UND TUTTE  KAPITEL 5. MATCHING

(a) Induktionsanfang: |V | = 0, 1, d.h. V = ∅ oder V = {x}. Im Fall von V = ∅ kann es gar keine ungeraden Komponenten geben. Im Fall von V = {x} ist die Behauptung offensichtlich wahr, da K \ x durch M = ∅ überdeckt wird.

(b) Sei nun n = |V | ≥ 2 und die Behauptung für alle k < n bewiesen. Es reicht jetzt reicht zu zeigen, dass def(K \ x) = 0. Wir beweisen dies indirekt und nehmen def(K \ x) > 0 an: Sei R ⊆ V (K \ x), so dass q((K \ x) \ R) − |R| = def(K \ x) > 0. Weil |K| ungerade ist, muss |K \ x| gerade sein und es gilt q((K \ x) \ R) ≡_{2} |R|. Damit muss auch def(K \ x) gerade sein, d.h. es gilt def(K \ x) ≥ 2. Wir erhalten q(G \ (S ∪ R ∪ {x})) − |S ∪ R ∪ {x}| ≥ def(G): Es gilt q(G\(S ∪R∪{x})) = q(G\S)−1+q((K \x)\R), weil wir höchstens die ungerade Komponente K verlieren (daher −1), jedoch die neuen ungeraden Komponenten in (K \ x) \ R hinzu nehmen (daher +q(K \ x) \ R). Damit ergibt sich nun die gewünschte Ungleichung:

\begin{aligned}q(G \ (S ∪ R ∪ \{x\})) − |S ∪ R ∪ \{x\}| & = q(G \ S) − 1 + q((K \ x) \ R) − |S| − |R| − 1 \\ & = def(G) + def(K \ x) − 2 ≥ def(G) \end{aligned}

Nach Definition des Defekts von G folgt q(G \ (S ∪ R ∪ {x})) − |S ∪ R ∪ {x}| = def(G). Also haben wir mit S′ = S ∪ R ∪ {x} eine größere Menge als S gefunden, welche die Gleichung q(S′)−|S′| = def(G) erfüllt, was einen Widerspruch zur Wahl von S darstellt. Damit gilt also def(K \ x) = 0. Somit gibt es auch ein perfektes Matching in K \ x.

3. Es existiert eine Menge von Kanten, die genau einen Endpunkt in S haben und deren zweiter Endpunkt in einer der ungeraden Komponenten von G \ S liegt. Zwei Kanten sollen dabei nicht in der gleichen ungeraden Komponente von G \ S enden.

Wir betrachten den Hilfsgraphen B = (S ˙∪{ungerade Komponenenten von G \ S}, F) mit der Kantenmenge F = {{x, K}|x ∈ S, ∃{x, y} ∈ E, y ∈ V (K)}. Wir wollen nun zeigen, dass ein Matching in B existiert, welches S überdeckt.

Beweis: Nach dem Satz von Hall reicht es aus zu zeigen, dass ∀S′ ⊆ S : |N_{B}(S′)| ≥ |S′|.

Sei S′ ⊆ S mit |S′| > |N_{B}(S′)|.

⇒ q(G \ (S \ S′)) ≥ q(G \ S) − |N_{B}(S′)| > q(G \ S) − |S′|

(Ausgehend von q(G\S) könnten wir für jede ungerade Komponente verlieren, die mit einem Knoten aus S′ verbunden ist. Dies sind jedoch höchstens N_{B}(S′) Komponenten.)

⇒ q(G \ (S \ S′)) − |S \ S′| > q(G \ S) − |S′| − |S \ S′| = q(G \ S) − |S| = def(G)

Dies stellt einen Widerspruch zur Definition von def(G) dar, d.h. es muss |S′| ≤ |N_{B}(S′)| für alle S′ ⊆ S gelten.

Mit 1. erhalten wir, dass alle Komponenten von G \ S ungerade sind. Weiterhin haben wir mit 3., dass wir q(G \ S) Kanten finden können, die S überdecken und genau einen Endpunkt in S haben. Der andere Endpunkt liegt dann jeweils in einer ungeraden Komponente. Mit 2. finden wir dann auch ein Matching, was die noch unüberdeckten Knoten der ungeraden Komponenten überdeckt. Wenn es ungerade Komponenten gibt, wo kein Knoten durch eine Kante mit genau einem Endpunkt in S überdeckt ist, so können wir einen beliebigen Knoten aus dieser Komponente auswählen und ein perfektes Matching für den Rest der Komponente finden. Somit gibt es ein Matching, dass |V | − q(G \ S) + |S| = |V | − def(G) Knoten überdeckt, d.h. es gilt |V (G)| − def(G) ≤ 2ν. Mit der vorhergehenden Bemerkung haben wir die Gleichheit 2ν(G) = |V (G)| − def(G).

Vorlesung am 14.12.2007

Eulertouren, Hamiltonkreise

6.1 Eulertouren

Definition Ein Graph G ist eulersch, falls es einen Zykel gibt, der jede Kante von G genau einmal enthält. Satz 6.1. Wenn G = (V, E) zusammenhängend ist, sind die folgenden Aussagen äquivalent:

1. G ist eulersch.

2. Für alle v ∈ V ist der Grad von v gerade.

3. E ist die kantendisjunkte Vereinigung von Kreisen. Beweis:

1. (1) ⇒ (2) Jeden Knoten, den man mit dem Pfad betritt, muss man auch wieder verlassen. Dafür sind bei jedem Besuch 2 Kanten nötig, d.h. die Anzahl der Kanten in jedem Knoten ist gerade.

2. (2) ⇒ (3) Wir führen eine Induktion über |E| durch. Da δ(G) ≥ 2, existiert ein Kreis C in G. ⇒ G′ = (V \ {v ∈ V |d(v) = 2, v ∈ V (C)}, E \ E(C)) erfüllt immer noch die Bedingung. ⇒ ∃C_{1}, ..., C_{k} Kreise: E \ E(C) = ˙⋃_{i=1}^{k}C_{i}. ⇒ E = E(C) ˙∪ ⋃_{i=1}^{k} E(C_{i})

3. (3) ⇒ (1) Sei E = ˙⋃_{i=1}^{k}E(C_{i}), C_{i} Kreis in G. Wir führen nun eine Induktion über k durch:

(a) Im Fall k = 1 sind wir fertig.

(b) k → k + 1 Sei G′ = G \ C_{k+1}. Für alle Zusammenhangskomponenten K in G′ gilt V (K) ∩ V (C_{k+1}) ≠ ∅. Sei v_{k} ∈ V (K) ∩ V (C_{k+1}) beliebig. Für alle K existiert nun I_{k} ⊆ {1, ..., k}, sodass E(K) = ⋃_{i∈I_{k}} E(C_{i}). ⇒^{I.V.} ∃ Eulertour U_{k} in K ⇒ G ist eulersch: Beginne mit einem Knoten auf C_{k+1} und laufe den Kreis C_{k+1} ab. Für jedes k füge U_{k} an den Knoten V_{k} ein.

6.2. HAMILTONKREIS  KAPITEL 6. EULERTOUREN, HAMILTONKREISE

Bemerkung

1. (a) Zusammenhang lässt sich mittels DFS in O(m) testen.

(b) Die Eigenschaft 2. kann ebenfalls in O(m) verifiziert werden.

⇒ in O(m) kann getestet werden, ob ein gegebener Graph G eulersch ist.

2. Wenn G eulersch ist, dann findet der folgende (auf der 3. Eigenschaft basierende) Algorithmus eine Eulertour in O(m) Zykel Euler(v ∈ V (G(V, E))){

while(∃{v, w} ∈ E unmarkiert){ markiere({v, w}); Euler(w); Tour=Tour+{v, w};

}

return Tour; }

3. Es gilt auch alles für Multigraphen.

6.2 Hamiltonkreis

Gegeben ist ein Graph G und gesucht ist ein spannender Kreis in G, bzw. die Existenz desselben. Wir wissen bereits, dass dieses Problem NP -vollständig ist. Frage: Gibt es (einfache) hinreichende Kriterien für Hamiltonkreise? Wenn ein Graph einen Hamiltonkreis einthält, nennen wir ihn hamiltonisch.

Lemma 6.1. Sei G = (V, E) und x, y ∈ V, {x, y} ∉ E und d(x) + d(y) ≥ n. Dann ist G genau dann hamiltonisch, wenn G + {x, y} hamiltonisch ist.

Beweis:

1. ⇒ ✓

2. ⇐ Angenommen, G + {x, y} ist hamiltonisch und sei C ein Hamiltonkreis. Wir unterscheiden dann die folgenden Fälle:

(a) {x, y} ∉ E(C). Dann ist C Hamiltonkreis in G.

(b) {x, y} ∈ E(C).

Sei C = x, y, v_{1}, ..., v_{n−2}.

Angenommen, es existiere ein i ∈ {1, ..., n − 2}, so dass {x, v} ∈ E und {y, v_{i+1}} ∈ E. ⇒ ∃ Hamiltonkreis (x, v_{i}, v_{i−1}, ..., v_{1}, y, v_{i+1}, ..., v_{n−2}, x) in G. Falls kein solches i existiert, dann gilt

d_{G}(y) ≤ n − 1 − \underbrace{1}_{\{x,y\}∉E} −(  \underbrace{d_{G}(x)}_{∀\{x,v_{i}\}∈E:\{y,v_{i+1}∉E\}} − \underbrace{1}_{für \{x,v_{n}\} ist \{y,x\}∉E}).

⇒ d_{G}(y) + d_{G}(x) ≤ n − 1 ⇒ ↯

KAPITEL 6. EULERTOUREN, HAMILTONKREISE  6.2. HAMILTONKREIS

Definition Sei G = G_{0}, G_{1}, ..., G_{k} ein maximale Sequenz von Graphen, wobei G_{i+1} = G_{i} + {x, y} für eine Kante {x, y} ∉ E(G) und d_{G_{i}}(x) + d_{G−i}(y) ≥ n. Dann ist G_{k} der Hamiltonabschluss von G.

Lemma 6.2. (Eindeutigkeit des Hamiltonabschlusses) Der Hamiltonabschluss ist eindeutig.

Beweis: Seien G_{1} und G_{2} zwei verschiedene Hamiltonabschlüsse von G. Sei G_{1} = G + e_{1} + ... + e_{k} und i der kleinste Index, so dass e_{i} ∉ E(G_{2}). Der Index i existiert, da sonst G_{1} ⊂ G_{2} ⇒ ∃f = {x, y} ∈ E(G_{2}), f ∉ E(G_{1}), welches wir zu G_{1} hätten hinzunehmen können. Da e_{1}, ..., e_{i−1} ∈ E(G_{2}) folgt e_{i} = {x, y} mit d_{G_{2}}(x) + d_{G_{2}}(y) ≥ d(x) + d(y) ≥ n. ⇒ e_{i} kann zu G_{2} hinzugefügt werden, was einen Widerspruch zur Maximalität von G_{2} darstellt.

Satz 6.2. (Bondy, Chvátal (1976)) Der Hamiltonabschluss von G ist genau dann hamiltonisch, wenn G hamiltonisch ist.

Beweis: Induktion mit Verwendung des ersten Lemmas über die hinzugefügten Kanten.

Satz 6.3. (Ore (1960)) Sei |V (G)| ≥ 3 und ∀{x, y} ∉ E(G) : d(x) + d(y) ≥ n. Dann ist G hamiltonisch.

Beweis: Hamiltonabschluss von G ist K_{n} mit n = |V (G)|. Mit dem Satz von Bondy und Chvátal folgt die Behauptung.

Satz 6.4. (Dirac (1952)) Sei |V (G)| ≥ 3 und δ(G) ≥ \frac{n}{2}. Dann ist G hamiltonisch.

Beweis: Für alle \{x, y\} ∉ E(G) gilt d(x) + d(y) ≥ δ(G) + δ(G) ≥ 2 · \frac{n}{2} = n. Mit dem vorherigen Satz von Ore folgt dann die Behauptung.

Vorlesung am 19.12.2007

Satz 6.5. (Chvátal-Erdős (1972)) Sei |V (G)| ≥ 3 und κ(G) ≥ α(G). Dann ist G hamiltonisch.

Beweis:

1. Fall: α(G) = 1

⇒ G ist eine Clique, d.h. G ist hamiltonisch.

2. Fall: κ(G) ≥ α(G) ≥ 2.

Annahme: G ist nicht hamiltonisch.

Sei C = (v_{0}, ..., v_{|C|−1}, v_{|C|}) ein größter Kreis in G. Weil wir G als nicht hamiltonisch angenommen haben, gilt |C| < n = |V (G)|. Weiterhin seien S eine Zusammenhangskomponente in G − C, T = C ∩ N(S) und T′ = {v_{i}|v_{i−1} ∈ T }.

Behauptung: T′ ist eine unabhängige Menge in G.

Sei {v_{i}, v_{j}} ∈ E(G) und v_{i}, v_{j} ∈ T′.

Dann ist C′ = (v_{j}, v_{i}, ..., v_{i+1}, ..., v_{j−1}, P, v_{i−1}, v_{i−2}, ..., v_{j}) ein längerer Kreis als C, wobei P v_{i} und v_{i−1} über einen Pfad in S verbindet, d.h. P = (s_{1}, ..., s_{k}) mit s_{1} ∈ N(V_{j−1}) und s_{k} ∈ N(v_{i−1}). P existiert, da v_{i−1}, v_{j−1} ∈ T = C ∩ N(S) und S zusammenhängend ist.

Behauptung: Es existieren keine w ∈ T′, v ∈ S mit {w, v} ∈ E(G).

Sei v_{j} ∈ T′, s ∈ S : {v_{j}, s} ∈ E(G).

⇒ v_{j−1} ∈ T ⇒ ∃s′ ∈ S : {v_{j−1}, s′} ∈ E(G)

Weil S zusammenhängend ist, existiert ein s−s′-Pfad P in S, womit wir einen längeren Kreis als C finden, nämlich C′ = (v_{0}, ..., v_{j−1}, P, v_{j}, v_{|C|−1}, v_{0}).

T ist also eine trennende Menge, d.h. es gilt |T | ≥ κ(G).

Sei nun s ∈ S beliebig. Dann gilt α(G) ≥ |T′ ∪ {s}| > |T | ≥ κ(G), womit wir einen Widerspruch zur Voraussetzung erhalten.

Es folgt S = ∅, d.h. C ist ein Hamiltonkreis.

Bemerkung Die Umkehrung des Satzes gilt nicht, d.h. es gibt Graphen mit |V (G)| ≥ 3, die hamiltonisch sind, jedoch nicht die Eigenschaft κ(G) ≥ α(G) nicht aufweisen: Ein Beispiel ist der Kreis mit 6 Knoten, d.h. C_{6}. Wir haben hier |V (C_{6})| = 6 ≥ 3 und α(C_{6}) = 3 > 2 = κ(C_{6}).

Bemerkung Der Beweis des Satzes von Chvátal und Erdős ist konstruktiv, d.h. er liefert einen O(nm) Algorithmus, um in Graphen mit κ(G) ≥ α(G) einen Hamiltonkreis zu finden.

Satz 6.6. (Ore ⇒ Chvátal-Erdős (Bondy)) Falls für alle {x, y} ∉ E(G) die Ungleichung d(x) + d(y) ≥ n gilt, dann gilt auch κ(G) ≥ α(G).

Beweis: Sei S eine größte stabile Menge und A eine kleinste trennende Menge.

1. Fall: S ⊆ A

⇒ α(G) = |S| ≤ |A| = κ(G)

2. Fall: S ⊈ A

Sei X eine Zusammenhangskomponente in G−A mit S∩X ≠ ∅, x ∈ S∩X und Y = V \(A∪X).

Wir haben Y ≠ ∅, da G − A mindestens 2 Zusammenhangskomponenten hat.

(a) S ∩ Y = ∅, d.h. x ∈ S \ A ⊆ X Sei y ∈ Y beliebig. Dann gilt d(x) ≤ |(A ∪ X) \ S, weil x ∈ X gilt und damit x keine Nachbarn in Y haben darf. Weiterhin ist S eine stabile Menge, womit x auch keine Nachbarn in S haben darf. Es sind also nur noch Nachbarn in (V \ S) \ Y = (A ∪ X) \ S möglich. Weiterhin gilt d(y) ≤ |A|+|Y |, da y keine Nachbarn in X haben kann (sonst wäre y ∈ X, weil X zusammenhängend ist). Damit verbleiben nur Nachbarn in V \ X = A ∪ X. ⇒ n ≤ d(x) + d(y) ≤ |(A ∪ X) \ S| + |A| + |Y | = |A \ S| + |X \ S| + |A| + |Y | Falls |A| < |S| gilt, folgt der folgende Widerspruch:

n ≤ |(A ∪ X) \ S| + |A| + |Y | = |X \ S| + |A \ S| + |A| + |Y |

= |X \ S| + |A| − |S ∩ A| + |A| + |Y | < |X \ S| + |S| − |S ∩ A| + |A| + |Y | = |X \ S| + |S \ A| + |S ∩ A| − |S ∩ A| + |A| + |Y | = |X \ S| + |S \ A| + |A| + |Y | = |(X ∪ S) \ A| + |A| + |Y | = |X| + |A| + |Y | = n Also haben wir |A| ≥ |S|

KAPITEL 6. EULERTOUREN, HAMILTONKREISE  6.3. TSP
(b) S ∩ Y ≠ ∅

Sei y ∈ S ∩ Y.

Wir erhalten d(x) ≤ |X \S|+|A\S| weil x keine Nachbarn in Y (weil sonst der Nachbar von x ebenfalls in X sein müsste) und auch keine Nachbarn in S (S ist eine stabile Menge) haben kann. Es bleiben also nur noch Nachbarn in (X ∪A)\S = (X \S) ˙∪(A\S). Weiterhin haben wir d(y) ≤ |A\S|+|Y \(S ∩X)| ≤ |A\S|+|Y \S|, da y nur Nachbarn in Y \ (X ∩ S) und A \ S haben kann.

\begin{aligned}⇒ n & ≤ d(x) + d(y) ≤ |X \ S| + |A \ S| + |A \ S| + |Y \ S| \\ & = |V \ S| + |A \ S| ≤ |V \ S| + |A| = n − |S| + |A| \end{aligned}

⇒ |S| ≤ |A|

Vorlesung am 07.01.2008

6.3 TSP

Gegeben ist ein vollständiger Graph G = (V, E) mit Kantengewichten c : E → ℝ und eine Zahl k. Gefragt ist nun, ob in G ein Hamiltonkreis existiert, der eine Länge von höchstens k hat.

TSP Gegeben: (K_{n}, w), w : E(K_{n}) → ℝ_{≥0}. Gesucht: Hamiltonkreis mit minimalem Gewicht.

1. Das TSP (Traveling Salesman Problem) lässt sich nicht mit polynomiellem Aufwand auf einen konstanten Faktor approximieren, falls P ≠ NP gilt.

2. Metrische TSPs lassen sich auf einen Faktor von \frac{3}{2} approximieren. Ein TSP heißt metrisch, wenn die Dreiecksungleichung w(a, c) ≤ w(a, b) + w(b, c) für alle Knoten a, b, c gilt.

Satz 6.7. (9.1, Karp 1972) TSP ist NP-schwer.

Beweis: Wir reduzieren das Problem des Hamilton-Kreises auf das TSP. Sei G = (V, E) eine Hamilton-Kreis-Probleminstanz.

Wir konstruieren G′ als vollständigen Graphen mit Kantengewichten w(e) = \{ \begin{matrix}1 & , e ∈ G \\ 2 & , e ∉ G \end{matrix} und

k = |V |. G ist genau dann hamiltonisch, wenn G′ eine TSP-Tour der Länge |V | hat.

Praktisch relevante Instanzen für TSP

1. Metrisches TSP

Die Gewichtsfunktion erfüllt die Dreiecksungleichung: ∀x, y, z ∈ V : c(x, y)+c(y, z) ≥ c(x, z).

2. Rektlineares TSP

Knoten in ℝ^{2} und Abstände entsprechen der L_{1}- (Manhattan-) Norm. Dieses TSP ist ein metrisches TSP.

3. Euklidisches TSP

Knoten in ℝ^{2} und Abstände entsprechen der L_{2}- (euklidischen-) Norm. Dieses TSP ist ebenfalls metrisch.

Korollar 6.1. (9.2) Metrische TSPs sind NP-schwer.

6.4. APPROXIMATION  KAPITEL 6. EULERTOUREN, HAMILTONKREISE

Beweis: Die Reduktion aus dem Beweis, dass allgemeine TSPs NP-schwer sind, erzeugt ein metrisches TSP.

Lemma 6.3. (93: Garey, Graham, Johnson (1976)) Rektlineare und euklidische TSPs sind NP-schwer.

(ohne Beweis)

6.4 Approximation

Definition (Approximationsalgorithmus, Approximationsgüte) Sei Q ⊆ I ×S ein Optimierungsproblem mit Instanzenmenge I und Lösungsmenge S. Sei f : S → ℝ eine Bewertungsfunktion. Ein Approximationsalgorithmus A für Q ist ein Algorithmus, der für jedes i ∈ I eine Lösung s ∈ S mit (i, s) ∈ Q liefert. Den Wert f(s) der Lösung, die A für i liefert, bezeichnen wir mit A(i). Es sei Q ein Minimierungsproblem. A hat Approximationsgüte c, falls A(i) ≤ cf(s^{∗}), wobei s^{∗} die optimale Lösung der Instanz i ist, gilt.

Satz 6.8. (94: Sahni, Gonzalez (1976)) Falls es einen polynomiellen Approximations-Algorith-mus mit Approximationsgüte r ∈ ℕ für das TSP gibt, so gilt P = NP.

Beweis: Annahme: Es gibt r ∈ ℝ_{≥1}, so dass der polynomielle Approximationsalgorithmus A für ein TSP mit der Approximationsgüte r existiert. Sei G = (V, E) eine Instanz für das Himoltonkreis-Problem.

Wir definieren G′ als den vollständigen Graphen mit w(e) = \{ \begin{matrix}1 & , e ∈ G \\ r|V | & , e ∉ G \end{matrix} . Ist G hamiltonisch,

so hat G′ eine TSP-Tour der Länge |V |. Ansonsten muss jede TSP-Tour in G′ eine Kante der Länge r|V | benutzen und hat damit eine größere Länge als r|V |. Damit folgt A(G′) ≤ r|V | ⇔ G ist hamiltonisch.

Proposition 6.1. (96) Eine optimale TSP-Tour ist mindestens so lang wie ein minimalspannender Baum.

Beweis: Entferne aus TSP eine Kante und erhalte einen Baum, der mindestens so lang wie ein MST ist.

Definition (MST-Heuristik) Wir berechnen zunächst einen minimalspannenden Baum und erzeugen darauf eine Rundtour, in dem wir die Knoten in der Reihenfolge besuchen, in der wir sie bei einer Tiefensuche besuchen würden. Anschließend wählen wir Knoten aus, die mehrfach besucht wurden, entfernen die überzählen Besuche und ersetzen diese durch Abkürzungen zwischen dem Vorgänger und Nachfolger des mehrfach besuchten Knotens.

Lemma 6.4. (97) Die MST-Heuristik hat (bei metrischen TSPs) eine Approximationsgüte von 2.

Beweis: Sei MST Heur(I) die Länge einer Lösung der MST-Heuristik auf einer Instanz I. OP T (I) sei die Länge der optimalen Lösung. MST (I) sei die Länge eines minimal spannenden Baumes auf I. Es gilt MST Heur(I) ≤ 2 · MST (I) ≤ 2 · OP T (I). ⇒ MST Heur(I) ≤ 2 · OP T (I)

TODO Christofides-Heuristik?

Vorlesung am 16.01.2008

Färbungen

7.1 Färbungen

Definition (Knotenfärbung) Für einen Graphen G = (V, E) ist f : V → ℕ eine Färbung, falls f(x) ≠ f(y) für alle {x, y} ∈ E gilt. f ist eine k-Färbung, falls |f(V)| ≤ k. χ(G) = min{k ∈ ℕ|∃k−Färbung von G} ist die chromatische Zahl.

Satz 7.1. χ(G) zu ermitteln ist NP -vollständig, falls χ(G) ≥ 3.

(ohne Beweis)

Definition (Greedy Col) Färbung Greedy Col(G = (V, E)){

for(v ∈ V)

färbe v mit der kleinsten Farbe die in N(v) nicht vorkommt; }

Satz 7.2. (Laufzeit) Greedy Col findet eine Färbung mit höchstens Δ(G) + 1 Farben in linearer Zeit.

Beweis: Wir initialisieren A[1, ..., n] mit 0. Für alle Knoten in v ∈ V und für alle v ∈ N(i) mit f(v) ≠ 0 setzen wir A[f(v)] = i. Anschließend finden wir den kleinsten Index j, so dass A[j] ≠ i, und setzen f(v) = j. Wir erhalten also eine Laufzeit von 3 ∑_{v∈V} d(v) ≤ 6|E|.

Satz 7.3. (von Brooks) Sei G = (V, E) zusammenhängend, kein ungerader Kreis und keine Clique. Dann gilt χ(G) ≤ Δ(G).

Beweis: Im Fall von Δ(G) = 1 folgt G = K_{2}. Im Fall von Δ(G) = 2 ist G ein Pfad oder ein Kreis. Sei also Δ(G) ≥ 3. Wir führen nun eine Induktion über die Anzahl der Knoten n = |V | durch. Für n < 4 ist die Aussage offensichtlich erfüllt. Sei der Satz nun für Graphen mit höchstens n − 1 Knoten bewiesen und n > 3.

7.1. FÄRBUNGEN  KAPITEL 7. FÄRBUNGEN

1. Sei G nicht 2-fach-zusammenhängend.

Es gibt also einen trennenden Knoten x und G = G_{1} ∪ G_{2}, wobei V (G_{1}) ∩ V (G_{2}) = {x} und |G_{1}| > 1 < |G_{2}|.

Da N_{G}(x) ∩ V (G_{i}) ≠ ∅ (i = 1, 2), ist G_{i} keine (Δ(G) + 1)-Clique. (Eine der Kanten führt ja zu x und damit aus der vermeintlichen Clique heraus.)

(a) ∃i ∈ {1, 2} : G_{i} ist ungerade Kreis. Wir haben nun Δ(G) ≥ |d(x)| ≥ 3. Sei y ∈ V (G_{i}) \ {x}. Dann haben wir |d(y)| = 2. Nach Induktionsvoraussetzung für G − y ergibt sich ∃Δ(G)-Färbung von G − y. Da Δ(G) ≥ 3 und d(y) = 2 kann diese Färbung auf G erweitert werden.

(b) Weder G_{1} noch G_{2} ist eine Clique oder ein ungerader Kreis. Dann existieren nach Induktionsvoraussetzung Δ(G)-Färbungen f_{1}, für G_{1} und eine Δ(G)-Färbung f_{2} für G_{2}. O.B.d.A. sei nun f_{1}(x) = f_{2}(x) (sonst benennen wir einfach eine der Farben um).

⇒ f(v) = \{ \begin{matrix}f_{1}(v) & v ∈ V (G_{1}) \\ f_{2}(v) & v ∈ V (G_{2}) \end{matrix} ist eine Δ(G)-Färbung von G.

2. Sei G 3-zusammenhängend.

Da G keine Clique ist, existieren x_{1}, x_{2}, x_{n} so dass E ∌ {x_{1}, x_{2}} ⊆ N(x_{n}).

Sei x_{1}, x_{2}, ..., x_{n} eine Ordnung der Knoten von G, sodass für alle 1 ≤ i < n ein j > i mit x_{j} ∈ N(x_{i}) existiert. (Die Existenz dieser Ordnung folgt aus dem 3-Zusammenhang des Graphen.)

Wir färben nun G mit Greedy Col, wobei die Kanten in der gegebenen Ordnung gefärbt werden.

⇒ f(x_{1}) = f(x_{2}) = 1

⇒ ∀i < n : f(x_{i}) ≤ Δ(G), da höchstens Δ(G) − 1 Knoten aus der Nachbarschaft N(x_{i}) bereits gefärbt wurden.

⇒ |{e ∈ ℕ|∃x ∈ N(x_{n}) : f(x) = e}| ≤ Δ(G) − 1, da f(x_{i}) = f(x_{2}).

3. G ist 2- aber nicht 3-zusammenhängend.

Sei {x, y} eine trennende Menge und G_{1}, G_{2} die beiden Komponenten mit x und y (analog zum Fall 1).

Für i = 1, 2 gilt N(x) ∩ V (G_{i}) \ y ≠ ∅ und N(y) ∩ V (G_{i}) \ x ≠ ∅ (∗).

(a) {x, y} ∈ E(G)

Wir behandeln diesen Fall analog zu Fall 1 und färben die beiden Teilgraphen nach Induktionsvoraussetzung. Weil x und y in beiden Färbungen unterschiedliche Farben haben, können wir die Farben so permutieren, dass wir die Färbungen der Teilgraphen auf den gesamten Graphen ausdehnen können.

(b) {x, y} ∉ E(G)

Wir fügen die Kante {x, y} ein (d.h. wir erzwingen, dass beide Färbungen der Teilgraphen G_{i} die Knoten x und y unterschiedlich färben) und färben die Teilgraphen G′_{i} = G_{i} ∪ {x, y}, i = 1, 2 wie zuvor. Es gilt Δ(G′_{i}) ≤ Δ(G) nach (∗). Damit können wir diesen Fall analog zum Fall 3.1 behandeln.

KAPITEL 7. FÄRBUNGEN  7.1. FÄRBUNGEN

Definition (Mycielski-Konstruktion) Wir setzen M_{2} = K_{2} und M_{i+1} = (V_{i+1}, E_{i+1}) mit V_{i+1} = (V_{i} × {0, 1}) ∪ {v_{i+1}} E_{i+1} = {{(v, 0), (u, 0)}, {(v, 1), (u, 0)}|{v, u} ∈ E_{i}} ∪ {{v_{i+1}, (v, 1)}|v ∈ V_{i}}

Lemma 7.1. Es gilt ω(M_{i}) = 2 und χ(M_{i}) = i.

Beweis:

1. i = 2✓

2. i − 1 → i Wir zeigen zunächst, dass M_{i} keine Dreiecke enthält. Dreiecke, wo alle Punkte von der Form (v, 0) sind, können nicht existieren, weil M_{i−1} bereits dreiecksfrei war. Weiterhin gibt es keine Kanten der Form {(v, 1), (u, 1)}, d.h. es gibt keine Dreiecke, die v_{i} enthalten, da alle Nachbarn von v_{i} als zweiten Eintrag eine 1 haben. Aus dem gleichen Grund gibt es auch keine Dreiecke, wo mehr als ein Knoten von der Form (v, 1) sind. Also müssen wir noch überprüfen, ob ein Dreieck der Form (u, 1), (v, 0), (w, 0) existieren kann. Wenn ein derartiges Dreieck existierte, so wären die Kanten {u, v}, {u, w} und {v, w} bereits in M_{i−1} enthalten, d.h. M_{i−1} würde ein Dreieck enthalten. ⇒ ω(M_{i}) = 2 Nun zeigen wir die Färbbarkeit:

(a) χ(M_{i}) ≤ i Die Menge V_{i}×{0} ist i−1-färbbar, weil M_{i−1} laut Induktionsvoraussetzung i−1-färbbar war. Sei f diese Färbung.

Dann ist g : V (M_{i}) → [i] definiert durch g(y) = \{ \begin{matrix}f(v), falls & y = (v, 0), v ∈ V_{i−1} \\ i , falls & y = (v, 1), v ∈ V_{i−1} \\ 1 , falls & y = x_{i} \end{matrix} eine

i-Färbung von M_{i}.

(b) χ(M_{i}) ≥ i

Annahme: χ(M_{i}) ≤ i − 1

Wegen χ(M_{i−1}) = i − 1 gilt ∀j ∈ {1, ..., i − 1} : ∃v_{i} ∈ V_{i−1} : f(v_{j}) = j, f(N(v_{j})) = [i − 1]\{j}, da sonst χ(M_{i−1}) ≤ i−2 wäre (falls nur f(v_{j}) = j, aber f(N(v_{j})) ≠ [i−1]\{j}, so könnten wir die Farbe j durch eine andere Fehlfarbe des Knotens ersetzen und damit die Farbe j einsparen). Sei g eine i − 1-Färbung von M_{i}. ⇒ ∀j ∈ [i − 1] : ∃(v_{j}, 0) ∈ V_{i−1} × {0} : g(v_{j}, 0) = j und g(N(v_{j}, 0) ∩ (V_{i−1} × {0})) = [i − 1] \ {j} ⇒ g(v_{j}, 1) = j ⇒ g(N(x_{i})) = [i − 1] ⇒ g kann keine Färbung sein.

Definition tw(G) ist die Länge eines kürzesten Kreises.

Bemerkung Wenn tw(G) groß ist, sieht G lokal wie ein Baum aus.

Satz 7.4. (Erdös (1959)) ∀g, k ∈ ℕ∃ Graph G : χ(G) ≥ k, tw(G) > g

Beweis: Der Beweis wurde am Ende leider etwas unangenehm, daher wurde er nur als Kommentar im TEX-Code übernommen. *grins*

Vorlesung am 23.01.2008

7.2. FÄRBUNGEN VON 3-CHROMATISCHE GRAPHEN  KAPITEL 7. FÄRBUNGEN

Bemerkung Wenn P ≠ NP, dann existiert kein polynomieller Algorithmus, der 3-chromatische Graphen färbt. Beweis: Reduktion auf 3-Färbbarkeit.

Bemerkung Wenn P ≠ NP, dann existiert kein polynomieller Approximationsalgorithmus mit Güte < \frac{4}{3}. Beweis: Hier kein Beweis. Vielleicht im alten Skript?

TODO Beweis bei Gelegenheit mal kopieren.

7.2 Färbungen von 3-chromatische Graphen

Wie gut lässt sich eine Färbung für 3-chromatische Graphen finden?

Definition (Algorithmus von Widgerson) Gegeben ist ein Graph G mit χ(G) = 3. Gesucht ist eine Färbung f : V (G) → [n]

Färbung widgerson(G){

while(∃v ∈ V : d_{G}(v) > \sqrt{n}) \{ färbe G[v ∪ N_{G}(v)] mit 3 für v exklusiven Farben f_{v_{1}}, f_{v_{2}}, f_{v_{3}}; G = G − (v ∪ N(v));

}

färbe G mit der Greedy-Heuristik; return Färbung;

}

Satz 7.5. Der Widgerson-Algorithmus findet eine Färbung mit höchstens 4\sqrt{n} Farben.

Beweis: Da bei jedem Durchlauf der while-Schleife mindestens \sqrt{n} Knoten entfernt werden, kann diese höchstens \sqrt{n}-mal durchlaufen werden. Bei jedem Durchlauf verwendet der Algorithmus höchstens 3 Farben, d.h. am Ende der Schleife haben wir höchstens 3\sqrt{n} Farben verwendet. Der Restgraph hat einen Maximalgrad, der kleiner als \sqrt{n} und lässt sich mit der Greedy-Heuristik mit \sqrt{n} zusätzlichen Farben färben.

Bemerkung Der Widgerson-Algorithmus hat eine Güte von O(\sqrt{n}) für 3-chromatische Graphen. Der beste bekannte Approximationsalgorithmus (von Blum und Karger) hat einen Aufwand von O(n^{\frac{3}{14}} p(log n)), p ∈ ℝ[X].

Bemerkung (Khanna, Linial, Safra (1994)) Wenn P ≠ NP gilt, so existiert kein polynomieller Approximations-Algorithmus der Güte \frac{5}{3}.

KAPITEL 7. FÄRBUNGEN  7.3. APPROXIMATIONSALGORITHMEN

7.3 Approximationsalgorithmen für χ(G)-Färbungen für allgemeine Graphen

Bemerkung Die Greedy-Heuristik (wähle die erste noch nicht in der Nachbarschaft verwendete Farbe und färbe den Knoten damit) hat eine Güte von \frac{Δ(G)+1}{3}.

Satz 7.6. Für alle C ∈ ℝ existiert ein polynomieller Färbungsalgorithmus mit Approximationsgüte ⌈\frac{n}{C} ⌉.

Beweis: Gegeben sei ein Graph G = (V, E). Wir bestimmen eine Zerlegung V = ˙⋃_{k=1}^{t}V_{k} mit t = ⌈\frac{n}{C} ⌉ und |V_{k}| ≤ C. Wir färben G[V_{k}] optimal. Damit erhalten wir eine Approximationsgüte von ^{\frac{∑_{k=1}^{t} χ(G[V_{i}])}{χ(G)}} ≤ \frac{tχ(G)}{χ(G)} = ⌈\frac{n}{C} ⌉.

Definition (Johnson Algorithmus) Färbung Johnson (G = (V, E)) {

k = 0;

while (G ≠ ∅) { S = ∅; H = G; while (H ≠ ∅) {

select x ∈ H|d_{H}(x) = δ(H);
S = S ∪ {x};
H = H − (x ˙∪N_{H}(x));

} k++; f(S) = k; G = G − S;

} }

Satz 7.7. Der Johnson-Algorithmus hat eine Approximationsgüte von O(\frac{n}{log n}) = o(n).

Beweis: Beweise gibt’s hier nur als unvollständigen Kommentar im Quellcode dieses Skripts. Vielleicht gibt’s im alten Skript mehr?

Vorlesung am 23.01.2008

7.4 Kantenfärbungen

Definition (Kantenfärbung) Wir betrachten einen Graphen G = (V, E). Eine Kantenfärbung ist f : E → ℕ, mit ∀e_{1}, e_{2} ∈ E : |e_{1} ∩ e_{2}| = 1 ⇒ f(e_{i}) ≠ f(e_{j}).

Definition (chromatischer Index) Der chromatische Index ist χ′(G) = min{|f(E)|, f ist Kantenfärbung}.

7.4. KANTENFÄRBUNGEN  KAPITEL 7. FÄRBUNGEN

Bemerkung Triviale Schranken sind Δ(G) ≤ χ′(G) ≤ 2Δ(G) − 1.

Satz 7.8. (König (1916)) Sei G = (V, E) bipartit. Dann gilt χ′(G) = Δ(G).

Beweis: Wir führen eine Induktion über |E| durch. Für |E| = 0 sind wir trivialerweise fertig. Induktion: |E| − 1 → |E|: Seien e = {x, y} ∈ E, G′ = G\e = (V, E \{e}) und f eine Kantenfärbung von G′ mit Δ(G) Farben. Für x und y existieren jeweils höchstens Δ(G) − 1 Nachbarn, d.h. für beide Knoten gibt es jeweils mindestens eine Farbe f_{x} (bzw. f_{y}), so dass f_{x} ∉ {f(u)|u ∈ N(x)} (analog für f_{y}). Falls f_{x} = f_{y}, dann setzen wir f(e) = f_{x} und sind fertig. Betrachten wir also den Fall f_{x} ≠ f_{y}. Wir definieren H = (V, {e′ ∈ E|f(e′) ∈ {f_{x}, f_{y}}}). ⇒ Δ(H) ≤ 2 ⇒ H ist eine Vereinigung von geraden Kreisen und Pfaden. Weiterhin gilt d(x) = d(y) = 1. Sei P ein Pfad maximaler Länge, der bei x beginnt und bei z endet. Es gilt y ≠ z, weil sonst entweder y eine Kante mit der Farbe f_{y} hätte oder anderenfalls in der Partitionsklasse von f_{x} liegen müsste. Wir tauschen nun die Farben f_{x} und f_{y} entlang P und erhalten eine Färbung f′. ⇒ f_{y} ∉ {f′(v)|v ∈ N(x)} ⇒ Wir können f′(e) = f_{y} setzen.

Bemerkung In bipartiten Graphen lässt sich mit Hilfe des obigen Beweises eine optimale Kantenfärbung in O(nm) finden.

Satz 7.9. (Vizing (1964)) ∀G = (V, E) : χ′(G) ≤ Δ(G) + 1

Beweis: Wir führen den Beweis durch Induktion über |E|: Induktionsanfang: Für |E| = 0 sind wir fertig. Induktionsschritt: |E| − 1 → |E| Seien e = {x, y_{1}} ∈ E, G′ = G \ e und f : E \ {e} → [Δ(G) + 1] eine Kantenfärbung. Beobachtung: ∀v ∈ V : ∃f_{v} ∈ [Δ(G) + 1] : f_{v} ∉ {f(u)|u ∈ N(v)} Falls f_{0} := f_{x} = f_{y_{1}} =: f_{1}, dann kann e mit f_{0} gefärbt werden. Betrachten wir nun den Fall f_{0} ≠ f_{1}. Fehlt f_{1} am Knoten x, so kann e mit f_{1} gefärbt werden. Ansonsten existiert ein Knoten y_{2}, sodass {x, y_{2}} mit f_{1} gefärbt wurde. Sei f_{2} die Fehlfarbe von y_{2}. Falls f_{2} eine Fehlfarbe von x ist, dann kann {x, y_{2}} mit f_{2} und e mit f_{1} gefärbt werden. Wenn f_{2} keine Fehlfarbe von x ist, können wir diese Konstruktion iterieren: Sei (y_{1}, y_{2}, ...) und (f_{1}, f_{2}, ...) eine maximale Sequenz, sodass f(x, y_{i}) = f_{i−1} für alle i ≥ 2 und f_{i} ist die Fehlfarbe von y_{i}.

[figure: x•; f_{1}; f_{2}; f_{3}; ...; •y_{1}; •y_{2}; •y_{3}; •y_{4}; …]

1. Fall: (y_{i}) ist endlich.

Sei l der maximale Index.

⇒ f_{l} ist eine Fehlfarbe von x, da es sonst y_{l+1} gäbe.

KAPITEL 7. FÄRBUNGEN  7.5. PERFEKTE GRAPHEN

Dann kann f wie folgt geändert werden:

Färbe {x, y_{i}} mit f_{i}, i = 1, ..., l und erhalte eine Δ(G)-Kantenfärbung von G.

2. Fall: (y_{i}) ist unendlich Sei l der kleinste Index, so dass es k < l existiert, mit f_{k} = f_{l}, und P ein Pfad maximaler Länge, der in y_{l} beginnt und nur Kanten mit Farben f_{0} und f_{l} benutzt. Es gelte |P | ≥ 1, da sonst f_{0} eine Fehlfarbe von y_{l} und damit f′(x, y_{i}) = f_{i}, i = 1, ..., l − 1 und f′(x, y_{l}) = f_{0} eine Δ(G)-Kantenfärbung wäre. Da f_{0} keine Fehlfarbe von y_{l} ist, hat P mindestens Länge von 1.

(a) P endet in x ⇒ P = (y_{l}, ..., y_{k+1}, x), da f_{0} Fehlfarbe von x ist und somit die letzte Kante von P mit f_{l} = f_{k} gefärbt ist. → Farbshift von y_{k}, ..., y_{1}: f′(x, y_{i}) = f_{i}, i = 1, ..., k → vertausche Farben f_{0} und f_{k} auf P

(b) P endet in y_{k} → Farbshift von y_{k−1}, ..., y_{1} → vertausche die Farben auf P → f′(x, y_{k}) = f_{0}

(c) Sonst → Farbshift von y_{l−1}, ..., y_{1} → Vertausche Farben auf P → f′(x, y_{l}) = f_{0}

Vorlesung am 30.01.2008

Bemerkung

1. Die Entscheidung χ′(G) = Δ(G) oder χ′(G) = Δ(G) + 1 ist selbst für kubische Graphen NP -schwer.

2. Fast alle Graphen G erfüllen χ′(G) = Δ.

7.5 Perfekte Graphen

Definition (perfekt) Ein Graph G ist perfekt, falls χ(H) = ω(H) für alle induzierten Untergraphen von G gilt.

Vermutung: Berge (1960) G ist genau dann perfekt, wenn G keinen ungeraden Kreis der Länge ≥ 5 und kein Komplement eines ungeraden Kreises als induzierten Untergraph enthält.

Vermutung: Berge (1960) G ist genau dann perfekt, wenn \overline{G} perfekt ist.

Bemerkung Bipartite Graphen sind perfekt.

7.5. PERFEKTE GRAPHEN  KAPITEL 7. FÄRBUNGEN

Definition G heißt triangulierter Graph, falls alle induzierten Kreise von G Dreiecke sind. Lemma 7.2. G ist genau dann ein triangulierter Graph, wenn jede inklusionsminimale trennende Menge S, die zwei Knoten auf einem Kreis voneinander trennt, eine Clique induziert. Beweis:

1. ⇒ Seien S (mit |S| ≥ 2) eine minimale trennende Menge und u, v ∈ S. (Im Fall von |S| ≤ 1 ist S trivialerweise eine Clique.) Da S minimal ist, haben u und v jeweils Nachbarn in jeder Komponente von G \ S. Seien H_{1} und H_{2} zwei Zusammenhangskomponenten von G \ S. ⇒ ∃ Pfad P_{i} in H_{i} ∪ S von u nach v. Wir wählen als P_{i} einen kürzesten Pfad aus. Falls {u, v} ∉ E, dann ist C = P_{1} ∪ P_{2} ein Kreis der Länge mindestens 4. ⇒ ∃{x, y} ∈ E mit {x, y} ⊆ V (C) und da P_{i} kürzester Pfad ist, gilt {x, y} ⊈ V (P_{i}), i = 1, 2. Da S trennend ist, kann nicht |{x, y} ∩ V (P_{1})| = 1 = |{x, y} ∩ V (P_{2})| gelten. Damit bleibt jedoch keine Möglichkeit mehr, wo diese Kante {x, y} sein kann, es sei denn, wir wählen {x, y} = {u, v}.

2. ⇐ Seien u, v nicht adjazente Knoten auf einem kürzesten Kreis C. Sei S eine minimal trennende Menge, die u und v trennt. ⇒ |(V (C) \ {u, v}) ∩ S| ≥ 2 Seien x, y ∈ (V (C) \ {u, v}) ∩ S. Da S eine Clique induziert, ist {x, y} ∈ E. Dies ist jedoch ein Widerspruch, also ist C kein kürzester Kreis mit 2 nicht adjazenten Knoten.

Satz 7.10. (Berge) Triangulierte Graphen sind perfekt. Beweis: Kein Beweis.

Definition v ∈ V ist simplizial, falls N(v) eine Clique bildet. Lemma 7.3. (Dirac) Wenn G trianguliert ist, dann ist G entweder ein vollständiger Graph oder es existieren zwei nicht adjazente simpliziale Knoten. Beweis: Wir führen den Beweis durch Induktion über |V |.

1. |V | = 1, 2, 3, 4✓

2. Induktionsschritt: Sei G keine Clique. ⇒ ∃u ≠ v : {u, v} ∉ E Sei S eine minimal trennende Menge (für u und v). Seien H_{1} und H_{2} zwei Zusammenhangskomponenten von G \ S, die u bzw. v enthalten. Laut Induktionsvoraussetzung sind entweder H_{1} ∪S oder H_{2} ∪S vollständige Graphen (dann sind u und v simplizial in G) oder H_{i} ∪ S enthält zwei nicht adjazente simpliziale Knoten für i = 1 oder i = 2. Im letzteren Fall liegen entweder u oder v in H_{i}. Damit ist einer dieser Knoten simplizial in G. Falls H_{j} ∪ S, j ≠ i eine Clique ist, dann ist jeder Knoten in H_{j} simplizial in G und nicht adjazent zum ersten gewählten Knoten.

Falls H_{j} ∪ S keine Clique ist, dann existiert mindestens ein simplizialer Knoten in H_{j}, der auch simplizial in G ist.

Vorlesung am 01.02.2008

Korollar 7.1. ω(G) kann für triangulierte Graphen in polynomieller Zeit berechnet werden.

Satz 7.11. (Lovász, Grötschel, Schrijver (1981)) χ, ω, α können für perfekte Graphen in polynomieller Zeit bestimmt werden.

Satz 7.12. (Chudnowsky, Robertson, Seymour, Thomas (2003)) Die strenge Berge Vermutung ist wahr.

Lemma 7.4. Wenn G perfekt ist, dann ist auch G′ für jede Knotenverdopplung perfekt.

Beweis: Wir führen eine Induktion über |V | durch.

1. Wenn |V | = 1 gilt, so folgt G′ = K_{2} und wir sind fertig.

2. Induktionsschritt:

Zu zeigen ist ω(G′) ≥ χ(G′). (Die Richtung ω(G′) ≤ χ(G′) ist trivial.)

Es gilt ω(G′) ∈ {ω(G), ω(G) + 1}.

(a) ω(G′) = ω(G) + 1 χ(G′) ≤ χ(G) + 1 = ω(G) + 1 = ω(G′)

(b) ω(G′) = ω(G) Sei f eine χ(G) = ω(G)-Färbung von G. Sei K eine größte Clique in G. Damit gilt x ∉ K, da sonst ω(G′) = ω(G) + 1 aus der Definition der Knotenverdopplung folgen würde. Sei X die Farbklasse, die x enthält und H = G \ (X \ {x}). Wir erhalten ω(H) < ω(G), weil in jeder ω(G)-Klicke ein Knoten aus der Farbklasse X liegen muss. Dieser kann (wie zuvor bemerkt) jedoch nicht x sein. Weiterhin ergibt sich χ(H) = ω(H) < ω(G) = χ(G), weil G perfekt ist. ⇒ ∃χ(G) − 1-Färbung von H. Wir färben nun (X \ {x}) ∪ {x′} mit einer neuen Farbe und sind fertig.

Satz 7.13. (Lovász (Schwache Berge Vermutung)) Wenn G perfekt ist, dann ist \overline{G} ebenfalls perfekt.

Beweis: Seien G = (V, E) und G′ = (V′, E′) zwei Graphen mit V′ = V ∪ {x′} (x ∈ V wird verdoppelt) und E′ = E ∪ {{x′, y}|y ∈ N(x) ∪ {x}}. Wir führen eine Induktion über |V | durch und definieren K = {U ⊆ V |U induziert eine Clique in G} und A = {U ⊆ V ||U| = α(G), U ist unabhängig}. Sei \overline{H} ein echter induzierter Untergraph von \overline{G}. Dann ist H ein echter induzierter Untergraph in G. Damit ist H perfekt und nach Induktionsvoraussetzung ist auch \overline{H} perfekt. Es bleibt also noch zu zeigen, dass χ(\overline{G}) ≤ ω(\overline{G}) = α(G). Wir werden zeigen, dass ein K ∈ K mit ∀A ∈ A : K ∩ A ≠ ∅ gilt. (*)

7.5. PERFEKTE GRAPHEN  KAPITEL 7. FÄRBUNGEN

Damit erhalten wir dann ω(\overline{G} − K) < ω(\overline{G}), da jedes A ∈ A eine größte Clique in \overline{G} induziert, die jedoch durch Entfernung eines Knotens verkleinert wird. Mit Hilfe der Induktionsvoraussetzung erhalten wir dann χ(\overline{G}) ≤ χ(\overline{G} − K) + 1 = ω(\overline{G} − K) + 1 ≤ ω(\overline{G}).

Nun zum Beweis von (*). Wir beweisen dies indirekt, d.h. wir nehmen an, (*) wäre falsch. Es gelte also ∀K ∈ K : ∃A_{K} ∈ A : A_{K} ∩ K = ∅. Sei G′ der Graph, der aus G entsteht, wenn jeder Knoten x ∈ V durch eine Clique G_{x} der Größe k(x) = |{K ∈ K|x ∈ A_{K}}| ersetzt wird. Als Kantenmenge dieses neu erzeugten Graphen wählen wir E′ = {{u, v}|u ∈ V (G_{x}), v ∈ V (G_{y}) ∧ (x = y ∨ {x, y} ∈ E)}. Durch unsere obige Annahme haben wir auch k(x) ≥ 1 für alle x ∈ V (G). G′ entsteht also aus G[U], U = {x ∈ V |k(x) > 0} durch eine Sequenz von Knotenverdoppelungen. Nach dem vorherigen lemma ist G′ somit perfekt. ⇒ χ(G′) = ω(G′) (**) Wir haben nun ω(G′) = ∑_{x∈X} k(x) für ein geeignetes X ⊆ V. ⇒ ω(G′) = |{(x, K)|x ∈ X ∩ A_{K}, K ∈ K}| = ∑_{K∈K} |X ∩ A_{K}| ≤ |K| − 1, da |X ∩ A_{K}| ≤ 1. (A_{K} ∈ A ⇒ A_{K} ist unabhängig in G, aber X induziert eine Clique.) ⇒ |V (G′)| = ∑_{x∈V} k(x) = |{(x, K)|x ∈ V ∩ A_{K}, K ∈ K}| = ∑_{K∈K} |A_{K}| = α(G) · |K|, da A_{K} ∈ A. χ(G′) ≥ \frac{|V (G′)|}{α(G′)} = \frac{α(G)}{α(G′)}|K| ≥ |K| > |K| − 1 ≥ ω(G′) Dies ist jedoch ein Widerspruch zu (**).

Vorlesung am 08.02.2008

Planare Graphen

8.1 Allgemeines

Definition planar Ein Graph G heißt planar, wenn es eine Einbettung R : V → ℝ^{2} des Graphen gibt, sodass sich Kanten nur in ihren Endpunkten schneiden.

Definition außerplanar Ein Graph G heißt , wenn es eine Einbettung des Graphen in den ℝ^{2} gibt, sodass sich Kanten nur in ihren Endpunkten schneiden und sich keine Knoten im Inneren des Graphen befinden.

Bemerkung Sei G = (V, E) planar und zusammenhängend. Es gilt

1. |V | − |E| + |R| = 2 (Euler-Formel)

2. |E| ≤ 3n − 6

3. |E| = 3n − 6 ⇔ G ist trianguliert.

Korollar 8.1. Wenn G planar ist, gilt δ(G) ≤ 5.

Beweis: Sei \overline{d} der Durchschnittsgrad von G. ⇒ \overline{d} = ^{\frac{∑_{v∈V} d(v)}{|V |}} = \frac{2|E|}{n} ≤ \frac{6|U|−12}{|V |} < 6 Alternativer Beweis: Sei U = {v ∈ V |d(v) ≥ 6}. ⇒ 6|U| ≤ ∑_{u∈U} d(u) = 2|E| ≤ 6n − 12 ⇒ |U| ≤ n − 2

Korollar 8.2. Sei G = (V, E) dreiecksfrei und planar. Dann gilt |E| ≤ 2|V | − 4 für |V | ≥ 5.

Beweis: (Beweisidee) Sei G ein maximaler K_{3}-freier planarer Graph.

1. G ist 2-susammenhängend.

8.2. FÄRBUNGEN  KAPITEL 8. PLANARE GRAPHEN

2. Jedes Gebiet von G ist durch mindestens 4 Kanten begrenzt.

4|R| ≤ ∑_{r∈R} |r| = 2|E|

⇒ (Euler) n − |E| + \frac{|E|}{2} ≥ 2 ⇒ 2(n − 2) ≥ |E|

Korollar 8.3. K_{3,3} ist nicht planar.

Beweis: |E(K_{3,3})| = 9 > 8 = 2 · 6 − 4 = 2|V (K_{3,3})| − 4

8.2 Färbungen

Satz 8.1. (Appel, Haken) Wenn G planar ist, so gilt χ(G) ≤ 4.

Beweis: Kein Beweis

Satz 8.2. (Kempe, Heawood) Wenn G planar ist, so gilt χ(G) ≤ 5.

Beweis: Wir führen eine Induktion über |V | durch. Für |V | ≤ 5 sind wir fertig. Nun zum Induktionsschritt: Sei (V, E, R) eine planare Einbettung. ⇒ ∃x ∈ V : d(x) ≤ 5 Sei H = G − x. Per Induktion über |V | existiert eine 5-Färbung f von H. Seien v_{1}, ..., v_{5} die Nachbarn von x in zyklischer Ordnung. Falls |f({v_{1}, ..., v_{5}})| < 5, dann gibt es eine freie Farbe für x. Nehmen wir also an, dass es für jedes i ein v_{i} mit f(v_{i}) = i gibt. Seien V_{i,j} = {y ∈ V |f(y) ∈ {i, j}} und F = H[V_{i,j}]. Falls v_{1} und v_{3} in verschiedenen Zusammenhangskomponenten von F liegen, so können die Farben 1 und 3 in der Komponente, die v_{1} enthält vertauscht werden und x kann mit der Farbe 3 gefärbt werden. Somit ist wieder eine Farbe für x frei. Anderenfalls existiert ein Pfad P in F, der v_{1} und v_{3} verbindet. Sei F′ = H[V_{2,4}]. Es existiert kein Pfad P′ in F′ der v_{2} und v_{4} verbindet, da dieser P schneiden müsste. Also liegen v_{2} und v_{4} in verschiedenen Zusammenhangskomponenenten, d.h. wir können die Farben 2 und 4 in der Komponente von v_{2} vertauschen. Damit haben wir wieder eine neue freie Farbe für x.

Definition (Listenfärbung) Gegeben ist ein Graph G = (V, E) und gesucht ist das minimale k (bezeichnet als χ_{l}(G)), sodass ∀L : V → \binom{ℕ}{k} eine Färbung f mit f(v) ∈ L(v) existiert. Die Abbildung L ordnet also jedem Knoten eine Liste von Farben zu, die für diesen Knoten zur Verfügung stehen. Daher stammt auch die Bezeichnung Listenfärbung.

Satz 8.3. Es gilt χ(G) ≤ χ_{l}(G).

Beweis: Wir betrachten die Listen L(v) = {1, ..., χ(G) − 1}.

Satz 8.4. (Thomassen (1994)) Wenn G planar ist, gilt χ_{l}(G) ≤ 5.

Beweis: Behauptung: Sei G ein planarer Graph, der aus einem Kreis C = v_{1}, ..., v_{r}, v_{r} besteht. Weiterhin sei die Menge der Kanten innerhalb des Kreises maximal, d.h. alle Gebiete sind Dreiecke. Seien v_{1} und v_{2} mit 1 und 2 gefärbt, |L(v)| ≥ 3 für alle v ∈ V (C)−{v_{1}, v_{2}} und |L(v)| ≥ 5 für alle V \V (C). Dann existiert eine Listenfärbung. Beweis der Behauptung: Wir führen eine Induktion über n = |V | durch. Induktionsanfang: Wenn r = 3 und G = C gilt, so ist die Aussage offensichtlich wahr. Induktionsschritt: Sei also r > 3 oder G ≠ C.

KAPITEL 8. PLANARE GRAPHEN 8.3. EIGENSCHAFTEN 3-ZUSAMMENHÄNGENDER GRAPHEN

1. Fall: ∃i ≠ j : {v_{i}, v_{j}} ∈ E, 2 ≤ i ≤ −2 ≤ r − 1

Nach Induktionsvoraussetzung existieren Listenfärbungen für C_{1} = (v_{1}, ..., v_{i}, v_{j}, ..., v_{r}, v_{1}) und C_{2} = (v_{i}, ..., v_{j}, v_{i}) und deren Inneres, wobei wir die Farben von v_{i} und v_{j} beliebig festlegen können.

⇒ Es existiert eine Listenfärbung für G.

2. Fall: Es existiert keine Sehne.

Seien v_{1}, u_{1}, ..., u_{s}, u_{r−1} die Nachbarn von v_{r} (im Uhrzeigersinn nummeriert). Da G im Inneren von C trianguliert ist, P = v_{1}, u_{1}, ..., u_{s}, u_{r−1} ein Pfad.

Da wir nicht im Fall 1 sind, gilt {u_{1}, ..., u_{s}} ∩ V (C) = ∅, d.h. C′ = P ∪ (C − v_{r}) ist ein Kreis. Seien x und y verschiedene Farben in L(v_{r}) \ {1}.

Setze L′(u_{i}) = L(u_{i}) \ {x, y} und L′(v) = L(v) für alle v ∉ {u_{1}, ..., u_{s}}.

⇒ Nach Induktionsvoraussetzung existiert eine Listenfärbung für C′ und sein Inneres mit f(v_{1}) ∪ f(v_{r−1}) ≠ {x, y}. (v_{1} ist bereits mit 1 gefärbt und v_{r−1} kann nicht beide Farben x und y haben.)

⇒ Auch ganz G ist färbbar.

Damit ist die Behauptung bewiesen. Da sie schwächere Voraussetzungen als der Satz hatte, ist somit auch der gesamte Satz bewiesen.

8.3 Eigenschaften 3-zusammenhängender Graphen

Lemma 8.1. Sei G ein dreizusammenhängender Graph mit |V | ≥ 5. Dann existiert eine Kante e ∈ E, sodass G/e 3-zusammenhängend ist.

Beweis: Kein Beweis. (Zumindest noch kein Beweis.)

Vorlesung am 13.02.2008

8.4 Satz von Kuratowski

Definition Seien G und H Graphen. H ist eine Unterteilung von G, falls H aus G konstruiert werden kann, indem man Kanten von G durch Pfade ersetzt, wobei die Pfade im Inneren Knotendisjunkt sind.

Lemma 8.2. (1) Wenn G dreizusammenhängend ist und |V (G)| ≥ 5 gilt, dann existiert eine Kante e ∈ E(G), sodass G/e 3-zusammenhängend ist.

Beweis: Übungsaufgabe.

Lemma 8.3. (2) Falls G/e eine Unterteilung von K_{5} oder K_{3,3} enthält, dann enthält auch G eine Unterteilung von K_{5} oder K_{3,3}.

Beweis: Sei S der Teilgraph in G/e mit e = {x, y} ∈ E(G), der eine Unterteilung von K_{5} oder K_{3,3} aufspannt. Sei T ein entsprechender Untergraph in G, d.h. T/e = S. O.B.d.A. können wir davon ausgehen, dass S wirklich ein K_{5} bzw. K_{3,3} ist. (Anderenfalls betrachten wir im Folgenden einfach Pfade statt Kanten.)

1. Fall: d_{T} (y) < 3

Dieser Fall wird analog zu d_{T} (x) < 3 behandelt.

8.4. SATZ VON KURATOWSKI  KAPITEL 8. PLANARE GRAPHEN

2. Fall: d_{T} (x) < 3

(a) N_{T} (x) \ {y} = ∅ ⇒ T \ x = S

(b) ∃z ∈ N_{T} (x) \ {y} ⇒ T ist eine Unterteilung von S, wobei die Kante {{x, y}, z} in S = T/e durch einen P_{2} ersetzt wurde.

3. min{d_{T} (x), d_{T} (y)} ≥ 3.

⇒ Der kontrahierte Knoten {x, y} in S hat mindestens Grad 4.

⇒ S ist eine Unterteilung von K_{5}, da der Maximalgrad einer Unterteilung von K_{3,3} genau 3 ist.

Damit hat der Knoten {x, y} mindestens 4 Nachbarn, die untereinander eine Clique bilden.

Nun gibt es die folgenden Fälle:

(a) Alle 4 Kanten von {x, y} gehörten ursprünglich zu x.

[figure: x•; •; •; y•; •; •]

In diesem Fall bilden x und die 4 Nachbarn ebenfalls einen K_{5}.

(b) Genau 3 Kanten von {x, y} gehörten ursprünglich zu x.

Dann gibt es auch eine Kante, die ursprünglich zu y gehörte.

[figure: x•; •; •; y•; •; •]

Weiterhin hat y jedoch einen Grad von mindestens 3, d.h. es existiert eine weitere Kante in die 4 Nachbarn von {x, y}. Mit dieser Kante erhalten wir dann eine zu Fall (c) analoge Struktur.

(c) Der Knoten x hat (außer y) genau zwei Nachbarn. Dann muss y mindestens die anderen beiden Knoten als Nachbarn haben.

[figure: x•; •; •; y•; •; •]

(d) Wenn x weniger als Nachbarn (außer y) hätte, hätte x in T nicht Grad 3.

Satz 8.5. (Charakterisierung planarer Graphen, Kuratowski (1930)) Ein Graph G ist genau dann planar, wenn er weder eine Unterteilung vom K_{5} noch vom K_{3,3} enthält.

Beweis:

KAPITEL 8. PLANARE GRAPHEN  8.4. SATZ VON KURATOWSKI

1. ⇒

Die Pfade einer Unterteilung dürfen sich nicht schneiden. Also ist keine Unterteilung von K_{5} und K_{3,3} planar.

Wenn G also planar ist, kann er keine Unterteilung von K_{5} oder K_{3,3} enthalten.

2. ⇐

Wir führen eine Induktion über |V | durch. Im Fall von |V | < 5 sind wir fertig.

(a) G ist nicht 3-zusammenhängend.

i. G ist nicht 2-zusammenhängend. Sei x ein trennender Knoten und H_{1}, ..., H_{l} die Komponenten von G \ x. Laut Induktionsvoraussetzung existiert eine planare Einbettung von H_{i} + x mit äußerem Gebiet R, welches x enthält. ⇒ Es existiert eine Einbettung von G, welche die Blöcke H_{i} + x in x verklebt.

ii. G ist zwei- aber nicht dreizusammenhängend.

Seien {x, y} eine trennende Menge, H_{1} eine Komponente von G \ {x, y}, H_{2} der Rest H_{2} = G \ (H_{i} ∪ {x, y}), G_{1} = H_{1} + {x, y} und G_{2} = H_{2} + {x, y}. Wir fügen nun die Kante {x, y} in G_{1} und G_{2} ein. Falls {x, y} ∈ E(G), dann enthalten G_{1} und G_{2} keine Unterteilung von K_{3,3} und K_{5}. Falls {x, y} ∉ E(G), dann enthalten G_{1} und G_{2} keine Unterteilung von K_{3,3} und K_{5}, da wir sonst {x, y} durch einen x − y-Pfad aus den inneren Knoten der jeweils anderen Zusammenhangskomponente von G \ {x, y} ersetzen könnten und somit bereits G eine entsprechende Unterteilung enthielte. Laut Induktionsvoraussetzung existiert eine planare Einbettung von G_{1} und G_{2} mit der Kante {x, y} auf dem äußeren Gebiet. Durch Zusammenkleisterung entlang dieser Kante erhalten wir die Planarität von G.

(b) G ist 3-zusammenhängend. Mit Lemma 1 existiert eine Kante e = {x, y} ∈ E(G), sodass G/e weiterhin dreizusammenhängend ist. Mit Lemma 2 enthält G/e keine Unterteilung von K_{5} oder K_{3,3} und laut Induktionsvoraussetzung existiert somit eine planare Einbettung von G/e. Sei z der Knoten in G/e, der e repräsentiert. Da G/e 3-zusammenhängend ist, ist (G/e) − z zweizusammenhängend. ⇒ Es existiert ein Kreis C, welcher das Gebiet in (G/e)−z begrenzt, welches den Knoten z in der Einbettung von G/e enthält. ⇒ N_{G/e}(z) ⊆ V (C) ⇒ N_{G}(x) ∪ N_{G}(y) ⊆ V (C) Seien x_{1}, ..., x_{k} die Nachbarn von x auf dem Kreis C im Uhrzeigersinn. Sei P_{i} der Teilpfad von C, der x_{i} mit x_{i+1} verbindet (x_{k+1} = x_{1}).

i. ∃P_{i} : N_{G}(y) \ {x} ⊆ V (P_{i})

⇒ G ist planar. ii. y hat mindestens zwei Nachbarn, die auf verschiedenen P_{i} liegen.

[figure: •; •; ∘; •; •; x•; •y; ∘; •; •]

In diesem Fall finden wir eine Unterteilung eines K_{3,3} in G, wenn die Nachbarn von x und y paarweise verschieden sind. Anderenfalls finden wir sogar eine Unterteilung eines K_{5}.

Index

Überdeckungszahl, 42

abhängige Menge

Matroid, 24 Adjazenzliste, 9 Adjazenzmatrix, 9 Algorithmus

Approximation, 50 Bellmann-Moore, 18 Kruskal, 19 Prim, 20

alternierender Pfad, 36 amortisierte Laufzeit, 16 Approximation

Algorithmus, 50

Güte, 50 Approximationsalgorithmus, 50 Approximationsgüte, 50 außerplanar, 61 auserplanar, 61

Basis

Matroid, 22 Baum, 8

spannender, 8 Bellmann-Moore-Algorithmus, 18 bipartit, 9 Blatt, 8 Breitensuche, 11

chromatische Zahl, 8, 51 chromatischer Index, 55 Cliquenzahl, 8

Durchsatz, 31

euklidisches TSP, 49 eulersch, 45

Färbung, 8, 51 k-Färbung, 51 chromatische Zahl, 51 Kante, 55 Knoten, 51 Listen-, 62 Fibonacci-Heap, 16

Güte

Approximation, 50 geschichtetes Restnetzwerk, 31 gewichtetes Matroid, 22 größtes Matching, 35 Grad, 7

Durchschnitts-, 7 Maximal-, 7 Minimal-, 7

Graph, 7 gerichteter, 7 Kreis, 7 Teil-, 8 vollständiger, 8 zusammenhängender, 8

graphisches Matroid, 22

Hamiltonabschluss, 47

hamiltonisch, 46

Heap, 16 Fibonacci, 16

Isomorphie Graphen, 8

Kante, 7

Färbung, 55 Kantenfärbung, 55 Kapazität

Schnitt

Netzwerk, 27 Knoten, 7

Färbung, 51 Nachbar, 7 Knotenfärbung, 51 Kreis

Graph, 7 Matroid, 24 Kruskal-Algorithmus, 19

Laufzeit

armortisiert, 16 Listenfärbung, 62

INDEX  INDEX

Matching, 35 größtes, 35 maximal, 35 perfekt, 41 schwerstes, 39

Matrixmatroid, 22 Matroid, 21

abhängige Menge, 24

Basis, 22 gewichtet, 22 Kreis, 24

maximal unabhängige Menge, 22 maximales Matching, 35 metrisches TSP, 49

Nachbar ausgehend, 7 eingehend, 7

Netzwerk, 27

Fluss, 27 Wert, 27 Schnitt, 27

Kapazität, 27 Wert

Fluss, 27

partit, 9 perfektes Matching, 41 Pfad, 7

alternierend, 36 augmentierend, 36

planar, 61

außer, 61 Potentialfunktion, 16 Prim-Algorithmus, 20

Rang

Unabhängigkeitssystem, 24 Rangquotient

Unabhängigkeitssystem, 25 Rektlineares TSP, 49 Restnetzwerk

geschichtet, 31

Schnitt

Netzwerk, 27 schwerstes Matching, 39 Stabile Menge, 8 Stabilitätszahl, 8

Teilgraph, 8 induzierter, 8 spannender, 8

Tiefensuche, 10 Tournament, 7 TSP, 49

euklidisch, 49 metrisch, 49 rektlinear, 49

Unabhängigkeitssystem, 21 Rang, 24 Rangquotient, 25 unterer Rang, 24 ungarischer Wald, 37 unterer Rang

Unabhängigkeitssystem, 24 Unterteilung, 63

Wald, 8

ungarisch, 37 Weg, 7

Zusammenhangszahl, 8 Zykel, 7