Graphenalgorithmen 001

Vorlesung

Graphenalgorithmen Sommersemester 2005

Angelika Steger ETH Zurich ¨

30. Juni 2005

2

Teile des vorliegenden Skriptes sind Erweiterungen des Skript zu meiner Vorlesung Effiziente Algorithmen und Datenstrukturen II, die ich im Sommersemester 1997 an der TU M¨ unchen gehalten habe. Das Skript zu meiner damaligen Vorlesung wurde von den Studenten der Vorlesung geschrieben, denen ich an dieser Stelle nochmals f¨ ur ihren Einsatz danken m¨ochte: Markus Ebersberger, Maximilian Fischer, Alexander Hall, Sebastian Heupel, Thomas Schickinger und Ulrich Voll.

Inhaltsverzeichnis 1 Fl¨ usse in Netzwerken

5

1.1

Einf¨ uhrung und Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2

Der Algorithmus von Ford–Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.2.1

Augmentierende Pfade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.2.2

Korrektheit f¨ ur ganzzahlige Netzwerke, Max–Flow–Min–Cut–Theorem . . . . . . .

8

1.2.3

Anmerkungen und Erweiterung auf nichtganzzahlige Netzwerke . . . . . . . . . . .

10

Die Push-/Relabel–Methode nach Goldberg und Tarjan . . . . . . . . . . . . . . . . . . .

12

1.3

2 Matching Probleme

19

2.1

Definition und Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.2

Das ungewichtete Matchingproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.2.1

Augmentierende Pfade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.2.2

Bipartite Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.2.3

Matching in allgemeinen Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Das gewichtete Matchingproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.3.1

Bipartite Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.3.2

Exkurs: Die primal-duale Methode der linearen Programmierung . . . . . . . . . .

36

2.3.3

Allgemeine Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

2.3

3 Das Rundreiseproblem 3.1

43

Exakte L¨ osungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3.1.1

Dynamische Programmierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3.1.2

Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.2

Das Rundreiseproblem mit Dreiecksungleichung . . . . . . . . . . . . . . . . . . . . . . . .

48

3.3

Das euklidische Rundreiseproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

4 Planare Graphen

51

4.1

Eigenschaften planarer Graphen

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

4.2

Planarit¨ atstest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

4.3

Zeichnen von planaren Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

3

INHALTSVERZEICHNIS

4 5 Separatoren

69

5.1

Separatoren in planaren Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

5.2

Anwendungen des Separatorensatzes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

6 Beschr¨ ankte Baumweite

77

6.1

Baumzerlegung und Baumweite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

6.2

Algorithmische Konsequenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

6.3

Partielle k-B¨ aume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

6.4

Bestimmung einer Baumzerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

Kapitel 1

Flu ¨ sse in Netzwerken 1.1

Einfu ¨hrung und Definitionen

In diesem Kapitel betrachten wir so genannte Netzwerke N = (V, A, c, s, t). Hierbei sei D = (V, A) s∈V t∈V c : A → R≥0

ein gerichteter Graph, die Quelle (engl.: source), die Senke (engl.: target) und eine nicht-negative Kapazit¨atsfunktion.

Intuitiv stelle man sich unter einem Netzwerk beispielsweise ein R¨ohrensystem vor, bei dem die Kanten des Graphen den Rohren entsprechen und die Knoten den Kreuzungspunkten der Rohre. Es soll nun z. B. eine Fl¨ ussigkeit von der Quelle s zur Senke t transportiert werden. Diese Fl¨ ussigkeit darf nur an der Quelle bzw. Senke eingespeist werden bzw. abfliessen. An allen anderen Kreuzungspunkten geht keine Fl¨ ussigkeit verloren. Jedes Rohr transportiert die Fl¨ ussigkeit nur in eine vorgegebene Richtung. Ausserdem kann jedes Rohr nur bis zu einer gewissen Obergrenze, der Kapazit¨at, Fl¨ ussigkeit aufnehmen. Formal l¨ asst sich dies wie folgt beschreiben: Definition 1.1 Eine Abbildung f : A → R heisst s–t–Fluss, falls 1.


u∈Γ+ (v)

f (v, u) =

2. 0 ≤ f (a) ≤ c(a)


u∈Γ− (v)

∀a ∈ A

f (u, v)

∀v ∈ V \ {s, t}

(Flusserhaltung)

(Zul¨ assigkeit)

Hier bezeichnet Γ+ (v) die von v aus erreichbaren Nachbarknoten, also Γ+ (v) := {u ∈ V : (v, u) ∈ A}. Analog bezeichnet Γ− (v) die Menge der Knoten, von denen aus v direkt erreicht werden kann, also Γ− (v) := {u ∈ V : (u, v) ∈ A}. Definition 1.2 Der Wert w(f ) eines Flusses f ist definiert durch   w(f ) = f (s, u) − f (u, s) u∈Γ+ (s)

u∈Γ− (s)

Anschaulich gibt also der Wert an, um wie viel die an der Quelle ins Netzwerk gepumpte Fl¨ ussigkeitsmenge die dort abfliessende Menge u ussigkeitsmenge, die an der ¨bertrifft. Diese Definition ist ¨aquivalent zur Fl¨ Senke mehr zu- als abfliesst: Proposition 1.3 F¨ ur ein Netzwerk mit gegebenem s–t–Fluss f gilt   w(f ) = f (u, t) − f (t, u) u∈Γ− (t)

u∈Γ+ (t)

5

¨ KAPITEL 1. FLUSSE IN NETZWERKEN

6 Beweis:

Folgt unmittelbar aus 



f (v, u) =

v∈V u∈Γ+ (v)





f (u, v)

v∈V u∈Γ− (v)

durch Umsortieren der Summanden und Anwendung von Teil 1 der Definition 1.1. Definition 1.4 Ein s–t–Fluss f0 mit w(f0 ) = max{w(f ) : f ist s–t–Fluss} heisst maximaler Fluss. In den folgenden Abschnitten betrachten wir nun das MaxFlow-Problem: Geg.: Ein Netzwerk mit nicht-negativer Kapazit¨atsfunktion N = (V, A, c, s, t) Ges.: Bestimme einen maximalen Fluss f . Diese Fragestellung spielt bei zahlreichen Anwendungen ein Rolle. Man denke hierbei z. B. an ein Transportnetzwerk, bei dem durch optimale Zuordnung der zu transportierenden G¨ uter zu den einzelnen Transportwegen ein maximaler Gesamtdurchsatz erreicht werden soll. Neben solchen direkten Anwendungen tritt das MaxFlow-Problem aber auch oft als Subproblem anderer Probleme auf1 . Die n¨ achste Proposition stellt sicher, dass die Suche nach einem maximalen Fluss immer sinnvoll ist. Proposition 1.5 In jedem Netzwerk gibt es einen maximalen Fluss. Beweis: Betrachte F = { f : f ist s–t–Fluss } ⊂ R|A| . Diese Menge ist abgeschlossen und beschr¨ankt. Daraus folgt, dass jede Funktion auf F , also insbesondere auch f : F → R, f → w(f ) auf F ihr Maximum annimmt.

1.2

Der Algorithmus von Ford–Fulkerson

Diesem Algorithmus liegt folgende einfache Idee zugrunde: Starte mit f ≡ 0 und vergr¨ossere w(f ) schrittweise, solange dies m¨ oglich ist. Dazu betrachten wir spezielle Pfade im Graphen.

1.2.1

Augmentierende Pfade

Definition 1.6 F¨ ur einen Fluss f in einem Netzwerk N heisst eine Folge s = v0 , v1 , . . . , vk−1 , vk = x ein augmentierender s − x–Pfad, falls f¨ ur alle i ∈ {0, . . . , k − 1} gilt: 1. 2.

e = (vi , vi+1 ) ∈ A und f (e) < c(e) oder e = (vi+1 , vi ) ∈ A und f (e) > 0

(e heisst Vorw¨artskante) (e heisst R¨ uckw¨artskante)

Anschaulich besagt dies, dass man entlang eines augmentierenden Pfades mehr Fl¨ ussigkeit transportieren kann, als dies im aktuellen Fluss f der Fall ist. Auf den Vorw¨artskanten ist die Kapazit¨at noch nicht ersch¨ opft, d. h. dort kann noch mehr durchgepumpt“ werden. Auf den R¨ uckw¨artskanten liegt ein von ” Null verschiedener Fluss entgegen des augmentierenden Pfades vor, der echt verringert werden kann. Abbildung 1.1 zeigt ein Beispiel f¨ ur dieses Vorgehen. Die Beschriftung der Kanten besteht aus Paaren (c(e), f (e)). Entlang des gestrichelt markierten augmentierenden Pfades kann der Fluss um eins erh¨ oht werden. Dadurch steigt der Wert des Flusses von eins auf zwei und erreicht dadurch den Maximalwert f¨ ur diesen Graphen. Das folgende Lemma pr¨ azisiert die Eigenschaften der augmentierenden Pfade. 1 Vgl.

hierzu sp¨ atere Kapitel der Vorlesung.

1.2. DER ALGORITHMUS VON FORD–FULKERSON v1

1/1

t

1/1

)

=

v1

1/1 s

1/1

1/1 1/0

1/ 0

1/1

s

1/0

7

v2

1/1

t

v2

Abbildung 1.1: Erh¨ ohung des Flusses entlang eines augmentierenden Pfades

Lemma 1.7 Sei f ein s–t–Fluss und s = v0 , v1 , . . . , vk−1 , vk = t ein augmentierender s–t–Pfad P . Dann gilt: F¨ ur jedes δ > 0 mit δ ≤ min({c(a) − f (a) : a ∈ P, a Vorw¨artskante} ∪ {f (a) : a ∈ P, a R¨ uckw¨artskante}) ist

⎧ ⎪ ⎨f (a) + δ fδ (a) = f (a) − δ ⎪ ⎩ f (a)

falls a ∈ P, a Vorw¨artskante falls a ∈ P, a R¨ uckw¨artskante sonst

ein s–t–Fluss mit Wert w(fδ ) = w(f ) + δ. Beweis: Zu u ufen ist die Definition 1.1: ¨ berpr¨ Die Zul¨ assigkeit folgt unmittelbar aus der Definition von fδ . Zum Nachweis der Flusserhaltung betrachten wir einen beliebigen Knoten v ∈ V \ {s, t}: 1. Fall: v liegt nicht auf P . Hier ist nichts zu zeigen. 2. Fall: v = vi ∈ P f¨ ur ein i ∈ {1, . . . , k − 1}. Je nachdem, ob es sich bei den an v angrenzenden Kanten auf dem Pfad um Vorw¨arts- oder R¨ uckw¨artskanten handelt, sind vier F¨ alle zu unterscheiden, die in Abbildung 1.2 dargestellt sind.

s s s s

+ + ; ;

v v v v

+ ; + ;

t t t t

Abbildung 1.2: Verschiedene F¨ alle bei der Modifikation von f entlang eines augmentierenden Pfades Offensichtlich bleibt in jedem Fall die Flusserhaltung erf¨ ullt. w(fδ ) = w(f ) + δ folgt sofort aus der Ver¨anderung von f auf der Kante (s, v1 ). ¨ Die vorangegangenen Uberlegungen f¨ uhren schliesslich zu folgendem Algorithmus:

¨ KAPITEL 1. FLUSSE IN NETZWERKEN

8 Alg. von Ford–Fulkerson (1)

Setze f ≡ 0;

(2)

Finde augmentierenden s-t Pfad P bzgl. f ; Falls keiner existiert: Stopp, gib f aus;

(3)

Setze δ := min({c(a) − f (a) : a ∈ P, a Vorw¨artskante} ∪ {f (a) | a ∈ P, aR¨ uckw¨artskante}); ⎧ ⎪ ⎨f (a) + δ f (a) := f (a) − δ ⎪ ⎩ f (a)

und

a ∈ P, a Vorw¨artskante a ∈ P, a R¨ uckw¨artskante sonst.

Zur¨ uck zu (2);

1.2.2

Korrektheit fu ¨ r ganzzahlige Netzwerke, Max–Flow–Min–Cut–Theorem

Bevor wir die Korrektheit des Algorithmus von Ford–Fulkerson untersuchen, ben¨otigen wir noch eine neue Definition: Definition 1.8 Sei N ein Netzwerk und W ⊂ V eine Knotenmenge mit s ∈ W und t ∈ W . Dann heisst (W, W ) ein s–t–Schnitt. Die Kapazit¨at des Schnitts ist definiert als 

c(W, W ) =

c(v, u)

(v,u)∈A v∈W,u∈W

Zwischen Fl¨ ussen und Schnitten besteht ein direkter Zusammenhang: Proposition 1.9 F¨ ur jeden s–t–Fluss f und jeden s–t–Schnitt (W, W ) gilt:   w(f ) = f (v, u) − f (u, v) ≤ c(W, W ) (v,u)∈A v∈W,u∈W

(u,v)∈A u∈W,v∈W

Beweis: w(f )

=

 u∈Γ+ (s)

=





f (s, u) − 

f (v, u) −

v∈W u∈Γ+ (v)

=



=



(v,u)∈A v∈W,u∈W

≤



f (v, u) −

(v,u)∈A v∈W



(v,u)∈A v∈W,u∈W

f (u, s)

u∈Γ− (s)





v∈W u∈Γ− (v)

f (u, v)

(u,v)∈A v∈W

f (v, u) −



f (u, v)

(u,v)∈A u∈W,v∈W

f (v, u) ≤ c(W, W )

f (u, v)

(wegen Flusserhaltung)

1.2. DER ALGORITHMUS VON FORD–FULKERSON

9

Anschaulich besagt die Proposition 1.9, dass jeder Fluss auf dem Weg von der Quelle zur Senke die Grenze zwischen einer Partition (W, W ) der Knoten mit s ∈ W vollst¨andig passieren muss. Die Bilanz zwischen dem Fluss aus W hinaus und in W hinein entspricht genau dem Fluss, der an der Quelle entsteht bzw. an der Senke abfliesst. Da die Ungleichung in Proposition 1.9 f¨ ur alle Fl¨ usse und alle Schnitte gilt, ergibt sich daraus unmittelbar folgendes Korollar: Korollar 1.10 F¨ ur jedes Netzwerk gilt max

f s–t–Fluss

w(f )

≤

min

(W,W ) s–t–Schnitt

c(W, W )

Nun sind wir in der Lage, die folgende Aussage u ¨ber die Korrektheit und Laufzeit des Algorithmus von Ford–Fulkerson zu formulieren: Satz 1.11 F¨ ur Netzwerke mit einer ganzzahligen Kapazit¨atsfunktion c : A → N0 terminiert der Algorithmus von Ford–Fulkerson nach h¨ochstens |V |cmax Augmentierungsschritten mit einem (ganzzahligen) maximalen Fluss, wobei cmax = max{c(s) : a ∈ A}. Beweis: Lemma 1.7 garantiert, dass der Fluss nach jeder Iteration des Algorithmus zul¨assig ist. Ausserdem ist klar, dass der Fluss immer ganzzahlig ist, d. h., dass f (e) ∈ N0 ∀e ∈ A, da der Nullfluss zu Beginn des Algorithmus diese Bedingung erf¨ ullt und alle Operationen w¨ahrend der Iteration (Minimumsbildung, Addition und Subtraktion) die Ganzzahligkeit erhalten. Da der Fluss in jedem Iterationsschritt echt erh¨oht wird und ganzzahlig bleibt, muss er also jedes mal um mindestens eins wachsen. Jede von der Quelle s ausgehende Kante kann also h¨ochstens cmax –mal an einem augmentierenden Pfad beteiligt sein. Da jeder augmentierende s–t–Pfad eine solche Kante enthalten muss und s weniger als |V | direkte Nachbarn hat, folgt unmittelbar die Oberschranke f¨ ur die Anzahl der Iterationen2 . Es bleibt also nur noch zu zeigen, dass der Fluss f0 , mit dem der Algorithmus terminiert, maximal ist. Hierzu betrachten wir W = {x ∈ V : es existiert ein augmentierender s–x–Pfad bez¨ uglich f0 }. Es gilt s ∈ W nach Definition und ausserdem t ∈ W , da der Algorithmus sonst einen augmentierenden s–t–Pfad gefunden und nicht terminiert h¨ atte. D. h. (W, W ) ist ein s–t–Schnitt. Nach Definition von W gilt: 1. f0 (x, v) = c(x, v)

∀(x, v) ∈ A mit x ∈ W, v ∈ W

2. f0 (u, x) = 0 ∀(u, x) ∈ A mit u ∈ W, x ∈ W Wenn man diese Werte in Proposition 1.9 einsetzt, so erh¨alt man w(f0 ) = c(W, W ) ≥

max

f s–t–Fluss

w(f )

wobei sich die Ungleichung aus Korollar 1.10 ergibt. Daraus folgt dann unmittelbar die Behauptung. Aus Theorem 1.11 k¨ onnen wir direkt folgende Versch¨arfung von Proposition 1.5 ableiten. Korollar 1.12 Ist N = (V, A, C, s, t) ein Netzwerk mit ganzzahligen Kapazit¨aten, so existiert ein ganzzahliger maximaler Fluss. Erg¨ anzend wollen wir noch ein bekanntes Resultat der Graphentheorie angeben. 2 Da uns, wie immer, nur die Gr¨ ossenordnung interessiert, verzichten wir auf weitere Argumente, diese Schranke noch um eins oder zwei zu erniedrigen

¨ KAPITEL 1. FLUSSE IN NETZWERKEN

10 Satz 1.13 (Max–Flow–Min–Cut–Theorem) F¨ ur jedes Netzwerk N = (V, A, C, s, t) gilt: max

f s–t–Fluss

w(f )

=

min

(W,W ) s–t–Schnitt

c(W, W )

Beweis: ≤“ haben wir in Korollar 1.10 bereits gezeigt. Bleibt also nur noch ≥“ nachzuweisen. ” ” uglich f0 defiBetrachte hierzu einen maximalen Fluss f0 , der nach Proposition 1.5 immer existiert. Bez¨ niere man eine Menge W0 genauso wie im Beweis von Theorem 1.11. Genau dieselbe Argumentation wie dort liefert w(f0 ) ≥ c(W0 , W0 ).

1.2.3

Anmerkungen und Erweiterung auf nichtganzzahlige Netzwerke

Anzahl der Iterationen Die in Theorem 1.11 angegebene Schranke f¨ ur die Anzahl der Iterationen ist bis auf eine Konstante bestm¨ oglich. Man betrachte hierzu das Netzwerk in Abbildung 1.3.

v1

c s

c

c

1

c

t

v2 Abbildung 1.3: Worst–case–Beispiel f¨ ur Ford–Fulkerson Wenn der Algorithmus abwechselnd die augmentierenden Pfade s, v1 , v2 , t und s, v2 , v1 , t w¨ahlt, so sind 2c Iterationen n¨ otig. Daraus folgt, dass der Algorithmus von Ford–Fulkerson kein effizienter, d. h. polynomieller Algorithmus ist, da die Kapazit¨ aten mit O(log cmax ) Bits kodiert werden k¨onnen. Wenn man also hinreichend grosse Kapazit¨ aten zul¨ asst, so ist die Laufzeit des Algorithmus exponentiell in der Gr¨osse der Eingabe. Dennoch kann der Algorithmus von Ford–Fulkerson unter gewissen Umst¨anden in der Praxis erfolgreich eingesetzt werden. Beispielsweise l¨ asst sich das Problem der Suche nach einem Maximum Matching3 in einem bipartiten Graphen auf ein MaxFlow–Problem in einem Netzwerk mit Kapazit¨aten c(e) = 1 transformieren. Dazu erweitert man den bipartiten Graphen um zwei neue Knoten s und t, die als Quelle und Senke des Netzwerks dienen. Von s aus werden Kanten zu allen Knoten einer Partition gezogen und alle Knoten der anderen Partition werden mit t verbunden. Diese neuen Kanten und alle Kanten des urspr¨ unglichen Graphen werden von der Quelle zur Senke gerichtet. Es ist leicht einzusehen, dass genau die Kanten mit einem Fluss gleich eins in der L¨osung des MaxFlow–Problems ein Maximum Matching bilden. Dieses Flussproblem kann der Algorithmus von Ford–Fulkerson in O(n) Iterationsschritten l¨osen, wobei n = |V |. Nichtganzzahlige Kapazit¨ aten: Algorithmus von Edmonds und Karp Theorem 1.11 l¨ asst sich leicht auf rationale Kapazit¨atsfunktionen erweitern, indem man die Kapazit¨aten mit dem Hauptnenner durchmultipliziert und auf diese Weise ein ¨aquivalentes Netzwerk erh¨alt, das die Voraussetzungen von Theorem 1.11 erf¨ ullt. F¨ ur irrationale Kapazit¨ aten kann der Algorithmus von Ford–Fulkerson v¨ollig versagen, wie das folgende Beispiel zeigt: 3 Dieser

Begriff wird in einem sp¨ ateren Kapitel genau definiert.

1.2. DER ALGORITHMUS VON FORD–FULKERSON Beispiel 1.14 Es seien φ = Netzwerk:

√ 5−1 2 ,

ci = φi und S =

11


∞

i=0 ci

=

1 1−φ .

Weiter betrachte man folgendes

co

s

c1

t

c2

wobei die drei horizontalen Kanten Kapazit¨aten c0 , c1 und c2 und alle ¨ ubrigen Kanten Kapazit¨at S haben. Durch Induktion kann man sich davon ¨ uberzeugen, dass der Ford-Fulkerson Algorithmus augmentierende Pfade stets so w¨ahlen kann, dass sich der Fluss in de i-ten Iterationen genau ci−1 erh¨oht. Der Wert der gefundenen Fl¨ usse konvergiert somit gegen S. [Um dies einzusehen, ¨ uberpr¨ uft man zun¨achst, dass f¨ ur alle usse i ∈ N gilt: ci+1 = ci−1 − ci . Die Idee ist nun, Pfade so zu w¨ahlen, dass nach i ≥ 2 Iterationen die Fl¨ uber die drei horizontalen Kanten genau ci , ci−1 und 0 betragen. F¨ ur die (i + 1)te Iteration w¨ahlt man ¨ dann einen Pfad, der die Kante mit Fluss 0 vorw¨arts durchl¨auft und die beiden anderen horizontalen Kanten r¨ uckw¨arts. Der Fluss wir daher um ci erh¨oht und die neuen Fl¨ usse ¨ uber die horizontalen Kanten betragen dann 0, ci−1 − ci = ci+1 und ci , was zu zeigen war.] Der Wert eines maximalen Flusses ist jedoch 3S.

Wir suchen deshalb eine Modifikation des Algorithmus von Ford–Fulkerson, der die folgenden zwei Ziele erreicht:

1. Der Algorithmus soll auch f¨ ur irrationale Kapazit¨atsfunktionen funktionieren. 2. Die Laufzeit, bzw. die Anzahl der Iterationen soll nur noch von der Gr¨osse des Graphen abh¨angen, nicht aber von der Gr¨ osse der Kapazit¨aten.

Bei der Implementierung des Algorithmus von Ford–Fulkerson hat man noch eine wichtige Wahlm¨oglichkeit, n¨ amlich die Auswahl des augmentierenden Pfades, entlang dem der Fluss erh¨oht wird. Edmonds und Karp haben gezeigt, dass man durch geschickte Durchf¨ uhrung dieses Schritts die beiden oben genannten Ziele erreichen kann. Ihre Variante des Algorithmus von Ford–Fulkerson w¨ahlt in jedem Iterationsschritt einen k¨ urzesten (bez¨ uglich der Anzahl von Kanten) augmentierenden Pfad aus. Dieser l¨asst sich leicht durch Breitensuche bestimmen. Da der Beweis zur Laufzeit des Algorithmus von Edmonds und Karp kompliziert ist und wir ausserdem im n¨ achsten Kapitel einen noch schnelleren Algorithmus betrachten werden, sei hier nur das Ergebnis ohne Beweis angegeben.

Satz 1.15 Der Algorithmus von Edmonds und Karp terminiert f¨ ur jedes Netzwerk nach h¨ochstens (nm)/2 Iterationen mit einem maximalen Fluss, wobei m = |A| und n = |V |.

¨ KAPITEL 1. FLUSSE IN NETZWERKEN

12

1.3

Die Push-/Relabel–Methode nach Goldberg und Tarjan

Die Idee von Goldberg/Tarjan besteht darin, am Anfang die Quelle voll aufzudrehen“, d. h. auf allen ” Ausg¨ angen der Quelle sch¨ opft man die Kapazit¨aten voll aus. Danach wird der Fluss iterativ weiter Rich” tung Senke“ geleitet (Push–Aktion), soweit es die Kapazit¨aten und die am jeweiligen Knoten verf¨ ugbare Fl¨ ussigkeit erlauben. Wenn der Fluss irgendwann bei der Senke angekommen ist und aufgrund der beschr¨ ankten Kapazit¨ aten ins Stocken“ gekommen ist, werden eventuell noch vorhandene u usse ¨ bersch¨ ” zur¨ uck zur Quelle geleitet und der Hahn wieder etwas zugedreht“. ” F¨ ur diese Methode ben¨ otigen wir die Voraussetzung, dass D = (V, A) symmetrisch ist, d. h. dass (u, v) ∈ A =⇒ (v, u) ∈ A, damit wir die Fl¨ ussigkeit sowohl von der Quelle zur Senke, als auch wieder zur¨ uck transportieren k¨ onnen. Dies kann man durch Hinzuf¨ ugen von Kanten (x, y) mit c(x, y) = 0 immer erreichen und stellt somit keine Einschr¨ankung dar. W¨ ahrend der Iterationen des Algorithmus betrachten wir nicht mehr echte Fl¨ usse, sondern Pseudofl¨ usse bzw. (genauer) Pr¨ afl¨ usse. Diese Begriffe werden in den folgenden Definitionen eingef¨ uhrt. Definition 1.16 Eine Abbildung f : A → R heisst Pseudofluss, wenn gilt: 1. f (u, v) ≤ c(u, v) f¨ ur alle (u, v) ∈ A und 2. f (u, v) = −f (v, u) f¨ ur alle (u, v) ∈ A. ¨ Definition 1.17 Gegeben sei ein Netzwerk mit einem Pseudofluss f . Als Uberschuss (engl.: excess) ef (v) im Knoten v bezeichnen wir  f (u, v) ef (v) := (u,v)∈A

Hinter dieser einfachen Summe verbirgt sich im Grunde die Bilanz zwischen Zu- und Abfluss im Knoten v. Diese kurze Formulierung wird durch den 2. Teil von Definition 1.16 erm¨oglicht. Fluss nach v hinein taucht in der Summe als positiver Summand auf und Fluss aus v heraus wird im Gegenzug als negativer Summand ber¨ ucksichtigt. ur alle v ∈ V \ {s, t}. Definition 1.18 Ein Pr¨ afluss (engl. preflow) ist ein Pseudofluss mit ef (v) ≥ 0 f¨ Zwischen einem Pseudofluss f und einem echten“ Fluss nach Definition 1.1 besteht ein enger Zusam” ¨ menhang. Wenn man n¨ amlich erreicht, dass alle Ubersch¨ usse abgebaut sind, d. h., dass ef (v) = 0 f¨ ur alle v ∈ V \ {s, t}, dann kann man leicht einen Fluss f  angeben durch  f (a) falls f (a) > 0  f (a) = 0 sonst, W¨ ahrend der Algorithmus u ussigen Fluss zur Senke oder, wenn deren Aufnahmef¨ahigkeit ersch¨opft ¨ bersch¨ ist, zur¨ uck zur Quelle transportiert, betrachten wir die sogenannten aktiven Knoten. Definition 1.19 Alle Knoten mit v ∈ V \ {s, t} mit ef (v) > 0 bezeichnen wir als aktive Knoten. Beim Abbau von u ussigem Fluss interessieren uns Kanten, u ¨bersch¨ ¨ ber die wir noch Fluss transportieren k¨ onnen. Definition 1.20 Die Restkapazit¨ at cf (a) einer Kante a ist definiert durch cf (a) = c(a) − f (a). Definition 1.21 Wenn wir nur Kanten mit positiver Restkapazit¨at betrachten, erhalten wir den Restgraph Df = (V, Af ), wobei Af = {a ∈ A | cf (a) > 0}.

1.3. DIE PUSH-/RELABEL–METHODE NACH GOLDBERG UND TARJAN

13

Als letztes ben¨ otigen wir nun noch einen Begriff, der es uns erlaubt festzulegen, wann wir u ¨ ber welche Kante zus¨ atzlichen Fluss schicken d¨ urfen. Hierzu f¨ uhren wir eine Funktion d ein, die jedem Knoten eine “H¨ ohe“ zuordnet. Im Algorithmus werden wir sicherstellen, dass zus¨atzlicher Fluss immer nur zwischen Knoten verschickt wird, deren H¨ ohe sich um genau den Wert 1 unterscheidet (und zwar vom h¨oheren zum niedrigeren Knoten). Dadurch dass man die Knoten sukzessive anhebt, kann auf diese Weise Fluss zun¨ achst Richtung Senke und danach u ussigen Fluss wieder zur¨ uck zur Senke schicken. ¨bersch¨ Definition 1.22 Gegeben sei ein Netzwerk mit Pseudofluss f . Eine Abbildung d : V → N0 mit 1. d(s) = n, d(t) = 0 und 2. d(u) ≤ d(v) + 1 f¨ ur alle (u, v) ∈ Af . heisst zul¨ assige Markierung.

Lemma 1.23 Ist f ein Pr¨afluss und d eine zul¨assige Markierung, dann gibt es in Df keinen s–t–Pfad. Beweis: Wir f¨ uhren einen Beweis durch Widerspruch. Sei also s = v0 , . . . , vl = t ein s–t–Pfad in Df . Dann ist (vi−1 , vi ) ∈ Af f¨ ur alle i ∈ {1, . . . , l} und l ≤ n − 1. Nach Definition gilt f¨ ur die Markierung: n = d(s) = d(v0 ) ≤ d(v1 ) + 1 ≤ (d(v2 ) + 1) + 1 ≤ . . . ≤ d(vl ) + l = d(t) + l = 0 + l ≤ n − 1 Damit haben wir den gew¨ unschten Widerspruch erhalten.

Bemerkung 1.24 Im Beweis von Theorem 1.11 (bei der Definition der Menge W ) haben wir bereits folgende Aussage gesehen: Wenn f ein Fluss ist, dann gilt: f maximal ⇐⇒ Df enth¨alt keinen s–t–Pfad. Lemma 1.25 Ist f ein Pr¨afluss und v ein aktiver Knoten, dann gibt es in Df einen Pfad von v nach s, ¨ d. h. Uberschuss kann immer zur¨ uck zur Quelle transportiert werden. Beweis:

Sei W = {w ∈ V : w ist in Df von v aus erreichbar}.

Wir nehmen nun an, dass s ∈ W und f¨ uhren dies zum Widerspruch. Betrachte alle Kanten (u, w) ∈ A die u uhren, d. h. ¨ ber den Rand“ der Partition von W nach W hinein f¨ ” mit u ∈ W und w ∈ W . Es gilt: (w, u) ∈ Af

0≤

 w∈W

=⇒

ef (w) =

f (w, u) = c(w, u) ≥ 0

  w∈W u∈V

f (u, w) =



=⇒



w∈W u∈V \W





≤0

f (u, w) = −f (w, u) ≤ 0

f (u, w) + 

  w∈W u∈W





f (u, w) ≤ 0 

=0

Das heisst ef (w) = 0 f¨ ur alle w ∈ W und damit insbesondere auch ef (v) = 0. Dies widerspricht unserer Annahme, dass v ein aktiver Knoten ist. Der eigentliche Algorithmus sieht folgendermassen aus:

¨ KAPITEL 1. FLUSSE IN NETZWERKEN

14 Basisalgorithmus // Initialisierung for all (u, v) ∈ A { f (u, v) := 0; if u = s then f (u, v) := c(u, v); if v = s then f (u, v) := −c(u, v); } for all v ∈ V
{ ef (v) = w:(w,v)∈A f (w, v); if v = s then d(v) := n else d(v) := 0; } // Hauptschleife while ( ∃ aktiver Knoten ) F¨ uhre eine (zul¨ assige) Update-Operation durch; Update-Prozeduren

Push(v, w) Anwendbarkeit: v aktiv, (v, w) ∈ Af und d(v) = d(w) + 1 Sende δ := min{ef (v), cf (v, w)} Flusseinheiten von v nach w; Relabel(v) Anwendbarkeit: v aktiv und ∀w ∈ Γ+ (v) gilt (v, w) ∈ Af oder d(w) ≥ d(v) d(v) := min{d(w) + 1|w ∈ Γ+ (v) mit (v, w) ∈ Af }; Lemma 1.26 Invarianten des Basisalgorithmus sind: a) In Relabel(v) wird d(v) um mindestens 1 erh¨oht. b) f ist immer ein Pr¨afluss und d eine zul¨assige Markierung. c) F¨ ur einen aktiven Knoten v kann immer eine der Operationen Push oder Relabel ausgef¨ uhrt werden. d) d(v) ≤ 2n − 1 ∀v ∈ V . Beweis: a) klar. b) Wegen der Wahl von δ ist klar, dass f ein Pr¨afluss ist. Mit Induktion u ¨ ber die Anzahl der Push / Relabel Aufrufe zeigen wir, dass d eine zul¨assige Markierung ist. Induktionsbeginn klar. Induktionsannahme d ist nach k Push / Relabel Aufrufen eine zul¨assige Markierung. Induktionsschluss k ; k + 1 Aufrufe. Wir betrachten die (k+1)te Ausf¨ uhrung einer Push / Relabel Prozedur. Hierbei unterscheiden wir, ob dies ein Push oder ein Relabel Aufruf ist. Relabel(v): Es wird nur d(v) ge¨ andert. • F¨ ur (w, v) ∈ Af gilt Ind. Ann.

d(w)

≤

dalt (v) + 1

a)

≤

dneu (v) + 1

• F¨ ur (v, w) ∈ Af gilt dneu (v) nach Konstruktion.

≤

d(w) + 1

1.3. DIE PUSH-/RELABEL–METHODE NACH GOLDBERG UND TARJAN

15

Push(v, w): Es gibt folgende m¨ ogliche Auswirkungen: • (v, w) wird aus Df entfernt. Dadurch bleibt d sicherlich eine zul¨assige Markierung. ugt. Zu zeigen ist in diesem Fall: d(w) ≤ d(v) + 1. Dies gilt • (w, v) wird zu Df hinzugef¨ nach Konstruktion, da Push(v, w) nur ausgef¨ uhrt wird, wenn d(v) = d(w) + 1. c) F¨ ur alle (v, w) ∈ Af gilt d(v) ≤ d(w) + 1. Falls Push(v, w) nicht anwendbar ist, gilt d(v) < d(w) + 1 ∀(v, w) ∈ Af , d.h. Relabel(v) ist anwendbar. d) Nach Lemma 1.25 existiert im Graphen Df ein Pfad p = (v0 = v, v1 , v2 , . . . , vl = s) von v nach s. D.h. l ≤ 2n − 1 d(v) = d(v0 ) ≤ d(v1 ) + 1 ≤ · · · ≤ d(vl ) + l = d(s) +     =n

≤n−1

Als unmittelbare Folgerung erhalten wir aus Lemma 1.26: Korollar 1.27 Der Basisalgorithmus terminiert mit einem maximalen Fluss. Als n¨ achstes wollen wir noch die maximale Laufzeit des Basisalgorithmus absch¨atzen. Dazu werden wir zun¨ achst Aussagen u ogliche Anzahl von Push bzw. Relabel Aufrufen herleiten. ¨ ber die maximal m¨ Lemma 1.28 Die Anzahl der Relabelings ist kleiner gleich 2n2 . Beweis: Pro Knoten v ∈ V \{s, t} kommen h¨ochstens 2n − 1 Relabelings vor ⇒ Insgesamt sind es maximal (n − 2) · (2n − 1) ≤ 2n2 . Es soll nun auch eine obere Schranke f¨ ur die Anzahl der Pushs gefunden werden. Dazu unterscheidet man zwischen saturierten und nicht saturierten Pushs. Erstere sch¨opfen die Restkapazit¨at einer Kante voll aus, letztere nicht. Lemma 1.29 Die Anzahl der saturierten Pushs ist kleiner gleich n · m. Beweis: Wir betrachten die Kante (v, w) ∈ A. Ein saturierter Push v → w tritt auf, wenn d(v) gleich d(w) + 1 ist. Anschliessend gilt: (v, w) ∈ Af . Vor dem n¨achsten Push von v nach w muss daher ein Push von w nach v erfolgen., d.h. d(w) muss mindestens um 2 erh¨oht werden und anschliessend muss d(v) um mindestens 2 erh¨ oht werden. Daher kann es h¨ochstens n saturierte Pushs v → w geben. Lemma 1.30 Die Anzahl der nicht saturierten Pushs ist kleiner gleich 2n2 m. Beweis:

Wir betrachten das Potential φ :=




d(v). Wie ver¨andert sich das Potential w¨ahrend

v: aktiv

eines Push bzw. Relabel Aufrufs? Wir unterscheiden hierf¨ ur drei F¨alle: ¨ nicht saturierter Push v ist danach nicht mehr aktiv, da durch den Push der gesamte Uberschuss abtransportiert wurde – die Kapazit¨ at der Kante wurde ja nicht voll genutzt. w wird unter Umst¨anden ¨ aktiv, falls der Knoten nicht vorher schon Uberschuss hatte ⇒ φ nimmt um mindestens d(v)−d(w) = 1 ab. saturierter Push Falls vor der Ausf¨ uhrung des Pushs bereits ef (w) > 0 galt, ¨andert sich am Potential durch den Push gar nichts. Andernfalls wird w aktiv ⇒ φ nimmt um h¨ochstens d(w) = d(v) − 1 ≤ 2n − 2 zu ; insgesamt nimmt φ bei saturierten Pushs um h¨ochstens #saturierter Pushs · (2n − 2) ≤ nm · (2n − 2) zu.

¨ KAPITEL 1. FLUSSE IN NETZWERKEN

16

¨ Relabel Wir ermitteln die Anderung des Potentials u ¨ ber alle, sagen wir, r Relabels hinweg. Sei di (v) ∀ i =  0 . . . r, ∀ v ∈ V = V \ {s, t} die Markierung von v nach dem i-ten Relabel. Bei dem i-ten Relabel andert sich das Potential um folgenden Wert: ¨   di (v) − di−1 (v) δi = v: aktiv

v: aktiv

Da ein Relabel immer nur bei aktiven Knoten durchgef¨ uhrt wird, ¨andert sich bei nicht aktiven Knoten sicherlich nichts. Daher gilt auch   δi = di (v) − di−1 (v) v∈V 

v∈V 

Nun summieren wir u ¨ber alle Relabels auf (Anfangs sind alle Markierungen in V  gleich 0):

r r      δi = di (v) − di−1 (v) = dr (v) ≤ 2n2 i=1

i=1

v∈V 

v∈V 

v∈V 

Durch Relabels nimmt das Potential also insgesamt h¨ochstens um 2n2 zu. ⇒ das Potential nimmt insgesamt maximal um nm·(2n− 2)+ 2n2 ≤ 2n2 m (Ohne Einschr¨ankung nehmen wir an, dass m ≥ n gilt – sonst ist das Flussproblem trivial l¨osbar ...) durch Relabels und saturierte Pushs zu. Da das Potential andererseits bei jedem nicht saturiertem Push um mindestens eins abnimmt, ist die Anzahl der nicht saturierten Pushs somit kleiner gleich 2n2 m. Aus den vorangehenden drei Lemmas folgt unmittelbar die Endlichkeit des Basisalgorithmus. F¨ ur eine effiziente Implementierung ben¨ otigen wir nun noch ein m¨oglichst geschicktes Verfahren f¨ ur die Auswahl der n¨ achsten Update-Operation in der Hauptschleife. Dazu f¨ uhren wir noch eine weitere Prozedur ein: Push/Relabel(v). Die Prozedur Push/Relabel(v) f¨ uhrt f¨ ur einen aktiven Knoten v nach M¨oglichkeit eine Push, ansonsten eine Relabel Operation durch. Dazu gibt es f¨ ur jeden Knoten eine Liste der adjazenten Kanten und eine Referenz current edge auf eine dieser Kanten. Zu Beginn (; Initialisierung) zeige current edge auf die erste Kante in der Adjazenzliste. Push/Relabel(v) Sei {v, w} die derzeitige current edge von v; if (Push(v, w) anwendbar) Push(v, w); else { if ({v, w} letzte Kante der Kantenliste von v) { Mache erste Kante der Kantenliste zur current edge; Relabel(v); } else { Ersetze current edge durch die n¨achte Kante der Kantenliste; weiter in der ersten Zeile; } } Lemma 1.31 In Push/Relabel(v) wird Relabel(v) nur ausgef¨ uhrt, wenn es auch erlaubt ist. Beweis: d(w) + 1

F¨ ur alle Kanten oberhalb der current edge gilt zu jedem Zeitpunkt cf (v, w) = 0 oder d(v) <

Satz 1.32 Der Basisalgorithmus mit der Push/Relabel Prozedur bestimmt einen maximalen Fluss in Zeit O(n2 m).

1.3. DIE PUSH-/RELABEL–METHODE NACH GOLDBERG UND TARJAN

17

Beweis: Dass der Algorithmus mit einem maximalen Fluss terminiert wissen wir bereits aus Korollar 1.27. Wir m¨ ussen also nur die behauptete Laufzeit nachweisen. Dazu unterscheiden wir vier Posten: 1. Zeit f¨ ur Relabels, 2. Zeit f¨ ur saturierte Pushs, 3. Zeit f¨ ur nicht saturierte Pushs, 4. Zeit f¨ ur das Durchlaufen der Kantenlisten in Push/Relabel. Ein Relabel hat die Laufzeit O (deg(v)). An jedem Knoten werden 2n Rela
wegen Lemma 1.26 maximal
bels durchgef¨ uhrt ⇒ die Gesamtlaufzeit f¨ ur alle Relabels ist O( n · deg(v)) = O(nm) ( deg(v) = 2m). v

v

Ein Push hat die Laufzeit O(1), wegen Lemma 1.29 und 1.30 haben die Push Operationen insgesamt eine Laufzeit von O(n2 m). Das Abarbeiten der Kantenliste in der Push/Relabel Routine geschieht h¨ochstens 2n − 1 mal pro Knoten, da es maximal so viele Relabels pro Knoten gibt. Zwischen zwei Relabel-Aufrufen wird die Adjazenzliste eines jeden Knotens genau einmal durchlaufen.
Somit ergibt sich als Gesamtlaufzeit f¨ ur das Durchlaufen der Kantenlisten in Push/Relabel: O(n · v∈V deg(v)) = O(nm). Damit ergibt sich folgende Gesamtlaufzeit des Basisalgorithmus: O(nm) + O(n2 m) + O(nm) = O(n2 m)

Durch eine geschickte Auswahl des n¨ achsten mit Push/Relabel zu bearbeitenden aktiven Knoten, kann man die Anzahl der nicht saturierten Pushs reduzieren. Diese sind mit O(n2 m) die gr¨ossten Laufzeitfresser. Es gibt mehrere Auswahlstrategien, die einfachste (FIFO) werden wir n¨aher betrachten. Bei der FIFO-Strategie werden die aktiven Knoten in einer Queue nach dem first-in first-out Prinzip gehalten. Basisalgorithmus mit FIFO-Strategie // Initialisierung . . . wie bisher . . . F¨ uge zus¨ atzliche alle aktiven Knoten in eine Queue Q ein; // Hauptschleife while ( Q nicht leer ) { Entferne den vordersten Knoten v von Q; repeat { Push/Relabel(v); Falls dadurch ein Knoten w aktiv wird, f¨ uge ihn am Ende von Q an; } until ( ef (v) = 0 oder d(v) hat zugenommen ) Falls v noch immer aktiv ist, f¨ uge v am Ende von Q an; } Satz 1.33 Der Basisgorithmus mit Push/Relabel und FIFO-Strategie hat Laufzeit O(n3 ). Beweis: Wir unterteilen den Algorithmus in Phasen. In der ersten Phase werden alle Knoten abgearbeitet, die w¨ ahrend der Initialisierung aktiv wurden. In Phase i + 1 werden die in Phase i eingef¨ ugten Knoten abgearbeitet. Aus der Queue wird ja vorne immer ein Knoten entfernt und bearbeitet und die dadurch neu aktiv gewordenen Knoten werden hinten eingeh¨angt. Wir u achst, dass es maximal 4n2 Phasen gibt. Dazu betrachten wir das folgende Potential: ¨berlegen uns zun¨ φ = max{d(v)|v aktiv}. Zu Beginn und am Ende ist φ = 0. Zun¨ achst zeigen wir, dass in einer Phase ohne Relabeling φ um mindestens eins abnimmt. Dies sieht man folgendermassen ein. F¨ ur alle Knoten w, die durch einen Push(v, w) aktiv werden, gilt d(w) = d(v) − 1. D.h., jeder Knoten der in der Phase aktiv wird hat einen d-Wert, der um eins kleiner ist als der d-Wert des Knotens, der den Push initiiert. Da nach Annahme in der Phase kein Relabel durchgef¨ uhrt wird, muss die repeat/until-Schleife f¨ ur v auf Grund der ersten Bedingung abgebrochen werden, der Knoten v ist also am Ende der Phase nicht mehr aktiv. Daher nimmt φ, das ja das Maximum der d-Werte der

¨ KAPITEL 1. FLUSSE IN NETZWERKEN

18

aktiven Knoten ist, in einer Phase ohne Relabeling sicherlich um mindestens eins ab. Die Anzahl Phasen ohne Relabeling ist daher beschr¨ ankt durch die gesamte Zunahme von φ. Wir sch¨atzen wieder ¨ahnlich wie in Lemma 1.30 ab. Nach dem i-ten Relabel (davor und danach sind dieselben Knoten aktiv) nimmt das Potential um   di (v) − di−1 (v) δi = max{di (v)|v aktiv} − max{di−1 (v)|v aktiv} ≤ v∈V 

v∈V 

¨ zu, mit di und V  wie bei Lemma 1.30. Insgesamt ergibt sich somit eine Anderung von

r r      δi ≤ di (v) − di−1 (v) = dr (v) ≤ 2n2 i=1

i=1

v∈V 

v∈V 

v∈V 

D.h. die gesamte Zunahme von φ ist maximal 2n2 . Damit haben wir also gezeigt, dass die Anzahl Phasen ohne Relabeling durch 2n2 beschr¨ankt ist. Die Anzahl Phasen mit Relabeling ist offensichtlich durch die Anzahl Relabelings und damit gem¨ass Lemma 1.28 ebenfalls durch 2n2 beschr¨ ankt. 2 ⇒ es gibt h¨ ochstens 4n Phasen. Zur¨ uck zur Laufzeit: 1. Zeit f¨ ur Durchlaufen der Kantenlisten in Push/Relabel: O(nm), siehe Beweis von Theorem 1.32. 2. Zeit f¨ ur Relabels: O(nm), siehe Beweis von Theorem 1.32. 3. Zeit f¨ ur saturierte Pushs: O(nm), siehe Beweis von Theorem 1.32. 4. Zeit f¨ ur nicht saturierte Pushs: O(n3 ), da h¨ochstens ein nicht saturierter Push pro Knoten pro Phase auftritt und es maximal 4n2 Phasen gibt.

Ausser der FIFO-Strategie gibt es noch weitere Auswahlstrategien, beispielsweise: • Highest √ Label: es wird jeweils der aktive Knoten mit maximalem d-Wert betrachtet. Laufzeit: O(n2 m) ¨ • Excess Scaling: es wird nur Fluss von Knoten mit gen¨ ugend grossem“ Uberschuss zu Knoten ” 2 ¨ mit gen¨ ugend kleinem“ Uberschuss geschickt. Laufzeit: O(nm + n log cmax ) ” Die Analyse dieser Strategien ist etwas aufwendiger. Wir wollen daher an dieser Stelle darauf verzichten. Der interessierte Leser sei auf das Buch Network Flows von Ahuja, Magnanti und Orlin verwiesen.

Kapitel 2

Matching Probleme 2.1

Definition und Beispiele

Betrachten wir das folgende Zuordnungsproblem. Gegeben ist eine Menge von Rechnern mit verschiedenen Leistungsmerkmalen (Speicher, Geschwindigkeit, Plattenplatz, etc.) und eine Menge von Jobs mit unterschiedlichen Leistungsanforderungen an die Rechner. Gibt es eine M¨oglichkeit, die Jobs so auf die Rechner zu verteilen, dass alle Jobs gleichzeitig bearbeitet werden k¨onnen? Graphentheoretisch k¨onnen wir das Problem wie folgt formulieren: Wir symbolisieren jeden Job und jeden Rechner durch einen Knoten und verbinden einen Job mit einem Rechner genau dann, wenn der Rechner die Leistungsanforderungen des Jobs erf¨ ullt. Gesucht ist dann eine Auswahl der Kanten, die jedem Job genau einen Rechner zuordnet und umgekehrt jedem Rechner h¨ochstens einen Job. Eine solche Teilmenge der Kanten nennt man ein Matching des Graphen. Definition 2.1 Eine Kantenmenge M ⊆ E heisst Matching in einem Graphen G = (V, E), falls kein Knoten des Graphen zu mehr als einer Kante aus M inzident ist, oder formal ausgedr¨ uckt, wenn e∩f =∅

f¨ ur alle e,f ∈ M mit e = f .

Man sagt ein Knoten v wird von M u ¨berdeckt, falls es eine Kante e ∈ M gibt, die v enth¨alt. Ein Matching M heisst perfektes Matching, wenn jeder Knoten durch genau eine Kante aus M u ¨ berdeckt wird, oder, anders ausgedr¨ uckt, wenn |M | = |V |/2. Bemerkung 2.2 Ein Graph enth¨alt im Allgemeinen sehr viele Matchings. Beispielsweise ist M = {e} f¨ ur jede Kante e ∈ E ein Matching. Die folgende Abbildung zeigt ein Matching (links) und ein perfektes Matching (Mitte).

Nicht jeder Graph enth¨alt jedoch ein perfektes Matching. F¨ ur Graphen mit einer ungeraden Anzahl an Knoten ist dies klar. Es gibt aber sogar Graphen mit beliebig vielen Knoten, deren gr¨osstes Matching aus einer einzigen Kante besteht. Dies sind die so genannten Sterngraphen (im Bild rechts), deren Kantenmenge genau aus den zu einem Knoten inzidenten Kanten besteht. Wir werden uns in diesem Kapitel mit der Frage besch¨aftigen, wie man ein bez¨ uglich bestimmten Kriterien optimales Matching bestimmen kann. Genauer werden wir uns zun¨achst der Frage widmen, wie 19

KAPITEL 2. MATCHING PROBLEME

20

man ein Matching mit m¨ oglichst vielen Kanten finden kann. Im zweiten Teil dieses Kapitels verallgemeinern wir dann die Aufgabe dahingehend, dass wir als Eingabe zus¨atzlich zu dem Graphen noch eine Gewichtsfunktion w : E → N eingeben und dann nach einem Matching suchen, dass a) m¨oglichst viele Kanten enth¨ alt und b) unter allen solchen Matchings eines mit m¨oglichst geringem Kantengewicht. Wie sich herausstellen wird, ist der Fall, dass der zu Grunde liegende Graph bipartit ist, wesentlich einfacher. Wir werden daher die beiden F¨ alle bipartiter Graph und beliebiger Graph jeweils separat betrachten. Formal werden wir also in diesem Kapitel die folgenden vier Probleme betrachten: (Ungewichtetes) Matching in bipartiten Graphen Eingabe: Ein zusammenh¨ angender bipartiter Graph G = (A  B, E). Ausgabe: Ein Matching M0 mit |M0 | = max{|M | : M Matching in G}. (Ungewichtetes) Matching in beliebigen Graphen Eingabe: Ein zusammenh¨ angender Graph G = (V, E). Ausgabe: Ein Matching M0 mit |M0 | = max{|M | : M Matching in G}. Gewichtetes Matching in bipartiten Graphen Eingabe: Ein zusammenh¨ angender bipartiter Graph G = (A  B, E) und eine Gewichtsfunktion w : E → N. Ausgabe: Ein Matching M0 mit |M0 | = k und w(M0 ) = min{w(M ) : M Matching in G mit |M | = k}, wobei k = max{|M | : M Matching in G}. Gewichtetes Matching in beliebigen Graphen Eingabe: Ein zusammenh¨ angender Graph G = (V, E) und eine Gewichtsfunktion w : E → N. Ausgabe: Ein Matching M0 mit |M0 | = k und w(M0 ) = min{w(M ) : M Matching in G mit |M | = k}, wobei k = max{|M | : M Matching in G}. Auf den ersten Blick mag die Definition des gewichteten Matchingproblems etwas artifiziell wirken. Wir wollen uns daher zun¨ achst die Definition etwas n¨aher bringen.
Wir beginnen mit einer Formalie: w(M ) bezeichnet das Gesamtgewicht aller Kanten in M , also w(M ) = e∈M w(e). Da wir vorausgesetzt haben, dass die Gewichtsfunktion positiv ist, wird nun auch klar warum wir nach einem Matching mit minimalem Gewicht, aber maximal vielen Kanten suchen. W¨ urden wir die Bedingung an die Anzahl Kanten weglassen, w¨ are das leere Matching (das ja Gewicht Null hat) immer ein optimales Matching. Genau genommen ist die Situation hier ¨ ahnlich zu der bei der Suche nach einem minimalen spannenden Baum. Auch dort wollen wir das Gesamtkantengewicht minimieren - aber unter der Nebenbedingung das die ausgew¨ahlten Kanten einen spannenden Baum bilden. Beim Matchingproblem wird also nur die Nebenbedingung span” nender Baum“ durch kantenmaximales Matching ersetzt“. Noch deutlicher wird die Analogie, wenn der ” Eingabegraph G vollst¨ andig ist. Da in vollst¨andigen Graphen immer ein perfektes Matching existiert, entspricht das Matchingproblem hier der Suche nach einem perfekten Matching minimalen Gewichtes. Dass wir uns bei der Eingabe auf zusammenh¨angende Graphen beschr¨ankt haben, sollte nicht weiter irritieren. F¨ ur nicht zusammenh¨ angende Graphen ergibt sich ein optimales Matching offensichtlich durch Vereinigung optimaler Matchings bez¨ uglich der einzelnen Zusammenhangskomponenten. da die Zusammenhangskomponenten eines Graphens in linearer Zeit einfach bestimmt werden k¨onnen, gen¨ ugt es somit das Matchingproblem f¨ ur zusammenh¨ angende Graphen zu l¨osen. Zum Abschluss dieses Abschnittes wollen wir nun noch einige Anwendungsbeispiele f¨ ur das Matchingproblem vorstellen. Sp¨ ater ... ;-)

2.2 2.2.1

Das ungewichtete Matchingproblem Augmentierende Pfade

Ein wichtiges Konzept f¨ ur die Konstruktion eines maximalen Matchings ist das eines augmentierenden Pfades. Augmentierende Pfade waren uns bereits bei dem Ford-Fulkerson Algorithmus begegnet. Im Zusammenhang mit Matchings sind sie leicht anders definiert.

2.2. DAS UNGEWICHTETE MATCHINGPROBLEM

21

Definition 2.3 Sei G = (V, E) ein Graph; M ein Matching in G. • Ein Pfad heisst M -alternierend (oder kurz alternierend), falls er abwechselnd Kanten aus M und E \ M enth¨alt. • Ein Pfad heisst M -augmentierend (kurz augmentierend), falls er M -alternierend ist und beide Endknoten nicht von M ¨ uberdeckt sind. Man macht sich leicht klar, dass ein M -augmentierender Pfad immer ungerade viele Kanten enth¨ alt, da die Anzahl der Nicht-Matchingkanten die Anzahl der Matchingkanten gem¨ass Definition um Eins u ¨ bertreffen muss. Vertauscht man daher entlang eines M -augmentierenden Pfades Matching und NichtMatching Kanten, so erh¨ oht sich die Kardinalit¨at der Matching-Kanten um Eins. Wir formalisieren diese Beobachtung in der folgenden Proposition. Proposition 2.4 Ist P ein M -augmentierender Pfad f¨ ur ein Matching M , dann gilt: M  := M ⊕ P = (M \ P ) ∪ (P \ M ) ist ein Matching mit |M  | = |M | + 1.

Beweis: Wir zeigen zun¨ achst, dass M  in der Tat ein Matching ist. Angenommen, dies w¨are nicht der Fall. Dann g¨ abe es e1 , e2 ∈ M  mit e1 ∩ e2 = ∅. Folgende drei Konstellationen sind m¨oglich: 1. e1 ∈ M und e2 ∈ M −→ Widerspruch dazu, dass M ein Matching ist. 2. e1 ∈ M und e2 ∈ / M ⇒ e1 ∈ / P, e2 ∈ P . Sei v der gemeinsame Knoten von e1 und e2 . Dann kann v kein Endpunkt von P sein, da v in M u ¨ berdeckt und P nach Annahme M -augmentierend bzgl. M / P , muss folglich von v eine weitere Kante e3 ∈ P ausgehen, die (da P alternierend ist) ist. Da e1 ∈ in M liegen muss. Dies ist jedoch ein Widerspruch zur Voraussetzung, dass M ein Matching ist. 3. e1 ∈ / M und e2 ∈ / M ⇒ e1 ∈ P, e2 ∈ P −→ Widerspruch dazu, dass P M -alternierend ist. M  ist also ein Matching. F¨ ur die Kardinalit¨at von M  gilt: |M  | = |M | − |M ∩ P | + |P \ M |. Da P augmentierend ist, gilt |P \ M | = |P ∩ M | + 1 und somit wie behauptet |M  | = |M | + 1. Proposition 2.4 besagt, dass man aus einem M -augmentierenden Pfad immer ein um Eins gr¨osseres Matching erhalten kann. Der folgenden Satz besagt nun, dass in der Tat noch mehr gilt: Ist M kein kardinalit¨ atsmaximales Matching, so gibt es immer einen M -augmentierenden Pfad, der benutzt werden kann, um M zu vergr¨ ossern. Satz 2.5 Ein Matching M ist genau dann (kardinalit¨ats-)maximal, wenn es keinen M -augmentierenden Pfad gibt. Beweis: ⇒“ Ergibt sich unmittelbar aus Proposition 2.4. ” ⇐“ Sei M ein Matching, das nicht maximal ist. Wir zeigen: es gibt einen M -augmentierenden Pfad. ” Sei Mmax ein (beliebiges) maximales Matching. Betrachte den Subgraphen M ⊕ Mmax (genauer: den durch die Kantenmenge M ⊕ Mmax induzierten Subgraphen). Es gilt – Jeder Knoten hat Grad ≤ 2, d. h. M ⊕ Mmax ist Vereinigung von Kreisen und Pfaden. – Jeder Kreis ist von gerader L¨ ange und enth¨alt die gleiche Anzahl von Kanten aus M wie aus Mmax .

KAPITEL 2. MATCHING PROBLEME

22

– Jeder Pfad enth¨ alt abwechselnd Kanten aus M und Mmax . Wegen |Mmax | > |M | muss es einen Pfad P geben, der mehr Kanten aus Mmax als aus M enth¨alt. Anfangs- und Endkanten von P geh¨oren daher zu Mmax , d. h. die Anfangs- und Endknoten von P sind von M nicht u ¨ berdeckt. Also ist P M -augmentierend.

Aus dem Beweis von Satz 2.5 ergibt sich auch eine obere Schranke f¨ ur die L¨ange eines k¨ urzesten M augmentierenden Pfades. Dies werden wir in Abschnitt 2.2.2 ben¨otigen und wollen sie daher hier noch kurz festhalten. Korollar 2.6 Sei Mmax ein maximales Matching und M ein Matching mit |M | < |Mmax |, in dem der k¨ urzeste M -augmentierenden Pfad, die L¨ange t hat. Dann gilt |M | ≥ |Mmax | − n/t. Beweis: Betrachte wie im Beweis von Theorem 2.5 den Subgraphen M ⊕ Mmax. Da ein Pfad in diesem Graphen h¨ ochstens eine Kante mehr aus Mmax als aus M enthalten kann, enth¨alt M ⊕ Mmax mindestens s := |Mmax | − |M | Pfade Pi (i = 1, . . . , s), die M -augmentierend sind. Die Pfade Pi sind knotendisjunkt und haben nach Annahme alle L¨ ange mindestens t. Es gilt daher s·t≤

s 

|Pi | ≤ n

i=1

und somit |Mmax | − |M | = s ≤ n/t. ¨ Aus obigen Uberlegungen ergibt sich unmittelbar der folgende Ansatz f¨ ur einen Matching-Algorithmus: 1. Starte mit einem beliebigen Matching. (Beispielsweise mit dem leeren Matching oder einem, das der Greedy-Algorithmus gefunden hat). 2. Vergr¨ ossere das Matching sukzessive entlang augmentierender Pfade. (Wie in Proposition 2.4 beschrieben). Zu l¨ osen ist hier lediglich noch die Frage, wie man augmentierende Pfade effizient findet. Diese auf den ersten Blick einfach aussehende Aufgabe ist in der Tat jedoch nicht ganz so einfach. Zumindest f¨ uhrt die nahe liegende Idee, bei einem beliebigen nicht u ¨ berdeckten Knoten anzufangen und einen von dort ausgehenden alternierenden Pfad zu verfolgen, bis man auf einen weiteren nicht u ¨ berdeckten Knoten trifft, nicht notwendiger Weise zum Ziel, wie die nachfolgende Abbildung zeigt.

? = Matching-Kanten

Das Problem hierbei ist, dass man bei der Konstruktion des augmentierenden Pfades auf Knoten treffen kann, die man bereits besucht hat und dadurch das Anfangsst¨ uck des Pfades quasi in umgekehrter Reihenfolge nochmal durchlaufen m¨ usste – was der Definition eines Pfades nat¨ urlich widerspricht. Man beachte jedoch dass dieses Problem nur auftreten kann, wenn der Graph ungerade Kreise enth¨alt. Beschr¨ankt man sich daher auf bipartite Graphen f¨ uhrte die oben angegebene Idee zur Konstruktion augmentierenden Pfade in der Tat zum Ziel, wie wir im n¨achsten Abschnitt sehen werden.

2.2. DAS UNGEWICHTETE MATCHINGPROBLEM

2.2.2

23

Bipartite Graphen

Die einfachste Art ein neues Problem zu l¨osen ist, es auf ein bereits gel¨ostes Problem zur¨ uckzuf¨ uhren. Im Falle des Matchingproblem in bipartiten Graphen ist dies ganz einfach: Wir konstruieren darau ein Flussproblem:

s

A

B

t

A

B

• Richte alle Kanten von A nach B. • Verbinde einen zus¨ atzlichen Knoten s (Quelle) durch gerichtete Kanten mit allen Knoten in A; verbinde alle Knoten in B durch gerichtete Kanten mit einem zus¨atzlichen Knoten t (Senke). • Gebe allen Kanten Kapazit¨ at identisch Eins. Offenbar entspricht dann ein maximales Matching im urspr¨ unglichen Graphen genau einem (ganzzahligen) maximalen Fluss im neuen Graphen. Damit erhalten wir unmittelbar: Satz 2.7 In bipartiten Graphen ist die Bestimmung eines maximalen Matchings in O(nm) Schritten m¨oglich. ¨ Beweis: Uberf¨ uhre das Matchingproblem wie oben beschrieben in ein entsprechendes Flussproblem. Dieses l¨ asst sich (beispielsweise mit dem Algorithmus von Ford und Fulkerson) innerhalb der geforderten Zeitschranke l¨ osen. √ Als n¨ achsten wollen wir die Laufzeit von O(nm) auf O( nm) verbessern. Der entsprechende Algorithmus wurde 1973 von Hopcroft und Karp entwickelt. Er ist noch immer der schnellste Algorithmus, den man f¨ ur das bipartite Matchingproblem kennt. Die zu Grunde liegende Idee ist recht einfach. Wir versuchen, wie im vorangehenden Abschnitt vorgestellt, ausgehend von den von M nicht u urzeste augmentierende Pfade zu finden — ¨ berdeckten Knoten in A k¨ und zwar wenn m¨ oglich mehrere gleichzeitig“. ” Um den Algorithmus etwas genauer skizzieren zu k¨onnen, ben¨otigen wir zun¨achst einige vorbereitende Hilfsaussagen. Lemma 2.8 Sei P ein k¨ urzester M -augmentierender Pfad f¨ ur ein Matching M und P ein beliebiger (M ⊕ P )-augmentierender Pfad. Dann gilt |P | ≥ |P | + 2|P ∩ P | ≥ |P |  := (M ⊕ P ) ⊕ P. Dann gilt (nach Proposition 2.4) |M | = |M | + 2, und M  ⊕ M enth¨ Beweis: Sei M alt daher mindestens zwei knotendisjunkte M -augmentierende Pfade, sagen wir P1 und P2 . ⊕M enth¨ ⊕M = M alt genau die Kanten, die in genau einem der Pfade P und P vorkommen. Daher gilt M    P ⊕ P und somit auch |P ⊕ P | = |M ⊕ M | ≥ |P1 | + |P2 | ≥ 2|P |, da P ein k¨ urzester M -augmentierender Pfad ist. Andererseits ist |P ⊕ P | = |P | + |P | − 2|P ∩ P |. Zusammen also |P | − 2|P ∩ P | ≥ |P |, woraus die Behauptung unmittelbar folgt.

KAPITEL 2. MATCHING PROBLEME

24

Lemma 2.9 Sei M1 , . . . , Mk+1 eine Folge von Matchings und P1 , . . . , Pk eine Folge von augmentierenden Pfaden, wobei gelte urzester Mi -augmentierender Pfad ( i = 1, . . . , k) • Pi ist ein k¨ • Mi+1 = Mi ⊕ Pi ( i = 1, . . . , k) Dann gilt a) |Pi+1 | ≥ |Pi | (i = 1, . . . , k) b) |Pi | = |Pj |, i = j ⇒ Pi und Pj sind knotendisjunkt. Beweis: a) Folgt direkt aus Lemma 2.8. b) Angenommen, dies gilt nicht. Dann w¨ahle i < j mit |Pi | = |Pj |, so dass Pi und Pj nicht knotendisjunkt sind, und j − i minimal bez¨ uglich dieser Eigenschaften ist. Dann gilt f¨ ur alle i + 1 ≤ k <  ≤ j: |Pk | = |P | und Pk und P sind knotendisjunkt. Aus der knotendisjunktheit der Pfade Pi+1 , . . . , Pj folgt aber, dass Pj nicht nur bez¨ uglich Mj sondern auch bez¨ uglich Mi+1 ein augmentierender Pfad ist. Nach Lemma 2.8 gilt daher: |Pj | ≥ |Pi | + 2|Pi ∩ Pj |, woraus wegen |Pi | = |Pj | folgt, dass |Pi ∩ Pj | = 0 sein muss, d. h. Pi und Pj sind kantendisjunkt. Sei nun v beliebig ∈ V (Pi )∩V (Pj ). Da jeder Knoten aus V (Pi ) in Mi+1 = Mi ⊕Pi u ¨berdeckt ist und zwar durch Matchingkanten, die in Pi enthalten sind, enth¨alt jeder Mi+1 -augmentierende Pfade, der einen Knoten von V (Pi ) enth¨ alt auch eine Kante aus Pi . Da Pj ein Mi+1 -augmentierender Pfad ¨ ussen Pi und Pj auch knotendisjunkt ist, der nach obiger Uberlegung kantendisjunkt zu Pj ist, m¨ sein, was unserer Annahme widerspricht.

Das Lemma legt folgenden Ansatz f¨ ur einen Matching-Algorithmus nahe: BipartitesMatching Eingabe: zusammenh¨ angender bipartiter Graph G = (A ∪ B, E). Ausgabe: (kardinalit¨ ats-) maximales Matching M ⊆ E. M = ∅; repeat Bestimme eine (inklusions-) maximale Menge knotendisjunkter k¨ urzester M -augmentierenden Pfade. Augmentiere M entlang dieser Pfade. until (es existiert kein M -augmentierender Pfad). Gem¨ ass Lemma 2.9 muss die L¨ ange eines k¨ urzesten M -augmentierenden Pfades in jeder Iteration der  das Matching, das wir nach √n Iterationen erhalten haben, Schleife zunehmen. Bezeichnen wir mit M -augmentierenden Pfades daher mindestens √n. Aus Korollar 2.6 so betr¨ agt die L¨ ange eines k¨ urzesten M √ | ≥ |Mmax | − n/ n. Der Algorithmus terminiert daher sp¨atestens nach √n weiteren Itefolgt daher |M rationen. Wenn wir also zeigen k¨ onnten, dass man zu einem Matching M in Zeit O(m) eine maximale Menge knotendisjunkter√k¨ urzester M -augmentierenden Pfade bestimmen kann, h¨atten wir einen Algorithmus, der in Zeit O( nm) ein maximales Matching bestimmt. Solch einen Algorithmus werden wir jetzt herleiten. Im Folgenden sei G = (A ∪ B, E) ein zusammenh¨angender bipartiter Graph und M ⊆ E ein Matching in G. Ziel ist es eine (inklusions-) maximale Menge knotendisjunkter k¨ urzester M -augmentierender Pfade zu bestimmen. Hierbei gehen wir folgendermassen vor. Durch eine modifizierte Breitensuche bestimmen wir in Zeit O(m) zun¨ achst die L¨ ange  eines k¨ urzesten M -augmentierenden Pfades. Zus¨atzlich generieren wir dabei einen geeigneten Subgraphen von G, in dem wir in einer zweiten Phase eine maximale Menge knotendisjunkter M -augmentierender Pfade der L¨ ange  durch Tiefensuche bestimmen k¨onnen. Der geeignete“ Subgraph ” von G ist dabei ein Graph G , dessen Knoten sich auf Ebenen“ (engl. layers) L0 , L1 , . . . , L2k+1 verteilen ” f¨ ur die gilt:

2.2. DAS UNGEWICHTETE MATCHINGPROBLEM

25

alt genau die von M nicht u • L0 enth¨ ¨ berdeckten Knoten aus A. alt alle Nachbarknoten der Knoten aus L0 . • L1 enth¨ • F¨ ur alle 1 ≤ i ≤ k gilt: – L2i enth¨ alt alle Knoten, die von Knoten aus L2i−1 u ¨ ber Matchingkanten erreicht werden k¨ onnen. (also Kanten – L2i+1 enth¨ alt alle Knoten, die von Knoten aus L2i u ¨ ber Nicht-Matchingkanten  aus E \ M ) erreicht werden k¨ onnen und die noch nicht in j≤2i Lj enthalten sind. • Die Mengen L1 , L3 , . . . , L2k−3 , L2k−1 enthalten nur von M u ¨ berdeckte Knoten. • L2k+1 ist entweder leer oder enth¨ alt mindestens einen von M nicht u ¨ berdeckten Knoten. • Die Kanten von G bestehen aus allen Matchingkanten zwischen Ebenen L2i−1 und L2i (1 ≤ i ≤ k) und allen Nicht-Matchingkanten zwischen Ebenen L2i und L2i+1 (0 ≤ i ≤ k). Man macht sich leicht klar, dass aus diesen Eigenschaften folgt, dass die L¨ange eines k¨ urzesten M augmentierenden Pfades genau 2k+1 ist bzw. dass, falls L2k+1 leer ist, es keinen M -augmentierenden Pfad gibt. Ist andererseits P irgendein M -augmentierender Pfad der L¨ange 2k + 1, dann ist P in G enthalten. F¨ ur die Bestimmung einer maximalen Menge knotendisjunkter M -augmentierender Pfade k¨onnen wir uns anken. Da wir nur an k¨ urzesten augmentierenden Pfaden interessiert sind, wissen wir daher auf G beschr¨ zus¨ atzlich, dass die zu bestimmenden Pfade genau einen Knoten von jedem Levels enthalten m¨ ussen. Wir k¨ onnen uns G daher auch als gerichteten Graphen vorstellen, wobei die Kanten jeweils von der gr¨osseren zur kleineren Ebene gerichtet sind. Die gesuchte maximale Menge knotendisjunkter M -augmentierender Pfade k¨onnen wir dann wie folgt bestimmen. Wir starten bei einem beliebigen nicht u ¨berdeckten Knoten der untersten Ebene eine Tiefensuche, die wir abbrechen sobald wir einen Knoten der obersten Ebene erreichen. Haben wir einen Knoten der obersten Ebene erreicht, definiert uns dies einen augmentierenden Pfad, den wir zu unserer Menge hinzuf¨ ugen. Dann l¨ oschen wir alle w¨ahrend der Tiefensuche besuchten Knoten und starten in dem verbliebenen Graphen von einem anderen von M nicht u ¨ berdeckten Knoten der untersten Ebene erneut eine Tiefensuche. Diesen Prozess wiederholen wir so lange, bis die unterste Ebene keinen weiteren von M nicht u alt. ¨ berdeckten Knoten mehr enth¨ Unmittelbar einsichtig sollte sein, dass in jeder der beiden Phasen, also Aufbau des Layergraphen G und Konstruktion der augmentierenden Pfade, jede Kante des Graphen h¨ochstens zweimal angefasst wird. Damit haben wir also in der Tat die gew¨ unschte Laufzeit von O(m) erhalten. Wir formulieren den Algorithmus nun noch etwas formaler. AugmentierendePfade Eingabe: zusammenh¨ angender bipartiter Graph G = (A ∪ B, E), Matching M ⊆ E. Ausgabe: (inklusions-) maximale Menge knotendisjunkter k¨ urzester M -augmentierender Pfade // Konstruiere Layergraph G = (V  , E  ) E  := ∅; X, L0 := ∅; for all v ∈ A, v nicht u ¨berdeckt do L0 := L0 ∪ {v}; for all {v, w} ∈ E do E  := E  ∪ {(w, v)}; X := X ∪ {w};  V := L0 ∪ X; while (X = ∅) and (X enth¨ alt nur u ¨ berdeckte Knoten) do // folge Matchingkanten von X in die Menge A Y := ∅; for all v ∈ X und {v, w} ∈ M do Y := Y ∪ {w}; E  := E  ∪ {(w, v)};  V := V  ∪ Y ; // folge Nicht-Matchingkanten von Y in die Menge B X := ∅;

KAPITEL 2. MATCHING PROBLEME

26

for all v ∈ Y und {v, w} ∈ E \ M do if (w ∈ V  ) then { X := X ∪ {w}; E  := E  ∪ {(w, v)}; }  V := V  ∪ X; if (X = ∅) then stop; // M ist maximales Matching; // Starte bei jedem nicht u ¨ berdeckten Knoten aus X eine Tiefensuche P := ∅; for all v ∈ X, v nicht u ¨berdeckt do Starte eine Tiefensuche in v, stoppe sobald ein Knoten aus L0 erreicht wird; if (Knoten aus L0 erreicht) then Sei P der gefundene Pfad von v zu dem Knoten aus L0 ; P := P ∪ {P }; Entferne alle bei der Tiefensuche besuchten Knoten aus V  und alle inzidenten Kanten aus E  ; Gebe P aus; ¨ Der folgende Satz fasst die vorangegangenen Uberlegungen nochmals zusammen. Satz 2.10 (Hopcroft, Karp) Der Algorithmus BipartitesMatching bei dem jede Iteration√der repeatSchleife durch den Algorithmus AugmentierendePfade realisiert wird, findet in Zeit O( nm) ein maximales Matching. Um den Ablauf einer Iteration des Algorithmus zu illustrieren betrachten wir den folgenden bipartiten Graphen mit Knotenmenge A = {1, 2, 3, 4, 5, 6} und B = {a, b, c, d, e, f }. Die fett gezeichneten Kanten stellen dabei die Kanten des aktuellen Matchings M dar. Die nicht u ¨berdeckten Knoten sind dick umrandet. Es sind dies die Knoten 1 und 4 in A und die Knoten c und e in der Menge B. 1

2

3

4

5

6

a

b

c

d

e

f

Den Aufbau des Levelgraphen beginnt man mit den nicht u ¨ berdeckten Knoten in A, in diesem Fall also mit den Knoten 1 und 4. Deren Nachbarn kommen in den n¨achsten Level, in dem Beispiel sind dies die Knoten a, b und d. Alle diese Knoten sind u ¨ berdeckt, wir bauen daher einen neuen Level auf, der aus den Endknoten der Matchingkanten besteht, die die Knoten dieses Levels u ¨berdecken; im Beispiel sind dies die Knoten 2, 3 und 6. Von diesen Knoten verfolgen wir wieder alle Nicht-Matchingkanten und erhalten die Knoten c, e und f . Diesmal sind nicht u ¨ berdeckte Knoten in der Menge enthalten und der Aufbau des Levelgraphen ist beendet. Level 0:

1

Level 1:

a

Level 2:

Level 3:

4

b

2

d

3

c

6

e

f

F¨ ur die Bestimmung der augmentierenden Pfade starten wir an einem (beliebigen) nicht u ¨ berdeckten Knoten im untersten Level eine Tiefensuche. Startet man in dem Knoten c k¨onnte man beispielsweise

2.2. DAS UNGEWICHTETE MATCHINGPROBLEM

27

den Pfad (c, 2, a, 1) erhalten. Alle bei der Tiefensuche besuchten Knoten werden entfernt und es wird eine neue Tiefensuche am Knoten e gestartet. Diesmal ergibt sich der Pfad (e, 3, b, 4). Nach Invertierung der Kanten entlang dieser beiden Pfade ergibt sich das folgende Matching, das bereits perfekt ist. 1

2

3

4

5

6

a

b

c

d

e

f

Man beachte, dass die Auswahl der Pfade nicht deterministisch ist. Im ersten Schritt h¨atten wir beispielsweise auch den Pfad (c, 3, b, 4) w¨ ahlen k¨onnen. Die anschliessende Tiefensuche von e aus h¨atte dann keinen Erfolg mehr gehabt. Der Pfad (c, 3, b, 4) stellt daher, ebenso wie die beiden Pfade (c, 2, a, 1) und (c, 2, a, 1), eine maximale Menge knotendisjunkter k¨ urzester augmentierenden Pfade dar. Das Beispiel zeigt daher auch, dass solche maximalen Mengen nicht notwendigerweise die gleiche Anzahl Pfade enthalten m¨ ussen. F¨ ur die Korrektheit und Einhaltung der Laufzeitschranke des Algorithmus ist es nicht erforderlich, dass wir eine maximale Menge mit m¨oglichst vielen Pfaden w¨ahlen, jede maximale Menge ist ausreichend. Der Leser m¨ oge sich an obigen Beispiel davon u ¨ berzeugen, dass auch bei Auswahl des Pfades (c, 3, b, 4) der k¨ urzeste augmentierende in dem dadurch entstehenden Graphen aus mehr als drei Kanten besteht. Abschliessend wenden wir wenden uns noch kurz der Frage zu, wann ein bipartiter Graph ein perfektes Matching enth¨ alt. Der Stern aus Bemerkung 2.2 zeigt uns bereits, dass auch in bipartiten Graphen ein perfektes Matching nicht immer existieren muss – ganz im Gegenteil, es kann durchaus sein, dass das gr¨ osste Matching aus nur einer Kante besteht. Der folgende Satz von Hall, in der Literatur oft auch unter der Bezeichnung Heiratssatz“ bekannt ” (warum?!), gibt eine notwendige und hinreichende Bedingung an, unter der ein Matching in einem bipartiten Graphen existiert, das alle Knoten einer Partition u ¨ berdeckt. Satz 2.11 (Hall) Sei G = (A  B, E) ein bipartiter Graph mit |A| ≤ |B|. Dann gilt: ur alle X ⊆ A. Es existiert ein Matching M der Kardinalit¨at |M | = |A| ⇐⇒ |Γ(X)| ≥ |X| f¨ Beweis: ⇒“ Dies ist unmittelbar einsichtig. ” ⇐“ Sei M ein maximales Matching in G. Setze ” X0 X

= =

{u ∈ A | u nicht u ¨ berdeckt } {u ∈ A | ∃ s ∈ X0 und ∃ M -alternierender Pfad von s nach u}

Y

=

{u ∈ B | ∃ s ∈ X0 und ∃ M -alternierender Pfad von s nach u}

Dann gilt offensichtlich: – Γ(X) ⊆ Y – Jeder Knoten in Y wird von M u ¨ berdeckt (sonst g¨abe es einen augmentierenden Pfad, im Widerspruch zur Maximalit¨ at von M ) ⇒ |X \ X0 | = |Y |. Also |X0 | + |X \ X0 | = |X| ≤ |Γ(X)| ≤ |Y |   = |Y |

⇒

|X0 | = 0.

KAPITEL 2. MATCHING PROBLEME

28

2.2.3

Matching in allgemeinen Graphen

Dieses Problem ist, vor allem wegen der Existenz ungerader Kreise, schwieriger als das Matching in bipartiten Graphen. ¨ Die Grundidee der augmentierenden Pfade k¨onnen wir aber u m¨ ussen wir uns ledig¨ bernehmen. Uberlegen lich, wie wir mit den Abschnitt 2.2.1 bereits angedeuteten Problemfall“ der ungeraden Kreise umgehen. ” Dazu f¨ uhren wir zun¨ achst einige Begriffe ein. Definition 2.12 Sei G = (V, E) ein Graph und M ⊆ E ein Matching. Einen ungeraden Kreis C, der genau (|C| − 1)/2 Matchingkanten enth¨alt, nennen wir eine Bl¨ ute (bez¨ uglich M ). Den einzigen nicht von diesen Matchingkanten u berdeckten Knoten von C nennen wir die Knospe von C. Ein alternierender Pfad ¨ P heisst Stiel der Bl¨ ute C, falls er in einem nicht u berdeckten Knoten beginnt und mit einer Matchingkante ¨ in der Knospe von C endet. An obiger Zeichnung kann man sich sofort eine wichtige Eigenschaft einer Bl¨ ute verdeutlichen: Von Startknoten des Stiels einer Bl¨ ute gibt es einen mit einer Matchingkante endenden alternierenden Pfad zu jedem Knoten der Bl¨ ute. Dies gilt, da wir nach Betreten der Bl¨ ute in der Knopse entwerder links ” rum“ oder rechts rum“ laufen k¨ onnen. Zur sp¨ateren Verwendung halten diese Beobachtung nochmals ” formal fest. Lemma 2.13 Ist C eine Bl¨ ute bez¨ uglich eines Matchings M und P ein Stiel von C, der in einem nicht uberdeckten Knoten u beginnt, so gibt es von u zu jedem Knoten v ∈ V (C) einen alternierenden Pfad, ¨ der in v mit einer Matchingkante endet. Die Grundidee eines Matchingalgorithmus f¨ ur beliebige Graphen ist es, wie bei bipartiten Graphen nach augmentierenden Pfaden zu suchen. Trifft man dabei auf ein Problem“, sprich eine Bl¨ ute, so besei” ” tigt“ man dieses Problem und beginnt danach die Suche nach einem augmentierenden Pfad von Neuem. Das Beseitigen“ der Bl¨ ute besteht darin, dass wir alle Knoten der Bl¨ ute zu einem einzigen Knoten ” kontrahieren. Die folgenden Zeichnung veranschaulicht dies an einem Beispiel. Knospe

Blute

Stiel

Wir legen noch etwas Notation fest. Ist C eine Bl¨ ute, dann bezeichnen wir mit G/C denjenigen Graphen, in dem wir alle Knoten aus V (C) und die damit inzidenten Kanten durch einen (einzigen) neuen Knoten vC ersetzen, der genau zu den Knoten ausserhalb von C verbunden ist, zu denen mindestens ein Knoten von C verbunden war. Mit M/C bezeichnen wir die Restriktion des Matchings M auf G/C (bei der wir aus M alle Kanten in C entfernen und bei der letzten (Matching-)Kante des Stiels den Knoten aus C durch den Knoten vC ersetzen.

2.2. DAS UNGEWICHTETE MATCHINGPROBLEM

29

Die f¨ ur unsere Zwecke fundamentale Eigenschaft dieser Konstruktion ist, dass augmentierenden Pfade in G/C augmentierenden Pfaden in G entsprechen. Satz 2.14 Sei G = (V, E) ein Graph, M ⊆ E ein Matching und C eine Bl¨ ute mit Stiel S bez¨ uglich M . Dann gilt: a) Ist P ein augmentierender Pfad in G/C, so entspricht dieser auf kanonische Art und Weise einem augmentierenden Pfad in G. b) Ist M/C ein maximales Matching in G/C, dann ist auch M ein maximales Matching in G. Beweis: a) Enth¨ alt P den Knoten vc nicht oder ist vC Endpunkt von P , so ist die Aussage trivialerweise richtig. Sei daher P = (u, . . . , x, vC , y, . . . , w), wobei ohne Einschr¨ankung {x, vC } eine Matchingkante sei. Nach Definition von G/C gibt es Knoten c1 und c2 in C, so dass {x, c1 } ∈ M und {c2 , y} ∈ E \ M gilt. Dann ist (u, . . . , x, c1 ) ein Stiel der Bl¨ ute C und gem¨ass Lemma 2.13 gibt es daher in G einen alternierenden Pfad zum Knoten c2 , der mit einer Matchingkante endet. Erg¨anzen wir diesen Pfad durch den Pfad (c2 , y, . . . , w), so erhalten wir damit einen M -augmentierenden Pfad in G.

C

vC

b) Angenommen dies w¨ are nicht der Fall. Dann gibt es mindestens ein Gegenbeispiel. Unter allen solchen w¨ ahlen wir eines mit m¨ oglichst wenig Knoten. Sei also G = (V, E) ein Graph mit kleinstem |V | f¨ ur das es ein Matching M und eine Bl¨ ute C gibt, so dass M nicht maximal in G ist, aber M/C maximal in G/C. Gem¨ ass Satz 2.5 gibt es einen M -augmentierenden Pfad P in G. Der Stil der Bl¨ ute C ist im Allgemeinen nicht eindeutig. Unter allen m¨ oglichen Stielen fixieren wir einen Stiel S, der die Anzahl Kanten in S, die nicht zu P geh¨ oren minimiert. Wir unterscheiden nun verschiedene F¨ alle und werden jeweils zeigen, dass – im Widerspruch zur Annahme – auch G/C einen (M/C)-augmentierenden Pfad enth¨alt. 1. Fall: P enth¨ alt keinen Knoten aus C. Dann w¨are P auch ein M/C-augmentierender Pfad in G/C. Widerspruch! 2. Fall: P enth¨ alt genau einen Knoten aus C. Da P alternierend ist, muss das genau die Knospe von C sein (und der Stiel von C daher leer sein). Daraus folgt sofort, dass P auch ein augmentierender Pfad in G/C ist. Widerspruch! 3. Fall: P enth¨ alt mindestens zwei Knoten aus C. Dann sei P1 das l¨angste Anfangsst¨ uck von P , das genau einen Knoten aus C enth¨ alt, und P2 das l¨angste Endst¨ uck von P , das genau einen Knoten aus C enth¨ alt. Es seien x1 bzw x2 diese entsprechenden Knoten aus C und xi die Nachbarknoten von xi aud Pi .

KAPITEL 2. MATCHING PROBLEME

30

P2 P1

C

Fall 3.a: Einer der beiden Kanten {xi , xi }, ohne Einschr¨ankung sei dies {x1 , x1 }, ist eine Matchingkante. Dann muss x1 die Knospe von C sein (woraus sofort folgt, dass {x2 , x2 } nicht ebenfalls eine Matchingkante sein kann). Ersetzen wir nun in P1 die Kante {x1 , x1 } durch die (Matching-)Kante {x1 , vc } und in P2 die Kante {x2 , x2 } durch die Kante {vc , x2 }, so erhalten wir hierdurch einen (M \ C)-augmentierenden Pfad in G/C. Fall 3.b: Beide Kanten {xi , xi } sind keine Matchingkanten. Ist mindestens einer der beiden Pfade Pi knotendisjunkt zum Stiel S der Bl¨ ute, so bildet S zusammen mit diesem Pfad einen augmentierenden Pfad in G/C. Andernfalls starte man in der Knospe und durchlaufe den Stiel, bis man einen Knoten trifft, der zu P1 oder P2 geh¨ ort. Sei y dieser Knoten und dieser geh¨ore o.E. zu P1 . Startend in y sei S  das l¨angste Teilst¨ uck des Stiels, das vollst¨ andig zu P1 geh¨ ort und y  der Endpunkt von S  . Wir unterscheiden nun wieder zwei F¨ alle: Fall 3.b.1: P1 durchl¨ auft S  in Richtung y  zu y. In anderem Worten: Startet man im Anfangspunkt von P , so trifft man erst auf y  und dann auf y. Setzen wir nun P1 als das Anfangsst¨ uck von P1 bis y  , erg¨anzt   durch den Stiel von y bis zur Knopse, so bildet P1 zusammen mit P2 einen (M/C)-augmentierenden Pfade in G/C. Widerspruch! P2

P1

S

y

y’

C

Fall 3.b.2: P1 durchl¨ auft S  in Richtung y zu y  . Hier unterscheiden wir wiederum zwei F¨alle. Fall 3.b.2.a: P1 hat mit dem Stiel genau die Knoten aus S  gemeinsam. In diesem Fall erh¨alt man einen (M/C)-augmentierenden Pfad f¨ ur G/C, in dem man P1 bis y durchl¨auft und dann den Stiel Richtung y  bis hin zum Endpunkt.

P1 y’

S

P2

y

C

Fall 3.b.2.b: P1 hat mit dem Stiel zus¨ atzlich zu den Knoten aus S  mindestens einen weiteren Knoten gemeinsam. Wir bezeichnen mit z den ersten Knoten des Stiels, den wir treffen wenn wir P1 vom Anfangspunkt aus durchlaufen. Beachte, dass nach Annahme z = y sein muss. Der Knoten z ist mit einer zum Stiel geh¨ orenden Matchingkante {z, z } inzident. Diese zeigt (von z aus gesehen) entweder in Richtung Knospe oder in Richtung Anfangspunkt.

2.2. DAS UNGEWICHTETE MATCHINGPROBLEM

31

P1

S

z’

z

P2

y’ y

C

P1

Fall 3.b.2.b.1: Die Matchingkante {z, z } zeigt in Richtung Anfangspunkt. Dann erh¨alt man einen (M/C)augmentierenden Pfad f¨ ur G/C, in dem man P1 bis z durchl¨auft und dann weiter auf dem Stiel bis zum Anfangspunkt l¨ auft. Fall 3.b.2.b.2: Die Matchingkante {z, z  } zeigt in Richtung Knospe. Der Pfad P1 durchl¨auft daher den Stiel startend in z in Richtung Knospe. Da er nach Annahme y vor y  trifft, muss P1 den Pfad wieder verlassen, sagen wir in w. Sei x der erste Knoten von P1 nach w, der wieder zu P1 geh¨ort. Wieder wissen wir, dass der Knoten x zu einer zum Stiel geh¨orenden Matchingkante {x, x } inzident ist. urden wir durch Durchlaufen Fall 3.b.2.b.2.a: Die Matchingkante {x, x } zeigt in Richtung Knospe. Dann w¨ von P1 bis x und dann des Stiels bis zur Knospe eine Stiel erhalten, der mehr Kanten mit P gemeinsam hat als S. Nach Wahl von S kann dies nicht sein.

P1 S

z

z’

P2

y’

w x

y

x’

C P1

Fall 3.b.2.b.2.b: Die Matchingkante {x, x } zeigt in Richtung Anfangspunkt des Stiels. Dann ist das uck des Stiels zwischen w und x eine Bl¨ ute C  mit Pfadst¨ uck von P1 zwischen w und x und das Pfadst¨ Knospe x. Nun kommt unsere letzte Fallunterscheidung: Fall 3.b.2.b.2.b.1: P2 enth¨ alt mindestens einen Knoten des Pfadst¨ uckes des Stiels zwischen w und x. Es sei w der erste solche Knoten. Dann erh¨ alt man einen (M/C)-augmentierenden Pfad, indem man P2 bis w durchl¨ auft, dann die Bl¨ ute C  bis zur Knospe w und von dort zur¨ uck zum Anfangspunkt von P1 .

KAPITEL 2. MATCHING PROBLEME

32 P1 S

z’

z

w’

y’

x’

w

P2

y

x

C

P1 P2

Fall 3.b.2.a.2.b.2: P2 enth¨ alt keinen Knoten des Pfadst¨ uckes des Stiels zwischen w und x. Dann k¨onnen wir die Bl¨ ute C  kontrahieren, erhalten in G/C  wieder einen augmentierende Pfad und somit – da G nach Annahme das kleinste Gegenbeispiel war – auch einen augmentierenden Pfad in (G/C  )/C, was nach Teil a) des Lemmas (hier verwenden wird, dass (G/C  )/C = (G/C)/C  ) ist) auch zu einem augmentierenden Pfad in G/C f¨ uhrt. D.h. auch dieser Fall ist nicht m¨oglich und unser Beweis ist damit vollst¨andig. P1

C’ S

z

z’ w

P2

y’

x’ x

y

C

P1

Mit Hilfe von Satz 2.14 ist ein Algorithmus f¨ ur das gewichtete Matchingproblem nun schnell formuliert. Matching Eingabe: zusammenh¨ angender Graph G = (V, E). Ausgabe: (kardinalit¨ ats-) maximales Matching M ⊆ E. M = ∅; repeat Starte in allen nicht-¨ uberdeckten Knoten eine parallele Breitensuche (analog wie bei den bipartiten Graphen). Sobald eine Bl¨ ute entdeckt wird, kontrahiere diese und starte die Breitensuche erneut. if (augmentierender Pfad wird gefunden) then Augmentiere entlang des Pfades; expandiere dabei alle eventuell kontrahierten Bl¨ uten entsprechend dem Beweis von Satz 2.14. until (es existiert kein M -augmentierender Pfad) Die Korrektheit des Algorithmus folgt wegen Satz 2.5 unmittelbar aus Satz 2.14. Die Laufzeit l¨ asst sich wie folgt absch¨ atzen. Da in einem Graphen mit n Knoten ein maximales Matching h¨ochstens n/2 Kanten enth¨alt, wird die repeat-Schleife h¨ochstens n/2 mal durchlaufen. Innerhalb jeder Iteration k¨onnen h¨ ochstens n/2 Bl¨ uten kontrahiert werden, da die Anzahl Knoten bei jeder Kontraktion um mindestens zwei abnimmt. F¨ ur die Breitensuche ben¨ otigen wir Zeit O(m), die Augmentierung entlang eines Pfades kostet O(n) Zeit, wobei wir pro Extraktion einer Bl¨ ute sicherlich mit Zeit O(m) auskommen. Insgesamt erhalten wir somit: Satz 2.15 Der Algorithmus Matching findet in Zeit O(n2 · m) ein maximales Matching.

2.3. DAS GEWICHTETE MATCHINGPROBLEM

33

Bemerkung 2.16 Die Laufzeit l¨asst sich auf zweierlei Arten noch verbessern. Zun¨achst kann man sich uberlegen, dass bei Verwendung geeigneter Datenstrukturen die Breitensuche nach Kontraktion eines Kno¨ tens nicht neu gestartet werden muss und daher pro Iteration insgesamt nur Zeit O(m) verbraucht – unabh¨angig von der Anzahl der kontrahierten Bl¨ uten. Analog kann man auch den Augmentierungsschritt in O(m) realiseren, ebenfalls unabh¨angig von der Anzahl Bl¨ uten. Damit ergibt sich eine Laufzeit von O(nm). √ Diese l¨asst sich dann noch auf O( nm) verbessern, in dem man, analog zum bipartiten Fall, m¨oglichst viele Pfade gleichzeitig betrachtet. Die technischen Details sind hier allerdings viel, viel aufwendiger (vgl. die Arbeiten von Micali und Vazirani (1980) und Vazirani (1994)).

2.3

Das gewichtete Matchingproblem

Ein in der kombinatorischen Optimierung sehr beliebter Ansatz f¨ ur die L¨osung gewichteter Probleme ist die so genannte primal-duale Methode der linearen Programmierung. Diese erm¨oglicht es die L¨osung eines gewichteten Problems auf die L¨ osung (einer Sequenz) von ungewichteten Problemen zu reduzieren. Dieser Ansatz kommt auch bei den meisten Algorithmen zur L¨osung des gewichteten Matchingproblems zum Einsatz. In diesem Kapitel werden wir einen solchen Algorithmus vorstellen. Die so genannte ungarische Methode zur L¨ osung des gewichteten Matchingproblems in vollst¨andigen bipartiten Graphen. Wir werden uns dabei jedoch nicht explizit auf die primal-duale Methode beziehen, sondern den Algorithmus ohne zus¨ atzliche Annahmen vollst¨ andig herleiten. Einzig die Frage, wie man denn auf einen solchen Algorithmus kommt, wird dabei unbeantwortet bleiben. Um letztendlich auch diese Frage zu beantworten, stellen wir anschliessend in einem kurzen Exkurs die Grundelemente der primal-dualen Methode vor. Einen Algorithmus f¨ ur das gewichtete Matchingproblem in allgemeinen Graphen werden wir dem Leser schuldig bleiben (m¨ ussen), da alle hierf¨ ur bekannten Algorithmen den Rahmen der Vorlesung sprengen. Wir werden aber in Abschnitt 2.3.3 zumindest noch einige grundlegenden Ans¨atze und Ideen beschreiben.

2.3.1

Bipartite Graphen

In diesem Abschnitt sei G = (A ∪ B, A × B) ein vollst¨andiger bipartiter Graph mit |A| = |B| = n und w : A × B → R eine Gewichtsfunktion. Zur Vereinfachung der Notation sei A = {a1 , . . . , an } und B = {b1 , . . . , bn }. Dann k¨ onnen wir die Gewichtsfunktion auch als n × n Matrix W = (wij ) darstellen, wobei wij = w(ai , bj ). Auf der Knotenmenge A ∪ B definieren wir eine Markierungsfunktion  : A ∪ B → R und nennen diese zul¨assig, falls gilt f¨ ur alle 1 ≤ i, j ≤ n. (2.1) (ai ) + (bj ) ≤ w(ai , bj ) Zu einer (zul¨ assigen) Markierungsfunktion  bezeichnen wir mit G = (V, E ) denjenigen Subgraphen von G, der genau die Kanten enth¨ alt, bei denen (2.1) mit Gleichheit gilt. Also E = { {ai , bj } | 1 ≤ i, j ≤ n und (ai ) + (bj ) = w(ai , bj )}. Die folgende Proposition zeigt, dass man sich auf die Bestimmung eines perfekten Matchings in G beschr¨ anken kann — so man die richtige“ Markierungsfunktion gew¨ahlt hat. ” Proposition 2.17 Ist  eine zul¨assige Markierungsfunktion und M ein perfektes Matching in G , so ist M ein (gewichts-)minimales perfektes Matching in G. Beweis:

Wir bestimmen zun¨ achst das Gewicht des Matchings M . Es gilt

    w(M ) = w(e) = (v) = (v), e∈M

e∈M

v∈e

v∈A∪B

KAPITEL 2. MATCHING PROBLEME

34

wobei die zweite Gleichheit gilt, da M nur Kanten aus G enth¨alt, und die dritte Gleichheit aus der Tatsache folgt, dass M ein perfektes Matching ist.  ein beliebiges perfektes Matching in G. Dann gilt analog, wobei wir nun verwenden, dass  Sei nun M eine zul¨ assige Markierungsfunktion ist: ) = w(M

 e∈M

(2.1)

w(e) ≥

 e∈M



 v∈e

(v)

=



(v) = w(M ).

v∈A∪B

Die Idee ist nun die folgende: Wir starten mit einer beliebigen zul¨assigen Markierungsfunktion (beispielsweise f¨ ur alle i = 1, . . . , n mit (ai ) = min1≤j≤n w(ai , bj ) und (bi ) = 0). F¨ ur diese wird G wahrscheinlich kein perfektes Matching enthalten. Wir bestimmen daher lediglich ein gr¨osstes Matching in G und versuugt werden chen dann die Markierungsfunktion so zu ver¨andern, dass zus¨atzliche Kanten zu G hinzugef¨ k¨ onnen – und zwar ohne die im Matching bereits vorhandenen Kanten zu verlieren. Genauer gehen wir wie folgt vor: GewichtetesBipartitesMatching Eingabe: vollst¨ andiger bipartiter Graph G = (A ∪ B, A × B) mit Gewichtsfunktion w : A×B → R. Ausgabe: (gewichts-) minimales perfektes Matching M . Setze (ai ) := min1≤j≤n w(ai , bj ) und (bi ) := 0 f¨ ur alle i = 1, . . . , n. Bestimme zugeh¨ origen Graphen G . M := ∅. repeat repeat S0 := {a ∈ A | a nicht von M u ¨berdeckt}; S := {a ∈ A | es gibt einen M alternierenden Pfad von einem Knoten aus S0 zu a}. T := {b ∈ B | es gibt einen M alternierenden Pfad von einem Knoten aus S0 zu b}. if (alle Knoten in T sind von M u ¨ berdeckt) then λ := min{w(a, b) − ((a) + (b)) | a ∈ S, b ∈ B \ T }. Setze (a) := (a) + λ f¨ ur alle a ∈ S und (b) := (b) − λ f¨ ur alle b ∈ T . Adaptiere G an die ver¨anderte Markierungsfunktion. until (T enth¨ alt einen nicht von M u ¨berdeckten Knoten); Sei b0 ∈ T ein nicht von M u ¨berdeckter Knoten und P ein M -alternierender (und damit augmentierender) Pfad von einem Knoten in S0 zu b0 . Setze M := M ⊕ P . until (M perfektes Matching); Bevor wir die Laufzeit des Algorithmus betrachten, wollen wir uns zun¨achst von dessen Korrektheit u ¨ berzeugen. Die ¨ aussere repeat-Schleife ist unkritisch: Der Knoten b0 existiert gem¨ass der Abbruchbedingung der inneren repeat-Schleife, der Pfad P existiert gem¨ass der Definition von T . Zeigen m¨ ussen wir daher lediglich, dass die innere repeat-Schleife terminiert. Die Grundidee hier ist, dass die Markierungsfunktion so ge¨andert wird, dass einerseits alle Matchingkanten und alle Kanten, die bislang bei den alternierenden Pfaden, die zur Definition der Mengen S (beachte, uhrt haben, in G verbleiben. Dass aber andererseits mindestens eine Kante zu dass S0 ⊆ S) und T gef¨ G hinzugef¨ ugt wird, die in der n¨ achsten Iteration zu einer (echten) Vergr¨osserung der Menge T f¨ uhren wird. Da das aktuelle Matching M nach Annahme noch nicht perfekt ist, muss daher T sp¨atestens nach n Iterationen der inneren repeat-Schleife einen nicht u ¨berdeckten Knoten enthalten. Um uns davon zu u ¨ berzeugen, dass der Algorithmus all die eben genannten Eigenschaften hat, unterscheiden wir vier verschiedene Kantentypen: • Kanten zwischen S und T : Da wir den -Wert bei allen Knoten aus S um λ erh¨ohen, bei allen Knoten aus T jedoch um λ erniedrigen, bleibt die Bedingung (2.1) f¨ ur alle Kanten, f¨ ur die sie zuvor erf¨ ullt war (und die somit oren), weiterhin erf¨ ullt. zu G geh¨

2.3. DAS GEWICHTETE MATCHINGPROBLEM

35

• Kanten zwischen A \ S und B \ T : Da der -Wert weder f¨ ur Knoten aus A \ S noch f¨ ur Knoten aus B \ T ge¨andert wird, geh¨oren auch ¨ von diesen Kantentypen vor und nach der Anderung von  die gleichen Kanten zu G . • Kanten zwischen A \ S und T : F¨ ur alle Werte λ > 0 werden auf Grund der Erniedrigung der -Werte der Knoten in T alle solchen Kanten aus G verschwinden. Man beachte jedoch: Nach Definition von S und T verlaufen alle Matchingkanten zwischen S und T oder zwischen A \ S und B \ T . Wir k¨onnen hierdurch also auf keinen Fall eine Matchingkante verlieren. • Kanten zwischen S und B \ T : Die wichtige Beobachtung hier ist, dass G auf Grund der Definition von S und T keine solchen Kanten enthalten kann. (Denn sonst k¨onnten wir einen an einem Knoten aus S endenden alternierenden Pfad zu einem Knoten in B \ T fortsetzen, im Widerspruch zur Definition von T .) F¨ ur Werte ugt werden. Man u λ > 0 k¨ onnten andererseits neue Kanten in G hinzugef¨ ¨berzeuge sich nun, dass im Algorithmus der Wert von λ genau so gesetzt ist, dass gilt:  bleibt zul¨ assig und es wird mindestens eine Kante von S nach B \ T zu G hinzugef¨ ugt – die in der n¨ achsten Iteration dann zu einer Vergr¨osserung der Menge T f¨ uhren wird. Die Korrektheit (und Endlichkeit) des Algorithmus haben wir somit nachgewiesen. Wie steht es aber mit der Laufzeit? Einfach herleiten k¨ onnen wir: • Es gibt genau n Iterationen der ¨ ausseren repeat-Schleife. • F¨ ur jede diese Iterationen wird die innere repeat-Schleife h¨ochstens n Mal durchlaufen, wobei in jeder dieser Iterationen maximal Laufzeit O(n2 ) zur Bestimmung der Mengen S und T ben¨otigt wird und ebenfalls h¨ ochstens O(n2 ) zur Berechnung von λ. Die Aktualisierung der -Werte der Knoten geht in Zeit O(n), w¨ ahrend f¨ ur die Aktualisierung des Graphen G wiederum O(n2 ) Schritte ben¨otigt werden. Insgesamt ergibt sich somit eine Laufzeit von O(n · n · n2 ) = O(n4 ). Diese wollen wir nun noch auf O(n3 ) reduzieren. Dazu werden wir zeigen, dass wir f¨ ur eine Iteration der ¨ausseren repeat-Schleife statt mit Laufzeit O(n · n2 ) in der Tat mit Laufzeit O(n2 ) auskommen. Betrachten wir zun¨ achst die Absch¨ atzung der Laufzeit f¨ ur die Berechnung der Mengen S und T . Wie wir oben gesehen haben, nehmen die Mengen S und T in jeder Iteration zu. Wir k¨onnen daher auf den alten ¨ Mengen aufsetzen und m¨ ussen lediglich die durch die Anderung der -Werte neu hinzugekommen Kanten von S nach B \ T weiter verfolgen. Wir ben¨otigen daher nicht in jeder Iteration Laufzeit O(n2 ), sondern nur f¨ ur alle Iterationen der inneren repeat-Schleife insgesamt Laufzeit O(n2 ). (Man kann sich das auch so vorstellen: Insgesamt f¨ uhren wir genau eine Breitensuche durch – nur eben verteilt auf verschiedene Iterationen.) Kritischer ist die Berechnung der Werte λ und die Aktualisierung der Graphen G . Hier ben¨otigen wir zur Reduzierung der Laufzeit noch eine zus¨atzliche Datenstruktur. F¨ ur Knoten b ∈ B \ T sei slack[b] := min {w(a, b) − ((a) + (b))}. a∈S

(2.2)

Zugleich halten wir uns noch eine Liste edges[b], die genau diejenigen Kanten von b in die Menge S enth¨ alt, f¨ ur die in (2.2) Gleichheit gilt. Mit Hilfe dieser Datenstruktur l¨asst sich λ dann in Zeit O(n) berechnen, denn es gilt ja (2.3) λ = min slack[b] b∈B\T

und auch G l¨ asst sich in Zeit O(n) updaten, denn wir m¨ ussen ja lediglich alle Kanten aus edges[b] f¨ ur Knoten b ∈ B \ T f¨ ur die in (2.3) das Minimum angenommen wird, zu G hinzuf¨ ugen. (Genau genommen m¨ ussten wir auch noch alle Kanten von T nach A \ S aus G entfernen. Aber da diese die weiteren Breitensuche nicht tangieren, machen wir dies gesammelt nach Beendigung der repeat-Schleife.)

KAPITEL 2. MATCHING PROBLEME

36

F¨ ur die Initialisierung der beiden Datenstrukturen slack[b] und edges[b] wird einmalig Zeit O(n2 ) ben¨otigt. Updaten m¨ ussen wir sie jeweils, wenn ein neuer Knoten zu S hinzugef¨ ugt wird. Pro Knoten ben¨otigt dies Laufzeit O(n). Da h¨ ochstens n mal ein Knoten zu S hinzugef¨ ugt werden kann, brauchen wir insgesamt auch hier Laufzeit h¨ ochstens O(n2 ). Damit haben wir also gezeigt: Pro Iteration der ¨ausseren repeat-Schleife ben¨otigen wir h¨ochstens Zeit O(n2 ). Somit gilt: Satz 2.18 (Ungarische Methode) Der Algorithmus GewichtetesBipartitesMatching berechnet bei Verwendung der Datenstrukturen slack[b] und edges[b] in Zeit O(n3 ) ein gewichtsminimales perfektes Matching.

2.3.2

Exkurs: Die primal-duale Methode der linearen Programmierung

In der linearen Programmierung betrachtet man so genannte lineare Programme. Das ist nichts anderes als eine Optimierungsaufgabe mit linearer Zielfunktion und linearen Nebenbedingungen. Also beispielsweise (P )

min cT x s.t. Ax = b x≥0

wobei c, x ∈ Rn , b ∈ Rm und A eine m × n Matrix sei. Der Buchstabe (P ) fungiert hier lediglich als Namensgebung und deutet an, dass wir dieses Programm als primales Programm bezeichnen. Das dazugeh¨orige duale Programm involviert ebenfalls die Vektoren b und c und die Matrix A: (D) s.t.

max y T b y T A ≤ cT

Vektoren x und y, die die Nebenbedinungen aus (P ) bzw. (D) erf¨ ullen nennt man primal bzw. dual zul¨ assig. Eine wichtige Eigenschaft primal/dualer Programme ist, dass der Wert des primalen Programms immer gr¨ oßer gleich dem Wert des dualen Programms ist: Lemma 2.19 Sind x und y primal bzw. dual zul¨assige Vektoren, so gilt cT x ≥ y T b. Beweis:

Aus der Tatsache, dass x und y primal bzw. dual zul¨assig sind, folgt unmittelbar (D)

(P )

cT x ≥ (y T A)x = y T (Ax) = y T b.

Beispiel 2.20 (Gewichtetes Bipartites Matching) Um das bipartite Matching Problem in einem Graphen G = (A ∪ B, A × B) mit Gewichtsfunktion w : A × B → R als lineares Programm zu formulieren, gehen wir wie folgt vor. Wir f¨ uhren f¨ ur jede Kante e ∈ A × B eine Variable xe ein, die die Werte Null oder Eins annehmen soll. Dabei sollen letztendlich die Kanten mit Wert xe = 1 genau den Kanten eines (perfekten) Matchings entsprechen. Damit letzteres der Fall ist, m¨ ussen wir f¨ ur jeden Knoten genau eine der mit dem Knoten inzidenten Kanten ausw¨ahlen. Es muss also gelten:  xe = 1 f¨ ur alle v ∈ A ∪ B. e:v∈e

Minimieren wollen wir das Gewicht des Matchings, d.h. die Funktion  w(e) · xe . e∈A×B

2.3. DAS GEWICHTETE MATCHINGPROBLEM

37

Damit erhalten wir als lineares Programm (P ) s.t.




w(e) · xe x = 1 f¨ ur alle v ∈ A ∪ B e:v∈e e xe ≥ 0 f¨ ur alle e ∈ A × B.

min


e∈A×B

Das zugeh¨orige duale Programm lautet:
(D) max v∈A∪B yv s.t. ya + yb ≤ w(e)

f¨ ur alle e = {a, b} ∈ A × B.

Man beachte die Analogie zu den im vorigen Abschnitt eingef¨ uhrten Notationen. Die Variablen yv , v ∈ A ∪ B entsprechen der Markierungsfunktion  : A ∪ B → R und die Nebenbedingung aus (D) entspricht genau der Zul¨assigkeitsbedingung (2.1). Daher ist Proposition 2.17 auch nichts anderes als Lemma 2.19 angewandt auf den Spezialfall bipartites Matching. Eine Problematik wollen wir hier noch kurz ansprechen. In der Formulierung des primalen Programms haben wir die Annahme xe ∈ {0, 1} durch die weit schw¨achere Bedingung xe ≥ 0 ersetzt, aus der zusammen mit den Bedingungen an die Summe pro Knoten sich die Bedingung 0 ≤ xe ≤ 1 ableiten l¨asst. Statt der Forderung xe ∈ {0, 1} haben wir also nur die Forderung xe ∈ [0, 1] in dem Programm unterge” bracht“. Man sagt daher auch das lineare Programm ist eine Relaxierung des eigentlich interessierenden ganzzahligen Programms. Da durch die Relaxierung das Minimum h¨ochstens kleiner wird (man minimiert ja ¨ uber einen gr¨osseren Bereich), ist ein ganzzahliges Optimum des linearen Programms immer auch ein Optimum des ganzzahligen Programms. Die Umkehrung gilt allerdings im Allgemeinen nicht. Wohl aber in diesem speziellen Fall – wie wir sp¨ater sehen werden. Eine Konsequenz von Lemma 2.19 ist, dass der optimale (=minimale) Wert des primalen Programms immer gr¨ oßer gleich dem optimalen (=maximalen) Wert des dualen Programms ist. In der Tat gilt sogar Gleichheit: Satz 2.21 Sind (P ) und (D) zueinander duale lineare Programme, so ist der Wert ihrer optimalen L¨osungen gleich, d.h. min{cT x | x primal zul¨assig} = max{y T b | y dual zul¨assig}.

Auf den Beweis dieser Tatsache m¨ ussen wir aus Platzgr¨ unden leider verzichten. Aus Satz 2.21 kann man dann zus¨ atzlich ein Kriterium ableiten, wann zwei zul¨assige L¨osungen x und y optimal sind. Satz 2.22 (Satz vom schwachen komplement¨ aren Schlupf ) Gegeben das Paar zueinander dualer linearer Programme (P )

min cT x Ax x

(D) max =b ≥0

und

yT b y T A ≤ cT .

Sei x zul¨assige L¨osung von (P ) und y zul¨assige L¨osung von (D). Dann gilt x optimal f¨ ur (P ) und y optimal f¨ ur (D)

⇐⇒

(ci − y T A.i )xi = 0 f¨ ur alle i = 1, · · · , n,

wobei A.i die i-te Spalte von A bezeichne. Beweis:

⇐“ Diese Richtung folgt wegen ” n  (ci − y T A.i )xi = cT x − y T Ax = cT x − y T b i=1

(2.4)

KAPITEL 2. MATCHING PROBLEME

38

sofort aus Lemma 2.19.
“ Da x und y jeweils zul¨ assige L¨ osungen sind und somit f¨ ur alle i = 1, · · · , n gilt ” ci − y T A.i ≥ 0

und

xi ≥ 0,

folgt diese Richtung aus der Tatsache, dass f¨ ur optimale L¨osungen cT x = y T b gilt. Das Optimalit¨ atskriterium aus Satz 2.22 kann man nun verwenden, um einen Algorithmus zur Bestimmung optimaler primaler (und dualer) L¨ osungen zu konstruieren. Dazu halten wir zun¨achst fest, dass sich die Bedingungen des komplement¨ aren Schlupfes auch wie folgt umformulieren lassen:  i) y T A.i < ci ⇒ xi = 0 x optimal f¨ ur (P ) und y optimal f¨ ur (D) ⇐⇒ ii) xi > 0 ⇒ y T A.i = ci Die Grundidee der primal-dualen Methode ist nun wie folgt. Wir starten mit einer beliebigen dual zul¨assigen L¨ osung y0 , die wir sukzessive in eine optimale L¨osung umbauen“ wollen. Dazu verwenden wir die ” obige Darstellung des komplement¨ aren Schlupfes. Wir definieren daher eine Menge S := {1 ≤ i ≤ n | y0T A.i = ci }, die der Menge der Indizes i entspricht f¨ ur die xi positiv sein darf. Mit Hilfe von S definieren wir die eingeschr¨ ankten Probleme (RP )

min

n 

zi

und

(RD)

max

uT b

i=1

Ax + z xi z

=b  ≥0 =0 ≥0

i∈S i ∈ S

uT A.i

≤0

u

≤1

i∈S

.

(RD) ist das duale Problem zu (RP ), aus dem die Variablen mit Index i ∈ S gestrichen wurden. assig f¨ ur (D), (x0 , z0 ) optimale L¨osung von (RP ), und ist z0 ≡ 0, so gilt: Es gilt nun: Ist y0 zul¨ y0 ist optimal f¨ ur (D) und x0 ist optimal f¨ ur (P ). (Dies folgt unmittelbar aus der Tatsache, dass wegen assig L¨ osung f¨ ur (P ) ist und daraus, dass die Bedingungen des komplement¨aren z0 = 0 und x0 eine zul¨ Schlupfes erf¨ ullt sind.) Damit ergibt sich das folgende Schema zur Bestimmung optimaler L¨osungen x0 und y0 : Primal-duale Methode W¨ ahle eine zul¨ assige L¨ osung y0 f¨ ur (D) beliebig. Wiederhole, bis eine der Abbruchbedingungen gegeben ist: Bestimme zugeh¨ orige eingeschr¨ ankte Probleme (RP ) und (RD) Berechne optimale L¨ osung (x0 , z0 ) von (RP ) Falls z0 = 0 −→ stop: x0 und y0 sind optimal Berechne optimale L¨ osung u0 von (RD) T Falls u0 A ≤ 0 −→ stop: (P ) ist unl¨osbar Bestimme neue dual zul¨ assige L¨osung: y0 ← y0 + λ0 u0 , cj − y0T A· j | uT0 A· j > 0}. wobei λ0 := min{ j uT0 A· j Wir wollen uns nun noch kurz u ¨ berlegen, warum die primal-duale Methode funktioniert. Dazu betrachten wir die eingeschr¨ ankten Programme (RP ) und (RD). Da die beiden Programme dual zueinander sind, haben sie nach Satz 2.21 den gleichen optimalen Wert. Der Wert von (RP ) ist entweder Null, dann ist ur (P ), oder er ist positiv. Dann ist der optimale z0 identisch Null und x0 die gesuchte optimale L¨osung f¨ Wert von (RD) ebenfalls positiv, d.h. es gilt uT0 b > 0. Dies bedeutet aber, dass f¨ ur alle y = y0 + λu0 mit λ > 0 gilt: y T b = (y0 + λu0 )T b = y0T b + λuT0 b > y0T b.

2.3. DAS GEWICHTETE MATCHINGPROBLEM

39

Wir erhalten daher f¨ ur jedes λ > 0 ein y, f¨ ur das das duale Programm (D) einen echt gr¨osseren Wert ur welche λ > 0 ist y aber auch dual zul¨assig? Zu pr¨ ufen ist, ob y T A ≤ cT , d.h. ob als f¨ ur y0 hat. F¨ T y A·,i ≤ ci f¨ ur alle i gilt. Betrachten wir diesen Ausdruck etwas genauer:  ≤ y0T A·,i f¨ ur i ∈ S, nach Def. von S und da u0 zul¨assig f¨ ur (RD) T T T y A·,i = y0 A·,i +λ·u0 A·,i T = ci − δi + λ · u0 A·,i f¨ ur i ∈ S und einem δi > 0, nach Definition von S. Es gibt daher ein λ > 0, so dass f¨ ur alle i ∈ S (und damit f¨ ur alle i) y T A·,i ≤ ci gilt. Im Algorithmus wird das gr¨ osste solche λ gew¨ ahlt, da dann f¨ ur das zugeh¨orige y der Wert des dualen Programm (D) um den gr¨ osst m¨ oglichen Betrag ansteigt. Etwas schwieriger ist es, Aussagen u ¨ber die Endlichkeit des Verfahrens zu gewinnen. Zwar wissen wir, dass sich der Wert der dualen L¨ osung y0 in jedem Schritt verbessert, doch k¨onnnen wir a priori keine Aussagen u ¨ber das Mass der Verbesserung treffen. Trotzdem kann man zeigen, dass der primal-duale Ansatz im Allgemeinen terminiert. Der Beweis dieser Aussage sprengt allerdings wieder den Rahmen unserer Ausf¨ uhrungen. Besonders interessant ist der primal-duale Ansatz, wenn sich zumindest eines der eingeschr¨ankten Probleme (RP ) und (RD) kombinatorisch interpretieren lassen. Dann k¨onnen wir unter Umst¨anden auf bekannte L¨ osungsverfahren f¨ ur dieses Problem zur¨ uckgreifen und die zugeh¨orige duale L¨osung raten“. ” Dies ist beispielsweise f¨ ur das bipartite Matchingproblem der Fall. Beispiel 2.23 (Fortsetzung von Beispiel 2.20) Das eingeschr¨ankte primale Problem (RP ) entspricht hier einem ungewichteten Matchingproblem: Die (Knoten-)Variablen zv erlauben nicht u ¨berdeckte
Knoten.
Ist ein Knoten v nicht ¨ uberdeckt so ist die
Summe e:v∈e xe gleich Null und die Gleichung e:v∈e xe + zv = 1 ist daher f¨ ur zv = 1 erf¨ ullt. Da wir v zv minimieren sollen, entspricht das Problem (RP ) daher der Bestimmung eines (kardinalit¨ats-)maximalen Matchings in dem Graphen GS , der durch die Kanten e ∈ S gegeben ist. Formal   zv und (RD) max uv (RP ) min v∈A∪B



e:v∈e

xe + zv

v∈A∪B

=1 

∀v ∈ A ∪ B

xe

≥0 =0

∀e ∈ S ∀e ∈ S

zv

≥0

∀v ∈ A ∪ B

ya + yb ≤ 0 uv ≤ 1

∀{a, b} ∈ S ∀v ∈ A∪B .

Um (RP ) optimal zu l¨osen gen¨ ugt es in dem Graphen GS ein kardinalit¨atsmaximales Matching M zu bestimmen. An Hand von M kann man dann optimale L¨osungen (x, z) und u f¨ ur (RP ) bzw. (RD) unmittelbar ablesen. Dazu setzen wir   1 e∈M 1 v nicht ¨ uberdeckt von M xe = und zv = 0 sonst 0 sonst und

⎧ ⎪ ⎨+1 uv = −1 ⎪ ⎩ 0

es gibt einen alternierenden Pfad gerader L¨ange von einem nicht ¨ uberdeckten Knoten v0 zu v es gibt einen alternierenden Pfad ungerader L¨ange von einem nicht ¨ uberdeckten Knoten v0 zu v sonst,

(Man beachte, zu einem Knoten v kann es nicht alternierenden Pfade gerader und ungerader L¨ange geben, denn dann g¨abe es auch einen augmentierenden Pfad, im Widerspruch zur angenommenen Maximalit¨at von M ). Man ¨ uberzeugt man sich leicht, dass das so definierte u eine zul¨assige L¨osung von
(RD) ist, deren Wert der Anzahl nicht ¨ uberdeckter Knoten in A ∪ B entspricht. In der Tat gilt, dass uv genau zweimal der

KAPITEL 2. MATCHING PROBLEME

40

Anzahl nicht ¨ uberdeckter Knoten in A ∪ B entspricht, da es ja f¨ ur jeden gematchten Knoten mit Wert -1 auf der anderen Seite einen “Partnerknoten“ (n¨amlich der ¨ uber die Matchingkante erreichbare Knoten) mit Wert +1 gibt. Zum anderen k¨onnen wir Aussagen ¨ uber uA·,i wie folgt herleiten. Die Spalten der Matrix A entsprechen in diesem Beispiel den Kanten e des Graphen. F¨ ur jede Kanten e = {a, b} erhalten ur alle Kanten e ∈ S kleiner gleich Null sein. Wann wir daher den Ausdruck ua + ub und dieser muss f¨ k¨onnte dies verletzt sein? Nur dann wenn ua = 1 und ub = 0 (oder analog ua = 0 und ub = 1). Dies kann aber f¨ ur Kanten e = {a, b} aus S nicht der Fall sein. (W¨are eine solche Kante in S k¨onnten wir den alternieren Pfad zu a um die Kanten e zum Knoten b verl¨angern.) Wir k¨onnen daher an Hand eines kardinalit¨atsmaximalen Matchings in dem durch die Kanten e ∈ S gegebenen Graphen eine optimale duale L¨osung f¨ ur (RD) bestimmen und somit auch die aktuelle duale L¨osung f¨ ur (D) verbessern. Genau dies haben wir in dem im vorigen Abschnitt vorgestellten Algorithmus auch getan – mit dem einzigen Unterschied, dass wir (aus Gr¨ unden der Einfachheit und Effizienz) nur alternierende Pfade mit Startknoten in der Menge A betrachtet haben. Beispiel 2.24 (K¨ urzeste Pfade) Gegeben ist ein gerichteter Graph G = (V, A, c) mit einer Kostenurzester gerichteter Pfad zwischen s funktion c : A → Z+ und zwei Knoten s, t ∈ V . Gesucht ist ein k¨ und t. Wir m¨ochten dieses Problem mit der primal-Dualen Methode l¨osen. Dazu m¨ ussen wir das Problem zun¨achst als lineares Programm schreiben. Eine naheliegende Idee ist, einen Fluss f mit Wert 1 von s = v1 nach t = v2 zu schicken, wobei die Kapazit¨at auf den Kanten nicht beschr¨ankt ist. Wir minimieren die Gesamtkosten des Flusses, d.h. cT f . Da wir keine Kapazit¨atbeschr¨ankung haben, wird der gesamte Fluss ¨ uber den billigsten Weg nach t fliessen - dieser Weg entspricht aber genau dem k¨ urzesten s-t-Pfad. Unser lineares Programm sieht nun folgendermassen aus. min cT f

⎡

⎢ ⎢ ⎢ s.t. Af = ⎢ ⎢ ⎣

+1 -1 0 .. .

⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

0 f ≥0 Dabei bezeichnet A die Inzidenzmatrix von G, d.h. ⎧ ⎪ ⎨+1 , ej verl¨asst den Knoten vi . aij = −1 , ej f¨ uhrt in den Knoten vi hinein. ⎪ ⎩ 0 , sonst Offensichtlich ben¨otigen wir die Nebenbedingung f¨ ur den Knoten t nicht, denn dieser Knoten schluckt einfach den gesamt Fluss. Wir streichen also aus A die ensprechende Zeile und erhalten min cT f

⎡

⎤

(P)

+1 ⎢ 0 ⎥ ⎢ ⎥ s.t. Af = ⎢ . ⎥ ⎣ .. ⎦ 0 f ≥0 und max ys s.t. ya − yb ≤ cab ∀(a, b) ∈ A

(D)

yt = 0. Eine zul¨assing duale L¨osung ist durch yv = 0 ∀v gegeben. Wir k¨onnen also annehmen, dass uns zu Beginn jeder Iteration der primal-dualen Methode eine dual zul¨assige L¨osung y zur Verf¨ ugung steht. Sei S = {(a, b) ∈ A : ya − yb = cab },

2.3. DAS GEWICHTETE MATCHINGPROBLEM

41

d.h. S enth¨alt alle Kanten u ¨ber welche man Fluss schicken kann ohne die Optimalit¨atsbedingungen zu verletzen. Damit erhalten wir eingeschr¨anke lineare Programme n−1 

min

zi

i=1

(RP) ⎡

⎢ ⎢ s.t. Af + z = ⎢ ⎣

+1 0 .. .

⎤ ⎥ ⎥ ⎥ ⎦

0 f ≥0 fa b = 0 ∀(a, b) ∈ S z≥0

(2.5)

und max us

(RD)

s.t. ua − ub ≤ 0 ∀(a, b) ∈ S uv ≤ 1 ∀v ∈ V. Es stellt sich nun heraus, dass (RD) sehr einfach zu l¨osen ist. Zun¨achst ist das duale Optimum entweder 0 oder 1. Das kann man wie folgt bergr¨ unden. Das primale Optimum ist 0 genau denn, wenn es einen Pfad zwischen s und t gibt, der nur Kanten aus S benutzt (Denn damit gibt es auch einen zul¨assigen s-t-Fluss). Anderenfalls kann man sich leicht u ¨ berlegen, dass  0 , falls es einen Pfad von v nach t in S gibt. ∗ uv = 1 , sonst zul¨assig f¨ ur (RD) ist. Wegen uv ≤ 1 ist u∗ offensichtlich optimal. Das bedeutet aber, dass man (RD) durch eine einfache Breitensuche bestimmen kann. Da (u∗a − u∗b ) ∈ {−1, 0, 1} erhalten wir λ = min{cab − (ya − yb ) : u∗a − u∗b > 0}. ¨ Sei nun W = {v ∈ V : u∗v = 0}. Man kann zeigen (Ubungsaufgabe!), dass f¨ ur alle v ∈ W der Wert von urzesten Pfades von v nach t entspricht. Weiterhin kann man sich leicht ¨ uberlegen, yv der L¨ange des k¨ dass f¨ ur alle v ∈ W der Wert von yv gleich ist - denn wegen der Wahl von u∗ werden in jeder Iteration alle dualen Variables zu Knoten in V \ W um den gleichen Wert erh¨oht. Das bedeutet, dass in jeder Iteration der primal-dualen Methode die Menge W um den Knoten in V \ W erweitert wird, der die geringste Distanz zu t hat. Dies ist aber genau die Idee, dessen sich der Algorithmus von Dijkstra bedient. Tatschlich gen¨ ugt es, den primal-dualen Algorithmus von einigen Ballast zu befreien um zu sehen, dass beide Algorithmen identisch sind.

2.3.3

Allgemeine Graphen

F¨ ur allgemeine Graphen G = (V, E) mit Gewichtsfunktion w : E → R gehen wir im Prinzip ganz a¨hnlich vor, wie im vorigen Abschnitt f¨ ur den bipartiten Fall ausgef¨ uhrt. D.h., wir stellen ein lineares Programm und das zugeh¨ orige duale Programm auf und verwenden die primal-duale Methode. Dadurch ergibt sich in jedem Schritt statt eines gewichteten Matchingproblems ein ungewichtetes Matchingproblem, das wir mit Hilfe des in Abschnitt 2.2.3 entwickelten Algorithmus l¨osen k¨onnen. Wir beginnen daher mit dem linearen Programm
(P ) min e∈E w(e) · xe
s.t. f¨ ur alle v ∈ V e:v∈e xe = 1 xe ≥ 0 f¨ ur alle e ∈ E.

KAPITEL 2. MATCHING PROBLEME

42 Das zugeh¨ orige duale Programm lautet:
max v∈V yv s.t. yu + yv ≤ w(e)

(D)

f¨ ur alle e = {u, v} ∈ E.

Die Problematik hier ist, dass im Fall von allgemeinen Graphen eine optimale L¨osung von (P ) nicht notwendigerweise ganzzahlig sein muss. Betrachten wir dazu das folgende Beispiel: 2

1

5 1

1 1

3

2

4

1

1 1

2

2

6

Die Zahlen an den Kanten seinen hierbei das Gewicht der Kante. Ein gewichtsminimales perfektes Matching ist beispielsweise 1

5 4

3 2

6

1

5

Betrachten wir andererseits

4

3 2

6

wobei wir allen gestrichelten Kanten den Wert 1/2 geben und den u ¨ brigen Kanten den Wert Null. Dann sieht man leicht, dass der so definierte Vektor eine zul¨assige L¨osung f¨ ur (P ) ist, dessen Wert echt kleiner als der Wert eines gewichtsminimalen perfekten Matchings ist. Wie k¨ onnen wir die Problematik fassen? Betrachten wir dazu eines der Dreiecke in der Zeichnung. Da ein Dreieck aus ungerade vielen Knoten besteht, wissen wir, dass es in jedem perfekten Matching eine Kanten geben muss, die das Dreieck nach aussen“ verbindet. Dies ist in der gefundenen nichtganzzahligen L¨osung ” nicht der Fall. F¨ ugen wir daher f¨ ur alle Knotenmengen X ⊂ V mit |X| ungerade eine Ungleichung der Form  xe ≥ 1 e:|e∩X|=1

zu (P ) hinzu, w¨ urden wir zumindest in obigem Beispiel alle nichtganzzahligen optimalen L¨osungen ausschliessen. Wie man zeigen kann, ist dies auch allgemein der Fall.

Kapitel 3

Das Rundreiseproblem Eines der bekanntesten kombinatorischen Optimierungsprobleme ist das so genannte Rundereiseproblem oder auch kurz TSP, von engl. travelling salesman problem. Rundreiseproblem (tsp)     Eingabe: Ein vollst¨ andiger Graph G = (V, V2 ) mit L¨angenfunktion  : V2 → R≥0 . Ausgabe: Ein Hamiltonkreis H mit (H) = min{(H  ) : H  Hamiltonkreis in G}. (Ein Hamiltonkreis in einem Graphen ist ein Kreis, der jedem Knoten des Graphen enth¨ alt.) V  Oftmals betrachtet man das Problem auch f¨ ur Graphen mit E = 2 . Dies ist keine echte Verallgemeinerung, da man beispielsweise jede nicht in dem Graphen vorhandene Kante zu dem Graphen hinzuf¨ ugen k¨ onnte und mit einem entsprechend hohen Gewicht versehen k¨onnte. Beispielsweise f¨ uhrt ein Gewicht ugten Kanten h¨ochstens dann nimmt, wenn von |V | · maxe∈E (e) + 1 dazu, dass man eine der neu hinzugef¨ der urspr¨ ungliche Graph keinen Hamiltonkreis enth¨alt. Formalisiert man dieses Argument, so erh¨alt man unmittelbar: Satz 3.1 Das Rundreiseproblem ist NP-schwer. Beweis: Wir reduzieren das NP-vollst¨ andige Problem Gegeben ein Graph G = (V, E), enth¨alt G einen ” Hamiltonkreis?“ auf das Rundreiseproblem. Dies erreichen wir, in dem wir einen gegebenen Graphen G = (V, E) durch einen vollst¨andigen Graphen    = (V, V ) auf der gleichen Knotenmenge ersetzen und als Gewichtsfunktion die Funktion G 2  :e→

1 e∈E 2 sonst

 ) die L¨ange einer k¨  verwenden. Bezeichnen wir nun mit tsp(G, urzesten TSP-Tour in dem Graphen G, so gilt offenbar G enth¨ alt Hamiltonkreis

⇐⇒

 ) = n(= |V |). tsp(G,

D.h., jeder Algorithmus f¨ ur das Rundreiseproblem l¨ost insbesondere auch das NP-vollst¨andige Entscheidungsproblem ob ein Graph einen Hamiltonkreis enth¨alt. Eine einfache Abwandlung dieses Beweises zeigt sogar, dass das Rundreiseproblem nicht einmal gut approximiert werden kann. Satz 3.2 F¨ ur alle c ∈ N gilt: F¨ ur das Rundreiseproblem gibt es keinen polynomiellen Approximationsalgorithmus mit G¨ ute ≤ c, ausser es gilt P = N P . 43

KAPITEL 3. DAS RUNDREISEPROBLEM

44 Beweis: funktion

Wir gehen analog vor wie im letzten Beweis, allerdings verwenden wir diesmal die L¨angen 1 e∈E :e→ 1 + cn sonst.

 Dann gilt f¨ ur jeden Hamiltonkreis H in G: Ist H ein Hamiltonkreis in G, so ist (H) = n. Ist andererseits H kein Hamiltonkreis in G, so ist (H) ≥ (n − 1) · 1 + (1 + cn) = (c + 1)n. Jeder Approximationsalgorithmus f¨ ur das Rundreiseproblem mit G¨ ute c muss daher einen Hamiltonkreis in G ausgeben, falls ein solcher existiert.

3.1

Exakte L¨ osungsverfahren

Im Hinblick auf Satz 3.1 ist es nicht weiter verwunderlich, das die besten bekannten L¨osungsverfahren f¨ ur das Rundreiseproblem exponentielle Laufzeit haben. Dennoch stellt sich die Frage wie schnell diese sind.

3.1.1

Dynamische Programmierung

Ein triviales√Durchprobieren aller m¨ oglichen Hamiltonkreise f¨ uhrt zu einem Algorithmus mit Laufzeit O(n!) = O( n(n/e)n ). Mit einer dynamischen Programmierung geht es viel schneller, allerdings erkauft man sich, wie wir gleich sehen werden, den Laufzeitvorteil mit zus¨atzlichem Speicherbedarf. Wie bei der dynamischen Programmierung u ¨ blich, besteht der Haupttrick des Algorithmus darin, sich eine geeignete, rekursiv berechenbare Funktion auszudenken. Hier w¨ahlt man: (im Folgenden gelte o.E. V = {1, . . . , n}) f (i, S) := L¨ ange eines k¨ urzesten Pfades von 1 nach i, der als innere Knoten genau die Knoten aus S enth¨alt. Offenbar gilt: 1. f (i, {j}) = (1, j) + (j, i) f¨ ur alle 1 < i = j ≤ n, 2. f (i, S) = minj∈S [f (j, S \ {j}) + (j, i)] f¨ ur alle 2 ≤ i ≤ n und S ⊆ V \ {1, i} und 3. tsp(G, ) = min1≤i≤n [f (i, V \ {1, i}) + (i, 1)]. Damit erhalten wir unmittelbar den folgenden Algorithmus f¨ ur die Berechung der minimalen L¨ange einer Rundreise: TSP (Dynamische Programmierung)   Eingabe: vollst¨ andiger Graph mit V = {1, . . . , n} und Gewichtsfunktion  : V2 → R. Ausgabe: L¨ ange eines k¨ urzesten Hamiltonkreises. for all 2 ≤ i = j ≤ n do f (i, {j}) := (1, j) + (j, i); for all 2 ≤ s ≤ n − 2 do for all S ⊂ {2, . . . , n} mit |S| = s do for all i ∈ {2, · · · , n} \ S do f (i, S) = minj∈S (f (j, S \ {j}) + (j, i)); return min1≤i≤n [f (i, V \ {1, i}) + (i, 1)].

¨ 3.1. EXAKTE LOSUNGSVERFAHREN

45

Wie bei der dynamischen Programmierung u ¨blich, kann man den Algorithmus leicht so modifizieren, dass man statt der L¨ ange einer minimalen Tour auch die Tour selbst erh¨alt. Man muss sich dazu nur jeweils merken, f¨ ur welchen Index das Minimum angenommen wird. Damit erhalten wir: Satz 3.3 Mit Hilfe dynamischen Programmierung l¨asst sich das Rundreiseproblem in Laufzeit O(n2 2n ) √ der n und Speicher O( n2 ) l¨osen. Beweis: Von der Korrektheit haben wir uns schon u ussen daher nur noch die behaup¨ berzeugt, wir m¨ teten Komplexit¨ atsschranken nachweisen. Die Laufzeit l¨ asst sich leicht durch n−2  n · n · n + n) = O(n2 2n ) O(n + s s=2
n   ur die Absch¨atzung des Speicherbedarfs stellen wir zun¨achst absch¨ atzen, da bekanntlich 2n = s=0 ns . F¨ fest, das es jeweils gen¨ ugt, die Werte f¨ ur zwei aufeinanderfolgende Werte von s vorzuhalten. Der Speicherbedarf l¨ asst sich daher durch         √ n n n n O(n · max ( + )) = O(n · max ) = O(n · ) = O( n · 2n ) 2≤s≤n−2 1≤s≤n 2 s−1 s n/2 n 2n absch¨ atzen, wobei die letzte Gleichung aus 2 = Θ( √ ) folgt, was sich wiederum leicht unter Verwendung n der Stirlingformel herleiten l¨ asst.

3.1.2

Branch and Bound

So genannte Branch and Bound“ Verfahren kommen in der Praxis bei vielen NP-schweren Optimierungs” verfahren zum Einsatz. Die grunds¨ atzliche Idee ist hier, das zu Grunde liegende Problem rekursiv ein immer einfachere Probleme zu zerlegen. Beim Rundreiseproblem w¨ahlt man sich beispielsweise beliebig (oder gem¨ ass geeigneter Heuristiken) eine Kante e und unterscheidet die beiden F¨alle: e geh¨ ort zum optimalen Hamiltonkreis und e geh¨ ort nicht zum optimalen Hamiltonkreis. Auf diese Weise erh¨ alt man aus dem Ausgangsgraphen G zwei Graphen G1 und G2 , wobei in G1 = G, die Kante e aber bereits als Kante des Hamiltonkreises feststeht, und G2 = G \ e. Mit beiden Graphen kann man nun rekursiv so weiter verfahren, d.h. eine Kante e ausw¨ahlen und die beiden F¨ alle e geh¨ ort zum optimalen Hamiltonkreis und e geh¨ort definitiv nicht zum optimalen Hamiltonkreis unterscheiden. Man u ¨ berlegt sich schnell, dass dieses Verfahren im Allgemeinen nicht sehr effizient sein wird, entspricht die Komplexit¨ at dieses Verfahrens doch der Gr¨oße des dabei entstehenden Bin¨arbaumes. Letzterer hat Tiefe |E| und enth¨ alt somit 2|E| Knoten. Die aus praktischer Sicht essentielle Idee besteht daher bei diesem Ansatz in dem zweiten Teil (→ Bound“) des Names. Hierunter versteht man Folgendes. Zu jedem Graphen bestimmt man eine m¨oglichst ” gute untere Schranke f¨ ur die beste noch erzielbare L¨osung. Ist diese Schranke schlechter als eine bereits bekannte L¨ osung, so muss dieser Ast des Baumes nicht weiter betrachtet werden. Betrachten wir diesen Ansatz f¨ ur das Rundreiseproblem. Wir ben¨otigen hierf¨ ur eine f¨ ur jeden Graphen effizient berechenbare, m¨ oglichst gute untere Schranke f¨ ur die L¨ange eines minimalen Hamitonkreises.

KAPITEL 3. DAS RUNDREISEPROBLEM

46

Gerne w¨ ahlt man hier den folgenden Ansatz: F¨ ur jeden Knoten w¨ahlen wir die beiden billigsten Kanten aus und berechnen dann die Summe der Kantenl¨angen aller ausgew¨ahlten Kanten. Klar ist: Dieser Wert ist kleiner gleich der doppelten L¨ ange eines k¨ urzesten Hamiltonkreises. (Dies sieht man wie folgt: W¨ahlt man in dem Hamiltonkreis f¨ ur jeden Knoten die beiden billigsten (=einzigen) inzidenten Kanten aus, so erh¨ alt man hier als Summe die doppelte L¨ange des Hamiltonkreises). Betrachten wir ein Beispiel: 4

1

a

5

3

1 2

b

4

c 3 d

f 2

1 1

e 2

Als untere Schranke erhalten wir hier (Knoten in alphabetischer Reihenfolge): 1 ((1 + 1) + (1 + 3) + (1 + 1) + (1 + 2) + (1 + 1) + (1 + 2)) = 8. 2 Als erste Zerlegungskante w¨ ahlen wir e = {a, b}. Wir erhalten die beiden Graphen mit den unteren Schranken

2

b

5 4

c 3 d

a

b 3

1

4

4

1

a

f

1

2

e

d 2

(2+4+2+3+2+3)/2=8

4

c 3

2

1

5

3

1

1

f 2

1 e 2

(3+7+2+3+2+3)/2=10

wobei die fett gezeichnete Kante {a, b} andeutet, dass diese Kante f¨ ur den Hamiltonkreis fest ausgew¨ ahlt wurde. Auf diese Art verfahren wir nun weiter, wobei wir folgenden Heuristiken verwenden: • Wir zerlegen jeweils denjenigen Graphen, der aktuell die kleinste untere Schranke hat. • In diesem Graphen w¨ ahlen wir als Zerlegungskante die/ein beliebige der k¨ urzesten Kanten des Graphen. • Hat ein Knoten bez¨ uglich der fest ausgew¨ahlten Kanten bereits Grad 2, so werden allen anderen zu ihm inzidenten Kanten gel¨ oscht. • Kanten, die mit bereits ausgew¨ ahlten Kanten einen (Nicht-hamitonschen) Kreis erzeugen, werden gel¨ oscht. • Entsteht durch das L¨ oschen von Kanten ein Knoten vom Grad zwei, so werden die beiden mit diesem Knoten inzidenten Kanten fest ausgew¨ahlt. Damit ergibt sich der folgende Baum:

d

a

1

1

c

1

11

1

/

e

b

3

1

1

c

1

1

e

4

b

2

2

5

f

2

d

a

5

3

f

1

c

13

1

1

3

1

1

c

1

1

c

3

1 e

4

b

e

4

b

2

2

5 f

/

e

b

2

5

f d

a

13

3

1 c

1

\

e

4

b

2

2

f

1 (2 + 5 + 4 + 4 + 2 + 4) = 10.5 2

d

a

\

1 (2+5+2+3+2+4) = 9 2

d

a

/

d

3

1

1

2

2

5

4

f

2

d

a

3

\

1

c

1 3

1 e

4

b

2

2

5

4

f

d

3 1

c

1 3

1 e

4

b

2

2

5

4

f

d

a

12

1

c

1

/

3

1 e

b

2

4

f

d

3

c

1 3

1 e

4

b

d

a

2

2

5

4

3

f

14

1

c

1

\

3

1 (3+4+4+4+3+4) = 11 2

2

a

\

1 (3 + 4 + 4 + 3 + 2 + 4) = 10 2

2

a

/

1 (3+4+4+3+2+4) = 10 2

1 (2+4+2+3+2+4) = 8.5 2

2

a

/

d

3

1

1

c

1 3

1 e

4

b

2

2

5

4

f

e

b

2

4

f d

a 1

1

c

d

3

1

1

c

3

1 e 2

4

b

2

5

4

f

/

1 e 2

4

b

2

5

4

f

2

\

d

a

3

1 (3+7+2+3+2+4) = 10.5 2

2

a

/

d

3

1

1

c

3

1 e 2

4

b

2

5

4

f

1

1

c

3

e 2

4

b

2

5

4

f

2

d

a

3 1

c

\

3

1 e

4

b

2

5

4

f

1 (6+9+4+3+2+6) = 14 2

1 (3+7+2+3+2+4) = 10.5 2

2

a

\

1 (3 + 9 + 2 + 3 + 2 + 4) = 11.5 1 (3+7+4+3+3+4) = 12 2 2

2

1 (2+4+2+3+2+4) = 8.5 2

2

a

¨ 3.1. EXAKTE LOSUNGSVERFAHREN 47

KAPITEL 3. DAS RUNDREISEPROBLEM

48

3.2

Das Rundreiseproblem mit Dreiecksungleichung

Von einem Rundreiseproblem mit Dreiecksungleichung spricht man, wenn die L¨angenfunktion  : die Dreiecksungleichung erf¨ ullt, wenn also (u, w) ≤ (u, v) + (v, w)

V  2

→R

f¨ ur alle u, v, w ∈ V.

Man u ¨ berzeugt sich leicht davon, dass die im Beweis von Satz 3.1 konstruierte L¨angenfunktion die Dreieckungleichung erf¨ ullt. Es gilt daher: Satz 3.4 Das Rundreiseproblem mit Dreiecksungleichung ist NP-schwer. Im Gegensatz zum allgemeinen Rundreiseproblem ist das Rundreiseproblem mit Dreiecksungleichung jedoch verh¨ altnism¨ aßig gut approximierbar. In der Tat erhalten wir aus der Tatsache, dass man in einem gewichteten Graphen einen minimal spannenende Baum effizient berechnen kann, leicht einen 2Approximationsalgorithmus. Wie dies geht veranschaulicht die folgende Abbildung:

Wir laufen also den Spannbaum aussen herum“ ab, wobei wir Pfadst¨ ucke, die bereits besuchte Knoten ” enthalten, abk¨ urzen. In der Abbildung sind wir beim Knoten oben links losgelaufen und haben den Baum im Gegenuhrzeigersinn umlaufen. Was k¨ onnen wir nun u ange des so gefundenen Hamiltonkreises sagen? Ohne Abk¨ urzungen ¨ber die L¨ w¨ urden wir jede Kante des Spannbaums genau zweimal durchlaufen. Auf Grund der Dreiecksungleichung ist die Abk¨ urzungskante“ h¨ ochstens so lang wie das ausgelassene Pfadst¨ uck entlang des Baumes. Der ” gefundene Hamiltonkreis hat somit eine L¨ange, die h¨ochstens doppelt so lang ist, wie die L¨ange des minimal spannenden Baumes. Da ein Hamiltonkreis, in dem man eine beliebige Kanten entfernt hat, einen Spannbaum darstellt, gilt mst(G, ) ≤ tsp(G, ) und somit alg(G, ) ≤ 2 mst(G, ) ≤ 2 tsp(G, ). Der oben beschriebene Algorithmus stellt daher, wie zuvor behauptet, in der Tat einen 2-Approximationsalgorithmus dar. Wie k¨ onnen wir diesen Algorithmus noch verbessern? Klar ist, wollen wir aus dem Baum einen Hamiltonkreis gewinnen, so m¨ ussen wir zumindest an Knoten mit ungeradem Grad, und somit insbesondere an den B¨ attern des Baumes, eine Kante doppelt durchlaufen. Erinnern wir uns nun noch daran, dass man in

3.3. DAS EUKLIDISCHE RUNDREISEPROBLEM

49

einem Graphen in dem jeder Knoten geraden Grad hat eine Eulertour, d.h. einen geschlossenen Kantenzug, der jede Kante genau einmal enth¨ alt, effizient berechnen kann, so haben wir bereits alle Ideen f¨ ur den Approximationsalgorithmus von Christofides, den besten derzeit bekannten Approximationsalgorithmus, zusammen. Approximationsalgorithmus nach Christofides   Eingabe: vollst¨ andiger Graph mit V = {1, . . . , n} und Gewichtsfunktion  : V2 → R, die die Dreiecksungleichung erf¨ ullt. Ausgabe: Hamiltonkreis H mit (H) ≤ 32 tsp(G, ). 1. Bestimme einen minimal spannenden Baum T . 2. Sei Vodd := {v ∈ V | v hat in T ungeraden Grad}. 3. Bestimme in dem durch Vodd induzierten Graphen G[Vodd ] ein minimales perfektes Matching M . 4. Bestimme in dem (Multi-)Graphen T ∪ M eine Eulertour E. 5. Wandle die Eulertour in einen Hamiltonkreis um, in dem entsprechende Abk¨ urzungen eingef¨ ugt werden.

Satz 3.5 Der Approximationsalgorithmus von Christofides berechnet in Zeit O = (n3 ) einen Hamiltonkreis, der h¨ochstens 1.5 mal so lang wie ein minimaler Hamitonkreis ist. Beweis: Betrachten wir zun¨ achst die Laufzeit. Die Berechnung eines minimal spannenden Baumes l¨ asst sich unter Verwendung von Fibonacci Heaps in O(m + n log n) realisieren. F¨ ur die Berechnung eines minimalen perfekten Matchings m¨ ussen wir O(n3 ) veranschlagen (siehe Abschnitt 2.3.3), die Berechnung einer Eulertour geht wiederum in Zeit O(m). Nun zur G¨ ute. Wir haben uns bereits u ¨ berlegt, dass mst(G, ) ≤ tsp(G, ). Was k¨ onnen wir nun u ¨ ber das Gewicht des minimalen Matchings M sagen? Dazu u ¨ berlegen wir uns zun¨ achst, dass wir aus jedem Hamiltonkreis in G einen h¨ochstens genauso langen Hamiltonkreis in G[Vodd ] erhalten k¨ onnen, in dem wir einfach jedes Pfadst¨ ucke, mit inneren Knoten aus V \ Vodd durch eine entsprechende Abk¨ urzungskante ersetzen, die wegen der Dreiecksungleichung h¨ochstens so lang wie das ersetzte Pfadst¨ uck ist. Somit gilt: tsp(G[Vodd ], ) ≤ tsp(G, ). Da in jedem Graphen die Anzahl Knoten mit ungeradem Grad gerade ist, enth¨alt der minimale Hamiltonkreis in G[Vodd ] gerade viele Kanten. Wir k¨onnen ihn daher in zwei perfekte Matchings zerlegen, von denen das k¨ urzere eine L¨ ange von h¨ ochsten 12 tsp(G[Vodd ], ) hat. Daher gilt: (M ) ≤

1 tsp(G[Vodd ], ) 2

und somit 1 3 (H) ≤ (T ∪ M ) = (T ) + (M ) ≤ mst(G, ) + tsp(G[Vodd ], ) ≤ tsp(G, ). 2 2

3.3

Das euklidische Rundreiseproblem

Einen Spezialfall des Rundreiseproblems mit Dreicksungleichung erh¨alt man, wenn die L¨angenfunktion  sich geometrisch interpretieren l¨ asst. Unter dem euklidischen Rundreiseproblem versteht man entsprechend das folgende Problem: Gegeben n Punkte x1 , . . . , xn ∈ R2 in der Ebene setzen wir (xi , xj ) := ||xi − xj ||2 , wobei ||xi − xj ||2 den (euklidischen) Abstand der beiden Punkte xi und xj bezweichne. ¨ Uberraschenderweise l¨ asst sich das euklidische Rundreiseproblem wesentlich besser l¨osen, wie 1996 Arora und Mitchell unabh¨ angig voneinander gezeigt haben. Der Beweis des folgenden Satzes sprengt allerdings den Rahmen dieser Vorlesung.

KAPITEL 3. DAS RUNDREISEPROBLEM

50

Satz 3.6 (Arora 1996, Mitchell 1996) F¨ ur das euklidische Rundreiseproblem gibt es ein polynomielles Approximationsschema. ¨ Wir schliessen dieses Kapitel mit einem kurzen Uberblick u ¨ber den Komplexit¨atsstatus des Rundreiseproblems

positiv negativ

TSP O(n2 2n ) ∈ AP X

∆-TSP G¨ ute 3/2 ∈ P AS

eukl. TSP PAS ∈ F P AS

wobei die nagativen Resultate nat¨ urlich auf der Annahme P = N P beruhen.

Kapitel 4

Planare Graphen Formal ist ein Graph durch Angabe seiner Knoten- und Kantenmengen vollst¨andig beschrieben. Eine anschaulichere Vorstellung erh¨ alt man andererseits meist erst dann, wenn man den Graphen zeichnet. Um die Zeichnung u ¨ bersichtlich zu halten, wird man dabei versuchen, die Anzahl der Schnittpunkte von Kanten m¨ oglichst gering zu halten. Besonders u ¨bersichtlich wird die Zeichnung, wenn man solche ¨ Uberkreuzungen von Kanten v¨ ollig vermeiden kann. Definition 4.1 Ein Graph heisst planar, wenn man ihn so zeichnen (man sagt auch: in die Ebene einbetten) kann, dass sich keine Kanten kreuzen. Ein ebener Graph ist ein planarer Graph zusammen mit seiner Darstellung in der Ebene. Streng mathematisch gesehen ist dies noch keine Definition. Dazu m¨ ussten wir zuvor noch pr¨azise definieren, was es heisst, einen Graphen zu zeichnen“ bzw. was Kreuzungen“ sind. Dies kann man tun, ” ” allerdings nicht ohne betr¨ achtlichen Aufwand. Wir werden uns in diesem Kapitel daher mit der Verwendung der aus der Anschauung offensichtlichen Begriffe und Tatsachen begn¨ ugen.

4.1

Eigenschaften planarer Graphen

Bevor wir uns der algorithmischen Frage zuwenden, wie man testen kann, ob ein gegebener Graph planar ist, wollen wir zun¨ achst noch einige Eigenschaften von planaren Graphen festhalten. ur Wir betrachten zun¨ achst einige Beispiele. F¨ ur den K4 findet man leicht eine planare Einbettung. F¨ den K5 andererseits werden s¨ amtliche Versuche ihn planar darzustellen sp¨atestens an der letzten Kante fehlschlagen. Er ist nicht planar. Als zweites Beispiel betrachten wir noch die so genannten vollst¨andig bipartiten Graphen Km,n , die aus zwei Mengen mit m bzw. n Knoten bestehen, wobei jeder Knoten in der ersten Menge zu jedem Knoten in der zweiten Menge benachbart ist, w¨ahrend alle Knoten innerhalb der ur K2,n , n gleichen Menge untereinander nicht benachbart sind. Wieder gilt: F¨ ur den K2,3 (und analog f¨ beliebig) findet man leicht eine planare Einbettung, f¨ ur den K3,3 ist dies andererseits bereits nicht mehr m¨ oglich. K4 K5 K2,3 K3,3

planar

nicht planar

planar

nicht planar

Ebene Darstellungen planarer Graphen sind im Allgemeinen nicht eindeutig. Allerdings gelten gewisse Invarianten. Beispielsweise wird in jeder Darstellung die Anzahl der Gebiete gleich sein. (F¨ ur die Definition eines Gebietes verwenden wir wiederum eine anschauliche Definition: die zusammenh¨angenden Teile, die man erh¨ alt, wenn man die Ebene entlang der Kanten zerschneidet.) F¨ ur den K4 erh¨alt man vier Gebiete (das ¨ aussere Gebiet z¨ ahlt man mit), unabh¨angig davon wie man ihn zeichnet. Allgemein gilt: 51

KAPITEL 4. PLANARE GRAPHEN

52

Satz 4.2 (Eulersche Polyederformel) Sei G = (V, E) ein zusammenh¨angender ebener Graph. Dann gilt #Gebiete = |E| − |V | + 2. Der Beweis folgt leicht durch Induktion u ¨ ber die Anzahl der Kanten. Aus der eulerschen Polyederformel kann man leicht eine obere Schranke f¨ ur die Anzahl Kanten eines planaren Graphen ableiten. Satz 4.3 F¨ ur jeden planaren Graphen G = (V, E) mit |V | ≥ 3 Knoten gilt |E| ≤ 3|V | − 6. Beweis: Ohne Einschr¨ ankung d¨ urfen wir annehmen, dass G zusammenh¨angend ist. Wir betrachten eine Einbettung von G. R seien die durch die Einbettung entstehenden Gebiete. Jedes Gebiet wird von mindestens 3 Kanten begrenzt und jede Kante begrenzt h¨ochstens zwei Gebiete. Daraus folgt, dass 3|R| ≤ 2|E|. Und zusammen mit der eulerschen Formel erhalten wir 2 |E| ≥ |R| = |E| − |V | + 2. 3 Daraus folgt aber, dass 1 |E| ≤ |V | − 2. 3 Multiplizieren wir nun beide Seiten mit 3, so erhalten wir das gew¨ unschte Resultat.  Aus Satz 4.3 folgt, dass der K5 nicht planar ist. Der K5 hat n¨amlich 52 = 10 Kanten aber nur 5 Knoten und 10
3 · 5 − 6. Mit einem ¨ ahnlichen Argument kann man zeigen, dass der K3,3 nicht planar ist. (Hier verwendet man, dass der K3,3 bipartit ist und in einem bipartiten planaren Graphen alle Gebiete von mindestens vier Kanten begrenzt werden m¨ ussen.) Die beiden Graphen K5 und K3,3 sind in gewisser Weise die kleinsten nicht-planaren Graphen. Nichtplanare Graphen gibt es nat¨ urlich viele. Beispielsweise ist jeder Graph, der einen K5 oder einen K3,3 als Teilgraphen enth¨ alt, ebenfalls nicht planar. Auch wenn wir ein oder mehrere Kanten des K5 oder des K3,3 durch Pfade ersetzen, ist der dadurch entstehende Graph, den man auch als Unterteilung des K5 bzw. des K3,3 bezeichnet, ebenfalls nicht planar. Der polnischen Mathematiker Kazimierz Kuratowski (1896– 1980) konnte andererseits zeigen, dass wir damit auch schon alle Arten, einen nicht-planaren Graphen zu erzeugen, beschrieben haben. Satz 4.4 (Kuratowski) Ein Graph G ist genau dann planar, wenn er weder eine Unterteilung des K5 noch des K3,3 als Teilgraphen enth¨alt. Satz 4.4 erm¨ oglicht unmittelbar einen Test auf Planarit¨at. Allerdings ist dessen Laufzeit miserabel: Da wir nicht nur auf den K5 und den K3,3 testen m¨ ussen, sondern auch auf alle beliebig grossen Unterteilungen, erhalten wir so a priori nur einen exponentiellen Algorithmus. Ein effizienteres Verfahren werden wir im n¨ achsten Abschnitt herleiten.

4.2

Planarit¨ atstest

In vielen F¨ allen ist nicht unmittelbar zu entscheiden, ob es sich bei einem gegebenen Graphen um einen planaren Graphen handelt. Ziel dieses Abschnittes ist es daher, einen effizienten Algorithmus zu beschreiben, der einen beliebigen Graphen G = (V, E) als Eingabe erh¨alt und als Ausgabe eine m¨ogliche Einbettung von G liefert, falls G planar ist, bzw. erkennt, dass G nicht planar ist. Dabei soll eine Laufzeit von O(|V |) erreicht werden. Es sei darauf hingewiesen, dass hier keine Versuche unternommen werden, eine m¨ oglichst “sch¨ one” Einbettung zu finden. Hierf¨ ur gibt es spezielle Algorithmen. Einen solchen werden wir im n¨ achsten Abschnitt vorstellen.

¨ 4.2. PLANARITATSTEST

53

Ohne Beschr¨ ankung der Allgemeinheit wird im folgenden angenommen, dass es sich bei G um einen 2-fach zusammenh¨ angenden Graphen handelt. Andernfalls kann der Graph zun¨achst an seinen Artikulationsknoten zerlegt und die Komponenten einzeln auf Planarit¨at getestet werden. Aus den Einbettungen der Komponenten kann man dann auf einfache Weise eine Einbettung f¨ ur den Gesamtgraphen erhalten. Zudem k¨ onnen wir nach Satz 4.3 annehmen, dass die Bedingung m ≤ 3n − 6 erf¨ ullt ist. Ansonsten ist der Graph ja auf keinen Fall planar.

Definition 4.5 Sei G = (V, E) ein Graph, der einen Kreis C enth¨alt (ein solcher existiert, da wir   2-fach Zusammenhang vorausgesetzt hatten). Ein Segment ist eine Komponente von V \ C, E \ C2 zusammen mit allen von dort ausgehenden Kanten. Die Verankerungen eines Segmentes sind die Knoten von C, an denen eine Kante des Segmentes endet. uberlappend, falls sie mindestens drei gemeinsame Verankerungen Zwei Segmente Si und Sj heissen ¨ haben oder es paarweise verschiedene Verankerungen a, b von Si und c, d von Sj gibt, so dass diese auf dem Kreis C in der Reihenfolge a, c, b, d vorkommen.

C

S1

Nebenstehende Skizze veranschaulicht diese Begriffe. Bei S1 bis S5 (incl. der ausgehenden Kanten) handelt es sich um Segmente bez¨ uglich C. Die markierten Punkte auf C stellen die Verankerungen der Segmente dar. u ¨ berlappend sind beispielsweise die Segmente S1 und S2 (drei gemeinsame Verankerungen), S3 und S5 sowie S4 und S5 . Intuitiv gesprochen sind zwei Segmente also genau dann u ¨berlappend, wenn man sie nicht beide auf einer Seite des Kreises (also innen oder aussen) einbetten kann, ohne dass sich Kanten kreuzen.

S2 S3

S4

S5

Lemma 4.6 Sei G ein Graph mit einem Kreis C und den Segmenten S1 , . . . , Sk . Gilt C + Si planar uberlappen sich nicht ∀ 1 ≤ i < j ≤ k, so ist G planar und es gibt eine ∀ i = 1, . . . , k und Si und Sj ¨ Einbettung, in der alle Segmente ausserhalb von C liegen (oder alle innerhalb). Beweis:

Wir f¨ uhren den Beweis per Induktion u ¨ber die Anzahl der Segmente k.

k = 0: klar. k − 1 ⇒ k: Seien 0, . . . ,  − 1 die Knoten des Kreises C (in dieser Reihenfolge). W¨ ahle zwei Knoten des Kreises i0 , i1 ∈ {0, . . . ,  − 1} mit kleinstm¨oglichem Abstand, so dass ein Segment Sj0 existiert, f¨ ur das alle Verankerungen in {i0 , . . . , i1 } liegen. [Achtung: Wir fordern nicht, dass i0 < i1 . Falls i0 > i1 , so rechnen wir modulo .] Falls es mehrere solche Sj0 gibt, w¨ahle eines mit maximal vielen Verankerungen. Unser Ziel ist es, die Induktionsannahme auf die Segmente S1 , . . . , Sj0 −1 , Sj0 +1 , · · · Sk anzuwenden und dann zu argumentieren, dass man auch das Segment Sj0 noch einbetten kann. Dazu zeigen wir zun¨achst: F¨ ur alle Segmente Sj mit j = j0 gilt: alt keine Verankerung aus {i0 + 1, . . . , i1 − 1}. Sj enth¨ Wir zeigen die Behauptung mit einem Widerspruchsbeweis. Angenommen, Sj enth¨alt doch so eine Verankerung. Dann sind drei F¨ alle zu unterscheiden: 1. Fall: Sj enth¨ alt auch eine Verankerung ausserhalb von {i0 , . . . , i1 }

KAPITEL 4. PLANARE GRAPHEN

54

i1

Sj

Sj 0

⇒ Widerspruch, da Sj0 und Sj u ¨ berlappen.

i0

2. Fall: Sj enth¨ alt keine Verankerung ausserhalb von {i0 , . . . , i1 } und i0 oder i1 ist keine Verankerung von Sj i1

Sj

Sj 0

⇒ Widerspruch zur Wahl von i0 , i1 .

i0

3. Fall: i0 und i1 sind Verankerungen von Sj . Da Sj und damit auch Sj0 (wir haben das Segment mit maximal vielen Verankerungen gew¨ahlt) eine weitere Verankerung in {i0 , . . . , i1 } hat, folgt i1

Sj

⇒ Widerspruch, da Sj0 und Sj u ¨ berlappen.

Sj 0

i0

(Fortsetzung des Induktionsbeweises:) C + (S1 + · · · + Sj0 −1 + Sj0 +1 + · · · + Sk ) sind planar nach der Induktionsannahme. Ausserdem ist C + Sj0 planar nach Voraussetzung. Da alle Verankerungen von Sj0 innerhalb des Intervalls {i0 , . . . , i1 } liegen und kein anderes Segment eine Verankerung {i0 − 1, . . . , i1 − 1} enth¨alt, kann man beide Einbettungungen problemlos zusammenf¨ ugen und erh¨ alt so eine Einbettung f¨ ur C + (S1 + · · · + Sk ). Damit ist der Induktionsschritt abgeschlossen und Lemma 4.6 gezeigt. Korollar 4.7 Sei G ein Graph mit einem Kreis C und den Segmenten S1 , . . . , Sk . Dann gilt:

G planar

⇔

(1) C + Si planar ∀ i = 1, . . . , k und (2) ∃ Partition {1, . . . , k} = I1 ∪ I2 , so dass sich keine zwei Segmente aus der gleichen Menge uberlappen. ¨

Beweis:

Zu zeigen sind wieder beide Richtungen:

“⇒”: Klar: w¨ ahle f¨ ur I1 die Menge der innen liegenden Segmente und f¨ ur I2 die aussen liegenden Segmente. “⇐”: Wende Lemma 4.6 zweimal an: erst auf die Segmente in I1 (bette diese aussen ein), dann auf die Segmente in I2 (bette diese innen ein).

¨ 4.2. PLANARITATSTEST

55

Damit folgt die Aussage. Aufbauend auf Korollar 4.7 kann man (mit einigem Aufwand) den Satz von Kuratowski (→ Satz 4.4) beweisen. Wir u ¨ berlassen dies dem Leser. Lemma 4.8 Sei C ein Kreis, S ein Segment und P ein Pfad auf C, der alle Verankerungen von S enth¨alt. Dann gilt:

⇔

C + S planar

(1) P + S planar und (2) es gibt eine Einbettung von P + S, in der P zum Rand des ¨ausseren Gebietes geh¨ort.

Beweis:

Die Richtigkeit dieser Aussage ist nach folgender Skizze unmittelbar einsichtig: C

P

S

Lemma 4.8 liefert also eine M¨ oglichkeit, den auf Planarit¨at zu testenden Graphen zu verkleinern, wovon im folgenden Gebrauch gemacht werden wird.

Idee f¨ ur einen Planarit¨ atstest Die bisherigen u uhren zu einer ersten Idee, wie sich ein Planarit¨atstest f¨ ur einen Graphen ¨berlegungen f¨ G realisieren l¨ asst: • W¨ ahle Kreis C beliebig, bestimme die Segmente Si und entsprechende Pfade Pi . • Verifiziere rekursiv, dass Si + Pi (hat weniger Kanten als G!) planar ist und es eine Einbettung gibt, in der Pi aussen liegt. ¨ • Bestimme den Uberlappungsgraphen U G der Segmente Si : Knoten von U G Kanten von U G:

= ˆ

Segmente Si Si und Sj werden genau dann durch eine Kante verbunden, wenn Si und Sj u ¨ berlappen.

• Verifiziere, ob U G bipartit ist. Ist dies der Fall, so ergeben sich aus den beiden bipartiten Knotenmengen von U G die Segmente, die innen bzw. aussen eingebettet werden m¨ ussen, und G ist damit planar (vgl. Abbildung 4.1). Ungl¨ ucklicherweise ist die erzielbare Laufzeit bei diesem Vorgehen zwar polynomiell aber noch nicht, ¨ wie erw¨ unscht, linear. Schon alleine der Uberlappungstest zur Erzeugung von U G hat, so der Kreis θ(n) Segmente induziert, eine Laufzeit von θ(n2 ).

KAPITEL 4. PLANARE GRAPHEN

56

innere Segmente

¨aussere Segmente

UG ¨ Abbildung 4.1: Bipartiter Uberlappungsgraph

Folgende Verbesserungen sind daher angebracht: (1) geschicktere Durchf¨ uhrung der Rekursion und ¨ (2) Uberlappungsgraph nicht explizit konstruieren! Kernidee zur Umsetzung dieser Forderungen ist es, daf¨ ur zu sorgen, dass die Segmente in einer bestimmten (geschickten!) Reihenfolge erzeugt werden. Die im Anschluss aufgef¨ uhrten Punkte sollen diesen Ansatz zun¨ achst zusammenh¨ angend skizzieren, wobei einige erg¨anzende Laufzeitbetrachtungen eingeflochten sind. Abschliessend werden die einzelnen Phasen des geschilderten Planarit¨atstests dann konkret an einem Beispielgraphen demonstriert werden.

Verbesserte Vorgehensweise • Bestimme einen DFS-Baum f¨ ur G und berechne dabei auch die Felder dfs[v] = low[v] = low2[v] =

dfs-Nummer, wie bisher min {dfs[v], dfs[w] | w durch ≥ 0 Baumkanten abw¨arts und genau eine R¨ uckw¨artskante von v aus erreichbar} min {dfs[v], dfs[w] | dfs[w] = low[v], w durch ≥ 0 Baumkanten abw¨ arts und genau eine R¨ uckw¨artskante von v aus erreichbar} [D.h., low2[v] gibt den zweitkleinsten dfs-Wert an, der durch ≥ 0 Baumkanten abw¨arts und genau eine R¨ uckw¨artskante von v aus erreichbar ist bzw. den dfs-Wert von v, falls ein entsprechender Knoten nicht existiert.]

⇒ Laufzeit O(n) [Erzielbar mit einer geeignet modifizierten Tiefensuche. Diese hat wegen m ≤ 3n − 6 und somit O(m) = O(n) in planaren Graphen Laufzeit O(n).] • Richte Kanten:

– Baumkanten abw¨arts – R¨ uckw¨ artskanten aufw¨arts

• Gewichte die Kanten folgendermassen: ⎧ falls (v, w) R¨ uckw¨artskante ⎨ 2 · dfs[w] 2 · low[w] falls (v, w) Baumkante und low2[w] ≥ dfs[v] c(v, w) = ⎩ 2 · low[w] + 1 falls (v, w) Baumkante und low2[w] < dfs[v] • Erzeuge f¨ ur alle v ∈ V eine Adjazenzliste der ausgehenden Kanten, aufsteigend sortiert nach deren Gewicht c(.).

¨ 4.2. PLANARITATSTEST

57

⇒ Laufzeit O(n) [Werfe zun¨ achst alle Kanten gem¨ass ihres Gewichtes in einen Bucket der Gr¨osse 2n (→ O(n)), hole sie dann gem¨ ass absteigendem Gewicht heraus und verteile sie auf die (anfangs leeren) Adjazenzlisten (→ O(n)).] • Markiere jede Kante als “neu” (d.h. unbetrachtet). • Bestimme einen Kreis C: v := Wurzel des DFS-Baumes; w := erster Nachbar von v in der Adjazenzliste von v; markiere (v, w) als “benutzt”; C := {(v, w)}; while (w = Wurzel des DFS-Baumes) { v := w; w := Endknoten der ersten noch unbenutzten Kante in Adjazenzliste von v; markiere (v, w) als “benutzt”; C := C + (v, w); } Gib Kreis C aus; ⇒ C besteht aus Baumkanten und genau einer R¨ uckw¨artskante (Beweis u ¨A). • Als n¨achstes werden die Segmente mit folgendem Algorithmus in “kleinen Teilen”, genauer als Folge von Pfadst¨ ucken, ausgegeben. Die zu Grunde liegende Idee ist hier, dass sich hinter diesem Ansatz die oben erw¨ ahnte Rekursion versteckt: Das erste ausgegebene Pfadst¨ uck des Segments l¨auft von einem Knoten v des Kreises C in das Segment, durchl¨auft dort eine Folge von Baumkanten und endet mit einer R¨ uckw¨ artskante wiederum am Kreis C. Zusammen mit einem entsprechenden Pfadst¨ uck des Kreises C erhalten wir auf diese Weise einen neuen Kreis – und testen rekursive, ob sich alle seine Segmente planar einbetten lassen. v := Knoten mit gr¨ osster dfs-Nummer in C; // dies ist Knoten v am Ende des vorigen Algorithmus while (v = Wurzel des DFS-Baumes) { while (es gibt “neue” Kanten in Adjazenzliste von v) { w := Endknoten der ersten noch unbenutzten Kante in Adjazenzliste von v; markiere (v, w) als “benutzt”; P := {(v, w)}; while (dfs[v] < dfs[w]) { // (v, w) ist eine Baumkante v := w; w := Endknoten der ersten noch unbenutzten Kante in Adjazenzliste von v; markiere (v, w) als “benutzt”; P := P + (v, w); } Gib Pfad P aus; } v := Vorg¨ anger von v; }

KAPITEL 4. PLANARE GRAPHEN

58

Bemerkung 4.9 Sei S ein Segment bez¨ uglich C und v die Verankerung von S mit gr¨osster DFS-Nummer (vgl. Abbildung 4.2). Dann treffen folgende Beobachtungen zu: • S wird u ¨ ber eine Baumkante (v, w) von v aus betreten und vollst¨andig ausgegeben, bevor der Algorithmus S wieder verl¨ asst. uckw¨artskanten. • S besteht aus dem Subbaum Tw des DFS-Baumes und allen von dort ausgehenden R¨ • Sei u der Endknoten des ersten ausgegebenen Pfades. Dann enth¨alt S nur Verankerungen aus Puv , wobei Puv der Pfad des DFS-Baumes (bzw. des Kreises C) ist, der u und v verbindet.

u C

v

w

Tw

Abbildung 4.2: Skizze zu Bemerkung 4.9

Lemma 4.10 Seien S1 , . . . , S die ersten  Segmente, die vom Algorithmus ausgegeben werden und P = (v, . . . , u) der erste Pfad von S , der ausgegeben wird. Weiter sei eine Einbettung von C + S1 + · · · + S−1 gegeben. Dann gilt: S l¨asst sich genau dann nicht aussen (innen) hinzuf¨ ugen, wenn es ein aussen (innen) eingebettetes Segment Si mit i ∈ {1, . . . ,  − 1} gibt, das eine Verankerung zwischen u und v besitzt. Beweis: Aufgrund der Arbeitsweise des Algorithmus zur Ausgabe der Pfade und den Beobachtungen aus Bemerkung 4.9, k¨ onnen die Baumkanten der bereits vollst¨andig ausgegebenen Segmente S1 , . . . , S−1 nur von den Knoten ausgehen, die in nachstehender Skizze gekennzeichnet sind: u

v

}

C

Baumkanten der Segmente S1 , . . . , S−1 k¨onnen nur hier beginnen

Sl Angenommen, es gibt ein Segment Si mit i ∈ {1, . . . ,  − 1}, das eine Verankerung innerhalb des Pfades Puv des DFS-Baumes (bzw. des Kreises C) besitzt. Dann sind folgende F¨alle zu unterscheiden:

1. Fall: Die Baumkante, u ¨ ber die Si betreten wird, beginnt unterhalb von Knoten v

¨ 4.2. PLANARITATSTEST

59

u

v

⇒ S und Si u ¨ berlappen.

S


Si

2. Fall: Die Baumkanten, u ¨ ber die S und Si betreten werden, beginnen im gleichen Knoten v und der erste Pfad von Si , der ausgegeben wurde, endet oberhalb von Knoten u

u

v

S


⇒ S und Si u ¨ berlappen.

Si

3. Fall: Die Baumkanten, u ¨ ber die S und Si betreten werden, beginnen im gleichen Knoten v und der erste Pfad von Si , der ausgegeben wurde, endet ebenfalls in Knoten u (beachte, dass der Pfad nicht unterhalb von u enden kann, ansonsten w¨are S vor Si ausgegeben worden).

atzliche R¨ uckw¨artskante haben, die zwischen u und v endet, sonst Damit muss auch S eine zus¨ w¨ are S vor Si ausgegeben worden (aus diesem Grund brauchten wir das Feld low2[.] !), also folgt

KAPITEL 4. PLANARE GRAPHEN

60

u

v

S


⇒ S und Si u ¨ berlappen.

Si

Damit ist ein eindeutiges Kriterium gezeigt, das angibt, wann sich eine gegebene Einbettung um ein Segment erweitern l¨ asst, ohne die Planarit¨at zu verletzen.

Verbesserte Vorgehensweise (Fortsetzung)

• Der Algorithmus “erkennt”, wenn der erste Pfad eines Segmentes ausgegeben wird. Daraufhin schickt er den derzeitigen Stand (die derzeitige Einbettung) auf einen Stack und macht rekursiv mit dem gerade ausgegebenen Pfad zusammen mit einem Teil des alten Kreises als neuem Kreis weiter. Es werden folgende Datenstrukturen verwendet:

Li Lo

: Liste der Pfade, die innen eingebettet werden : Liste der Pfade, die aussen eingebettet werden

Diese Listen sind aufgeteilt in Bl¨ ocke, f¨ ur die die Einbettung eines Pfades bereits die Einbettung aller u ur jeweils eine ganze Gruppe von ¨ brigen vorschreibt. Durch diese Form der Organisation kann f¨ Pfaden das ¨ andern des Ortes der Einbettung von innen nach aussen und umgekehrt (“flippen”) durch Pointer-Manipulationen in konstanter Zeit bewerkstelligt werden. Auf die genaue Ausf¨ uhrung der zugeh¨ origen Details wollen wir an dieser verzichten. Der interessierte Leser kann sie beispielsweise in Mehlhorn, Data structures and algorithms 2: Graph algorithms and NP-Completeness, Springer Verlag, 1984, nachlesen. Zusammenen mit den bereits angef¨ uhrten Laufzeitbetrachtungen ergibt sich dann:

¨ 4.2. PLANARITATSTEST

61

a

a

b

b

c

c

d

d

e

e

f

f

g

g

Abbildung 4.3: a) Beispielgraph

b) berechneter DFS-Baum

Satz 4.11 Der Planarit¨atstest l¨asst sich mit Laufzeit O(n) implementieren. Damit ist das eingangs formulierte Ziel, einen Planarit¨atstest mit linearem Laufzeitverhalten anzugeben, erreicht. Der verbleibende Teil dieses Abschnitts ist einem ausf¨ uhrlichen Beispiel gewidmet. Dazu soll der 2-fach zusammenh¨ angende Graph aus Abbildung 4.3a auf Planarit¨at getestet und gegebenenfalls eine m¨ ogliche Einbettung gefunden werden. Zun¨ achst werden mit Hilfe einer modifizierten Tiefensuche die Felder dfs[.], low[.] und low2[.] f¨ ur den gegebenen Graphen bestimmt. Nehmen wir f¨ ur unser Beispiel an, dass a b c d e f g • −→ • −→ • −→ • −→ • −→ • −→ • als DFS-Baum ermittelt wurde (vgl. Abbildung 4.3b), dann ergeben sich f¨ ur oben genannte Felder die Werte aus der folgenden Tabelle, wie man leicht u uft: ¨berpr¨ Knoten a b c d e f g

dfs[.] 1 2 3 4 5 6 7

low[.] 1 1 1 1 2 3 4

low2[.] 1 2 2 2 3 4 5

Entsprechend dem Resultat der Tiefensuche werden nun die Baumkanten abw¨arts, die R¨ uckw¨artskanten aufw¨ arts gerichtet, sowie die Kantengewichte bestimmt. Man erh¨alt dann den in Abbildung 4.4 wiedergegebenen Graphen. N¨ achster Schritt ist die Bestimmung eines Kreises C. Aufgrund der aufsteigend sortierten Adjazenzlisten ergibt sich dieser zu a b c a • −→ • −→ • −→ • . Die drei beteiligten Kanten gelten jetzt als benutzt. Offenbar existiert bez¨ uglich dieses Kreises lediglich ein einziges Segment S, das u ¨ber die Baumkante (c, d) betreten wird, wie Abbildung 4.4 (rechts) zeigt. Da alle Verankerungen des Segmentes auf dem Pfad P = (a, b, c) liegen, ist nach Lemma 4.8 der gesamte Graph also bereits dann planar, wenn P + S planar ist und es eine Einbettung gibt, in der P zum Rand des ¨ ausseren Gebiets geh¨ ort.

KAPITEL 4. PLANARE GRAPHEN

62 a 2 b

Kreis C 2

c

6 6 8

7 f

(c,d)

4

5 e

Baumkante

4

3 d

Nur ein Segment:

2

2

8 10

9 g

Abbildung 4.4: gewichteter und gerichteter Graph (links) und initiales Segment (rechts)

In der vorliegenden algorithmischen Umsetzung erfolgt die Ermittlung von S durch die Ausgabe von Pfaden. Der Algorithmus startet hierzu in Knoten c und w¨ahlt zun¨achst die Kante (c, d), weil dies die einzige unbenutzte adjazente Kante zu c ist. Da es sich um eine Baumkante handelt, werden nun die von d ausgehenden Kanten betrachtet und die R¨ uckw¨artskante (d, a) benutzt, denn diese weist das geringste Gewicht auf. Damit ist mit c d a • −→ • −→ • der erste Pfad von Segment S bestimmt.

Aus diesem Pfad und einem Teil des Kreises C erh¨alt man nun f¨ ur die Rekursion a b c d a • −→ • −→ • −→ • −→ • als neuen Kreis C  . Also lautet die Aufgabe im Rekursionsschritt wie folgt:

a b c 1. Rekursion: Finde planare Einbettung von Abbildung 4.5 (links), so dass • −→ • −→ • zum Rand des ¨ ausseren Gebietes geh¨ ort.

Der gegen¨ uber der Ausgangssituation verkleinerte Graph besitzt zwei Segmente bez¨ uglich des Kreises C  . Zum einen ist dies die R¨ uckw¨ artskante (d, b), zum anderen der Teilbaum, der u ¨ ber die Baumkante (d, e) betreten wird, zusammen mit allen davon ausgehenden R¨ uckwartskanten, siehe Abbildung 4.5 (rechts).

¨ 4.2. PLANARITATSTEST

63

a b

1. Segment: Rückwärtskante (d,b)

c 2. Segment: d

Baumkante

(d,e)

e

f

g

Abbildung 4.5: Problemgraph f¨ ur die 1. Rekursion (links) und aktuelle Segmente (rechts)

In analoger Weise ergeben sich die Teilprobleme f¨ ur die restlichen Rekursionsschritte:

b c d 2. Rekursion: Finde planare Einbettung von Abbildung 4.6 (links), so dass • −→ • −→ • zum Rand des ¨ ausseren Gebietes geh¨ ort.

c d e 3. Rekursion: Finde planare Einbettung von Abbildung 4.7 (links), so dass • −→ • −→ • zum Rand des ¨ ausseren Gebietes geh¨ ort.

d e f 4. Rekursion: Finde planare Einbettung von Abbildung 4.8, so dass • −→ • −→ • zum Rand des a ort. ¨usseren Gebietes geh¨

Wie in Abbildung 4.8 zu sehen ist, ist hier der Punkt erreicht, an dem kein weiterer rekursiver Aufruf mehr erforderlich ist, da der soweit reduzierte Graph bereits der gew¨ unschten Einbettung entspricht. Daher wird nun der Rekursionsstack abgearbeitet. Sozusagen “r¨ uckw¨arts” werden jetzt die jeweils vor dem Rekursionsschritt beiseite gelassenen Pfade zu der Einbettung hinzugef¨ ugt. In unserem Fall verl¨auft dies erfolgreich, wie in Abbildung 4.9 dargestellt. Damit ist gezeigt, dass f¨ ur den Beispielgraphen eine planare Einbettung existiert.

KAPITEL 4. PLANARE GRAPHEN

64

b

c

1. Segment: Rückwärtskante (e,c)

d 2. Segment:

e

Baumkante

(e,f)

f

g

Abbildung 4.6: Problemgraph f¨ ur die 2. Rekursion (links) und aktuelle Segmente (rechts)

c

d 1. Segment: Rückwärtskante (f,d)

e

f

2. Segment: Baumkante

g

Abbildung 4.7: Problemgraph f¨ ur die 3. Rekursion (links) und aktuelle Segmente (rechts)

d e

f

g

Abbildung 4.8: Problemgraph f¨ ur die 4. Rekursion

(f,g)

¨ 4.2. PLANARITATSTEST

65

d c e b

d

f g

c

e

f

d g

a

e

b

f g

c

d

e f g

Abbildung 4.9: Abschliessende Erzeugung der Einbettung

c

f a

b

d

g e

Abbildung 4.10: Alternative Einbettung f¨ ur den Beispielgraphen

KAPITEL 4. PLANARE GRAPHEN

66

Es bietet sich hier an, nochmals die Bemerkung vom Beginn dieses Abschnitts aufzugreifen. Dort wurde gesagt, dass wir uns damit begn¨ ugen wollen, eine m¨ogliche Einbettung zu finden, nicht jedoch eine besonders “sch¨ one”. Entsprechend kann man auch f¨ ur den vorgestellten Beispielgraphen Einbettungen finden, die weitaus schlichter ausfallen, wie Abbildung 4.10 zeigt.

4.3

Zeichnen von planaren Graphen

Bei den Anwendungen planarer Graphen in der Informatik (z.B. der Visualisierung von Strukturen oder Objekten) steht der algorithmische Aspekt im Vordergrund. In jedem einschl¨agigen Lehrbuch findet man Verfahren, die in Zeit O(|V | + |E|) testen, ob ein Graph G = (V, E) planar ist, und falls ja, diesen auch in die Ebene einbetten. Will man andererseits zus¨atzlich ¨asthetische Aspekte ber¨ ucksichtigen, st¨osst man auf ein Forschungsgebiet, in dem noch zahlreiche Probleme ungel¨ost sind. Ein Grund hierf¨ ur ist, dass es schon schwierig ist, u ¨ berhaupt zu beschreiben, was man gerne h¨atte. Zum Beispiel sind die folgenden vier Abbildungen alles planare Einbettungen des W¨ urfels Q3 .

Welches hiervon die richtige, sch¨ onste oder anschaulichste ist, h¨angt vom Kontext und nicht zuletzt auch vom Geschmack des Betrachters ab. Ein naheliegendes solches Kriterium ist der Wunsch, den Graphen so zu zeichnen, dass alle Kanten geradlinig sind. Hierf¨ ur wollen wir nun noch einen Algorithmus angeben. Eine F` ary-Einbettung eines planaren Graphen G ist ein Einbettung von G in die Ebene, so daß alle Kanten Geraden sind. Ferner wird nat¨ urlich verlangt, daß sich diese Kanten nicht kreuzen. Im folgenden werden wir uns u ¨ berlegen ob jeder planare Graph eine solche Einbettung hat, und wie man sie berechnen kann. Wir nehmen an, daß wir bereits u ugen. Ohne ¨ ber eine, im Prinzip beliebige Einbettung von G verf¨ Einschr¨ ankung erweiteren wir diese zu einer Triangulierung, d.h. jedes innere Gebiet ist ein Dreieck. Wenn es gelingt, eine F` ary-Einbettung f¨ ur Triangulierungen zu finden, sofindet man auch eine F` ary-Einbettung f¨ ur beliebige planare Graphen. Es gen¨ ugt n¨amlich, die gegebene Einbettung um einige Kanten zu einer Triangulierung zu erweitern, dann eine F` ary-Einbettung zu konstruieren und schließlich die k¨ unstlichen Kanten wieder zu entfernen. Eine Indizierung v1 , ..., vn der Knotenmenge heißt kanonische Ordnung, falls 1. Sei Gk−1 ⊆ G der, von {v1 , ..., vk−1 } induzierte Subgraph. Die Begrenzung des ¨außere Gebiet ∂(Gk−1 ) ist ein Kreis, der die Kante {v1 , v2 } enth¨alt. außeren Gebiete von Gk−1 . Ferner ist vk zu mindestens zwei aufeinander2. Der Knoten vk liegt im ¨ folgenden Knoten auf ∂(Gk−1 ) \ {v1 , v2 } verbunden. Man kann beobachten, daß durch die kanonische Ordnung im Prinzip eine Reihenfolge vorgegeben ist, in der man die Knoten iterativ hinzuf¨ ugen kann. Intuitiv betrachtet kann man auf diese Weise schon ’fast’ eine sch¨ one Einbettung finden. Im n¨achsten Abschnitt werden wir zeigen, daß dies - mit einigen zustzlichen Verschiebungen - tatschlich m¨ oglich ist. Lemma 4.12 Sei G = (V, E) ein eingebetteter Graph. Eine kanonische Ordnung von V kann man in Zeit O(n2 ) berechnen. Beweis: Zun¨ achst w¨ ahle man sich mit {v1 , v2 } eine beliebe Kante der Begrenzung des ¨außeren Gebietes der Einbettung von G. Sei Gn = G. Dann w¨ahlt man iterativ einen beliebigen Knoten vk ∈ ∂(Gk ) aus, f¨ ur den keine seiner adjazenten Kanten ein Sehne von ∂(Gk ) ist. Dann setzt man Gk−1 = V \ {vk , ..., vn }. Es bleibt zu zeigen, daß es einen solchen Knoten gibt. Sei {u1 , ..., um } = ∂(Gk ) und sei {ui , uj }, j > i + 1 eine Sehne mit j − i minimal. Dann ist ui+1 nicht adjazent zu ui , ui+1 , ..., uj adjazent, denn sonst g¨ abe es eine k¨ urzere Sehne. Andererseits kann ui+1 wegen Planarit¨at nicht adjazent zu den anderen Knoten auf dem Kreis sein.

4.3. ZEICHNEN VON PLANAREN GRAPHEN

67

Der Algorithmus [Fraysseix, Pach und Pollack 1990] konstruiert, gegeben eine kanonische Ordnung ary-Einbettung auf ein 2n − 4 mal n − 2 Gitter iterativ. Nehmen wir an, v1 , .., vn der Knoten, die F` wir haben ein eine F` ary-Einbettung des Graphen Gk = G[{v1 , ..., vk }] konstruiert. Seien v1 = w1 , w2 , . . . , wm = v2 die Knoten der Begrenzung des a ur alle k ≥ 3 folgende Invarianten ¨ußeren Gebietes von Gk . Dann sollen f¨ gelten: 1. pos(v1 ) = (0, 0) und pos(v2 ) = (2k − 4, 0). 2. x(w1 ) < x(w2 ) < . . . < x(wm ). 3. Eine Kante {wi , wi+1 } hat Steigung +1 oder −1. vk

vk

wl

wr

wl

wr

Abbildung 4.11: Einf¨ ugen von vk . Sei wl (wr ) der linkeste (rechteste) Nachbar von vk auf ∂(Gk−1 ). Will man die verlangten Invarianten nicht verletzen, so gibt es einen naheliegenden f¨ ur die Position von vk : Der Schnittpunkt der Graden mit Steigung 1 durch wl mit der Geraden mit Steigung −1 durch wr . Leider kann es vorkommen, daß eine oder beide Geraden nicht nur durch wl bzw. wr gehen, sondern auch noch andere Knoten auf ∂(Gk−1 ). Um dies zu vermeiden gen¨ ugt es, alle Punkte rechts von wl um 1 und alle Punkte rechts von wr und ufen, daß zum wr selbst um 2 nach rechts zu verschieben (Abbildung 4.11). Man kann nun leicht u ¨ berpr¨ einen keine der Invarianten verletzt ist und zum anderen die Einbettung noch eine F` ary-Einbettung ist. Wir erhalten also den folgenden einfachen Algorithmus: `ry-Einbettung Algorithm 4.13 Fa pos(v1 ) := (0, 0), pos(v2 ) := (2, 0) and pos(v3 ) := (1, 1). M (v1 ) = {v1 , v2 , v3 }, M (v2 ) = {v2 , v3 } and (v3 ) = {v3 }. ∂(G3 ) ← {v1 , v3 , v2 } =: {w1 , w2 , w3 }. for k = 4 to n do ∂(Gk ) = {v1 = w1 , . . . , wm = v2 }. Sei wl (wr ) der linkeste (rechteste) Nachbar von vk . Schiebe alle Knoten in M (wl+1 ) um 1 nach rechts. Schiebe alle Knoten in M (wr ) um 1 nach rechts. pos(vk ) ist der Schnittpunkt der Geraden durch wl mit Steigung +1 und der Geraden durch wr mit Steigung −1. ∂(Gk ) = {v 1 = w1 , . . . , wl , vk , wr , . . . , wm = v2 }. M (wi ) ∪ {vi } , i ≤ l . M (wi ) ← ,i ≥ r M (wi ) M (vk ) = M (wl+1 ) ∪ {vk }. end for Die Laufzeit ist offensichtlich O(n2 ), da man in jeder Iteration jede Kante h¨ochstens einmal betrachten muß.

KAPITEL 4. PLANARE GRAPHEN

68

Die Laufzeit des Algorithmus l¨ aßt sich auf O(n log n) verbessern. Zum einen kann man mit einem geeigneten Markierungsverfahren (siehe Orginalliteratur) eine kanonische Ordnung in Zeit O(n) finden. Zum anderen ist es nicht unbedingt n¨ otig die x-Koordinaten nach jeder Iteration anzupassen. Statt dessen speichern wir die Position implizit in einem Vektor πk , welchen wir in jeder Iteration in Zeit O(1) updaten. Angenommen, wir haben bereits πk−1 berechnet und seien i1 , ..., im die Indizes der Nachbar von vk . Dann f¨ ugen wir k links von i2 und n + k links von im in πk−1 ein und erhalten so πk . Die Funktion σ(j, k) = |{i : j < i, i steht vor j in πk } z¨ ahlt die Anzahl von Knoten, die (zeitlich) nach und (¨ortlich) vor vj eingef¨ ugt wurden. Das bedeutet, daß der Knoten vj genau σ(j, n) mal nach rechts geschoben wird. Sei x0 (vj ) die x-Koordinate, an der vj eingef¨ ugt wurde und sei xk (vj ), die (virtuelle) Position von vj nachdem vk eingef¨ ugt wurde. Dann gilt: xk (vj ) = x0 (vj ) + σ(j, k), x0 (vj ) und y(vj ) sind Funktionen von xj (vl ) und xj (vr ), wobei vl und vr den linkesten bzw. rechtesten Nachbar von vj bezeichnen. Es bleibt zu zeigen, daß man σ(j, k) in Zeit O(log n) berechnen kann. Dies erreicht man, indem man ein ¨ aquivalentes geometrisches Z¨ahlproblem formuliert. Dazu sei durch S = {(j, i) : an Stelle i in πn steht j oder n + j} eine Punktmenge gegeben. Um σ(j, k) zu berechnen, gen¨ ugt es die Punkte aus S zu z¨ahlen, welche im Rechteck R(j, k) = {(x, y) : j + 1 ≤ x ≤ k, 1 ≤ y ≤ πn−1 (j)} liegen, wobei πn−1 (j) die Position von j in πn ist. Dies ist mit geeigneten Algorithmen und Datenstrukturen in Zeit O(log n) m¨ oglich.

Kapitel 5

Separatoren Mit so genannten Divide-and-Conquer-Methoden lassen sich etliche Optimierungsprobleme einfach l¨osen. Ein essentielles Hilfsmittel hierf¨ ur ist ein Verfahren, das eine gegebene Instanz eines Problems in zwei mehr oder weniger unabh¨ angige Teile zerlegt. Dabei ist zu beachten, dass es f¨ ur die meisten Algorithmen, die nach dem Divide-and-Conquer Prinzip arbeiten, vorteilhaft ist, wenn die Aufteilung m¨oglichst gleichm¨ assig ist. Ein bekanntes Beispiel ist der Sortieralgorithmus Quicksort. Hier l¨asst sich die Laufzeit von O(n log n) nur erreichen, wenn die zu sortierende Sequenz in zwei etwa gleich grosse Teile aufgeteilt wird. F¨ ur Graphenprobleme stellen Separatoren einen geeigneten Teilungsbegriff dar. Allgemein ist ein Separator in einem Graphen eine Teilmenge der Knotenmenge des Graphen, nach deren Entfernung aus dem Graphen dieser in mehrere Komponenten zerf¨allt. Wir interessieren uns hier vor allem f¨ ur eine Zerlegung in zwei etwa gleich grosse Komponenten: C * C "klein" * A, B beide "gross" * keine Kanten zwischen A und B A

B

Definition 5.1 Sei 0 < α < 1 und f (n) eine Funktion und G = (V, E) ein Graph auf n Knoten. Eine Menge C ⊆ V heisst (f (n), α)-Separator, falls • |C| ≤ f (|V |) • G[V \C] in Komponenten zerf¨allt, die alle Gr¨osse ≤ α|V | haben. Im Allgemeinen haben Graphen keine kleinen Separatoren. Um dies einzusehen betrachte man beispielsweise den Kn . Aus diesem Grund beschr¨anken wir uns hier auf die Bestimmung von Separatoren in “d¨ unnen” Graphen. Genauer betrachten wir zun¨achst B¨aume und danach planare Graphen. Satz 5.2 Jeder Baum T besitzt einen (1, 12 )-Separator. Beweis: Wir w¨ ahlen v0 so, dass die gr¨ osste Komponente in T − v0 minimal ist. Wir wollen nun zeigen, dass v0 der gesuchte Separator ist. Dazu nehmen wir das Gegenteil an, n¨amlich, dass es eine Komponente X in T − v0 mit |X| > 12 n gibt. Wir betrachten dann den (eindeutig bestimmten) Nachbarn v1 von v0 in X. F¨ ur die gr¨ osste Komponente in T − v1 gilt offenbar, dass sie ≤ max{|X| − 1, n − |X|} < |X| ist. Daraus folgt sofort der Widerspruch. 69

KAPITEL 5. SEPARATOREN

70

X v0

v1

Abbildung 5.1: Skizze zum Beweis von Satz 5.2 Anhand des Beweises l¨ asst sich auch einfach ein Algorithmus mit linearer Laufzeit zum Bestimmen eines ¨ Aus die folgende (1, 12 )-Separator angeben. Wir u ¨ berlassen die Details dem Leser als Ubungsaufgabe. gewichtete Version von Satz 5.2 l¨ asst sich nach dem gleichen Prinzip beweisen: Satz 5.3 Sei T = (V, ET ) ein Baum und w : V → R≥0 eine Gewichtsfunktion. Dann kann man in linearer Zeit einen Knoten v0 ∈ V finden, so dass f¨ ur alle Komponenten T  von T \ v0 gilt: 

w(v) ≤

v∈T 

5.1

1 w(v). 2 v∈T

Separatoren in planaren Graphen

Wir wollen uns jetzt mit Separatoren in planaren Graphen besch¨aftigen. Wir wissen bereits, dass ein planarer Graph G einen Knoten mit Grad h¨ochstens 5 besitzt. Also enth¨alt jeder planare Graph auf mindestens 5 Knoten eine trennende Menge der Gr¨osse h¨ochstens 5. Wir wollen aber den Graphen in etwa gleich grosse Komponenten zerlegen. Dadurch wird die Aufgabe erheblich erschwert. Im Folgenden wollen wir folgenden Satz beweisen: √ Satz 5.4 Jeder planare Graph auf n Knoten besitzt einen ( 8n, 23 )-Separator und ein solcher l¨asst sich in Zeit O(n) bestimmen.

Zum Beweis des Satzes sind noch einige Vor¨ uberlegungen n¨otig. Zun¨achst ben¨otigen wir noch eine Definition.

Definition 5.5 Der Durchmesser eines Graphen G = (V, E) ist der l¨angste k¨ urzeste Abstand zwischen zwei Knoten, oder formal diam(G) = maxu,v∈V (dist(u, v)), wobei dist(x, y) die L¨ange eines k¨ urzesten Pfades zwischen x und y angibt.

Desweiteren spielt folgendes Lemma eine zentrale Rolle beim Beweis obigen Satzes.

5.1. SEPARATOREN IN PLANAREN GRAPHEN

71

C(e)

e

Abbildung 5.2: Skizze zum Beweis von Lemma 5.6 Lemma 5.6 Sei G = (V, E) ein planarer Graph und T = (V, ET ) ein spannender Baum in G mit Durchmesser s. Dann besitzt G einen (s + 1, 23 )-Separator und ein solcher l¨asst sich in O(n) bestimmen. Beweis: Sei G in die Ebene eingebettet und o. E. trianguliert, das heisst, jedes Gebiet wird von genau drei Kanten berandet. Dazu f¨ ugen wir einfach solange Kanten ein, bis der Graph trianguliert ist. Dies geht ¨ in Zeit O(n) (Ubungsaufgabe!). Offensichtlich ist ein Separator des neuen Graphen auch einer des alten. alt dann genau einen Kreis C(e) mit h¨ochstens s + 1 Kanten und Sei e ∈ E\ET eine Kante. ET ∪ e enth¨ ebenso vielen Knoten. Mit int(C(e)) und ext(C(e)) bezeichnen wir die Anzahl der Knoten im Inneren ¨ bzw. im Ausseren von C(e). Wir suchen nun eine Kante e, so dass sowohl int(C(e)) als auch ext(C(e)) ≤ 23 n Dazu beschreiben wir ein Verfahren, das ausgehend von einer Kante e ∈ E\ET mit int(C(e)) > 23 n eine Kante e konstruiert, so dass • Das Innere von C(e ) echt im Inneren von C(e) enthalten ist. • ext(C(e )) ≤ 23 n. Anzumerken bleibt noch, dass gelten kann int(C(e )) = int(C(e)). Dann enth¨alt das Innere von C(e ) aber zumindest eine Fl¨ ache weniger als C(e). Da int(C(e)) nur O(n) viele Fl¨ achen (Euler’sche Formel) enth¨alt, terminiert dieser Algorithmus nach linear vielen Schritten und liefert C(e) als gesuchten Separator. Nun m¨ ussen wir uns noch der Bestimmung von e widmen. Sei e = {x, y} und z der dritte Knoten des Gebiets im Inneren, das e enth¨alt. Da int(C(e)) > 0 k¨onnen nicht sowohl {x, z} als auch {y, z} Kanten aus C sein. Bei Verwendung einer geeigneten Datenstruktur kann man z in O(1) bestimmen. Dazu speichert man zu jedem Knoten die inzidenten Kanten in einer zyklischen Liste in der Reihenfolge, wie sie in der Einbettung im Gegenuhrzeigersinn auftreten. z

x

y

x

e’ y

y

x

x

y

e’ z

z

z Skizze zu Fall 1

Skizze zu Fall 2a

Skizzen zu Fall 2b

Abbildung 5.3: Skizzen zu den folgenden F¨allen Ausgehend von obiger Abbildung unterscheiden wir die folgenden F¨alle:

KAPITEL 5. SEPARATOREN

72 Fall1.

Genau eine der Kanten {x, z} oder {y, z} ist in C(e) enthalten. Sei {x, z} diese Kante. Wenn wir nun ahlen, so umfasst der neue Kreis genau eine Fl¨ache weniger. (Man beachte, dass {y, z} keine e := {y, z} w¨ Baumkante sein kann!) Fall2. Weder {x, z} noch {y, z} ist in C(e) enthalten. Daraus ergeben sich mehrere M¨oglichkeiten. Wir betrachten zun¨ achst den Fall, dass {x, z} in ET oder {y, z} in ET enthalten ist. Dann folgt, dass z im Inneren von C(e) liegt, wobei o. E. {x, z} in ET liegt. Also k¨onnen wir wieder e = {y, z} w¨ahlen. Nun betrachten wir den Fall, dass sowohl {x, z} als auch {y, z} nicht in ET enthalten sind. Wir nehmen nun an, dass int(C({x, z})) ≥ int(C({y, z})), dann gilt: 2 n 3

< = ≤

int(C(e))

    int(C({x, z})) + int(C({y, z})) + C({x, z}) ∩ C({y, z}) − 1     2int(C({x, z})) + C({x, z})

und somit   1   ext(C({x, z})) = n − int(C({x, z})) − C({x, z}) ≤ n − n − 

 3 ≥

 2 1   C({x, z}) ≤ n. 2 3

1 2 2 [ 3 n−|C({x,z})|]

Somit ergibt sich, dass e = {x, z} die gew¨ unschten Eigenschaften hat. Jetzt m¨ ussen wir uns noch um den Aufwand k¨ ummern, den wir betreiben m¨ ussen, um zu zeigen, dass int(C({x, z})) ≥ int(C({y, z})) oder umgekehrt. Wir wollen dies in O(1) bestimmen. Dies gelingt uns aber i.a. nicht, denn f¨ ur eine spezielle Kante e kann der Aufwand sehr hoch sein. Im Folgenden sehen wir aber, dass wir durch einen geschickte amortisierte Laufzeitanalyse trotzdem die gew¨ unschte Schranke einhalten k¨ onnen. F¨ ur die Bestimmung von z ben¨ otigen wir f¨ ur alle F¨alle 2b zusammen nur O(n), da jede Baumkante h¨ ochstens einmal durchlaufen wird. Damit k¨ onnen wir uns jetzt der Bestimmung von e zuwenden. Hierbei gen¨ ugt es entweder int(C) oder ext(C) zu bestimmen (vgl. Fall 2b). Des weiteren l¨asst sich int(C(·)) berechnen, indem man die Baumkanten im Inneren z¨ ahlt. Also verfolgen wir die Baumkanten abwechselnd im Inneren von int(C({x, z})) und int(C({y, z})), solange bis wir ein Gebiet vollst¨andig durchlaufen haben. Wichtig f¨ ur die Laufzeit ist, dass die in diesem Gebiet liegenden Baumkanten sp¨ater nie mehr behandelt werden. Wie wir leicht sehen k¨ onnen ist der Aufwand f¨ ur das andere Gebiet h¨ochstens genauso gross. Also ergibt sich auch hier ein Aufwand f¨ ur alle F¨alle von Fall 2b zusammen von O(n).

Nach diesen Vor¨ uberlegungen k¨ onnen wir zum Beweis von Satz 5.4 zur¨ uckkehren. Beweis: Ohne Beschr¨ ankung der Allgemeinheit sei G zusammenh¨angend. W¨ahle v0 ∈ V beliebig als Wurzel und teile die Knoten von G in Mengen Li = {v ∈ V |dist(v0 , v) = i}. Weiter sei l = max{i|Li = 0} der maximale Abstand eines Knotens aus G zu v0 . √ Falls nun 2l + 1 ≤ 8n, dann garantiert Lemma 3.15 den gesuchten Separator.   Anderenfalls setzen wir s =  n2  und Sj := {Li |i ≡ j mod s}. Wir w¨ahlen nun einen Index j0 so, dass Sj0 die kleinste Menge Sj ist. F¨ ur diese gilt dann sicherlich |Sj0 | ≤  ns . Wenn wir nun die Komponenten onnen wir zwei F¨ alle unterscheiden. von G\Sj0 betrachten, k¨ 1.Fall: Falls alle Komponenten ≤ 23 n sind, dann sind wir wegen  ns  ≤ 2.Fall:

√ √ 2 n fertig.

5.1. SEPARATOREN IN PLANAREN GRAPHEN

73

vo

L1 L2

Li Abbildung 5.4: Skizze zum Beweis Es gibt eine (und nur eine!) Komponente > 23 n. Wir kontrahieren die Knoten von Sj0 in dem Level oberhalb dieser Komponente. Dadurch entsteht ein BFS-Baum mit Tiefe ≤ s − 1 und Durchmesser ≤ 2(s − 1). Aus dem vorherigen Lemma folgt daher, dass diese Komponente einen Separator der Gr¨ osse ≤ 2s − 1 hat. √ Damit hat G einen Separator der Gr¨ osse ≤  ns  + 2s − 1 ≤ 8n. Um die letzte Ungleichung einzusehen,  schreibe man s als s = n/2 + δ f¨ ur ein 0 ≤ δ < 1 und u ¨berzeuge sich davon, dass  √ n n + 2( n/2 + δ) − 1 ≤ 8n + 2s − 1 =  s n/2 + δ f¨ ur alle 0 ≤ δ < 1. Da wir die Mengen Li aus dem in linearer Zeit berechenbaren BFS-Baum ablesen k¨onnen und zur Berechnung des Separators gem¨ ass Lemmas 5.6 ebenfalls nur Aufwand O(n) ben¨otigen, l¨asst sich insgesamt der gesuchte Separator ebenfalls in linearer Zeit bestimmen. √ Bemerkung 5.7 Man kann sogar zeigen, dass es in jedem planaren Graph einen ( 8n, 23 )-Separator gibt, f¨ ur den die Knoten des Separators in G einen Kreis bilden. Abschliessend wollen wir noch folgende Versch¨arfung von Satz 5.4 zeigen: Satz 5.8 Sei G = (V, E) ein planarer Graphauf n Knoten und = (n) eine beliebige Funktion, so dass 1

≤ 1 und n ≥ 24. Dann enth¨alt G einen ( 24n  , )-Separator und ein solcher kann in Zeit O(n log  ) bestimmt werden.  Beweis: Wir setzen s =  n 6  und wenden folgendes Verfahren an, das eine wiederholte Anwendung des vorigen Algorithmus darstellt. 1.Schritt Wir verwenden wie im Beweis von Satz 5.4 eine Breitensuche um von einem beliebigen Knoten v0 ∈ V aus eine Menge Sj0 zu bestimmen, so dass |Sj0 | ≤  ns  und alle Komponenten von G[V \Sj0 ] in planare Graphen mit Durchmesser ≤ 2s − 2 eingebettet werden k¨onnen. Dann setzten wir C := Sj0 . 2.Schritt Solange es Komponenten H in G[V \C] der Gr¨osse ≥ n gibt, bestimmen wir mit Hilfe von Lemma 5.6 wie im Beweis von Satz 5.4 eine Menge C  der Gr¨osse ≤ 2s − 1, so dass H nach Entfernen von C  in Komponenten der Gr¨ osse ≤ 23 |V (H)| zerf¨allt. Dann setzen wir C := C ∪ C  Nun bleibt noch zu zeigen, dass C h¨ ochstens die angegebene Gr¨osse hat und dass die geforderte Laufzeit eingehalten wird. Dazu partitionieren wir alle Komponenten, die im Laufe des Algorithmus auftreten wie folgt. N0 := Menge aller Komponenten ≤ n

KAPITEL 5. SEPARATOREN

74 Ni := Menge aller Komponenten >

 3 i−1 2

n und ≤

 3 i 2

n f¨ ur 1 ≤ i ≤ log 32 1 .

Falls im Laufe des Algorithmus eine Komponente H aus Ni in kleinere zerf¨allt, so haben diese h¨ochstens 2 oren daher nicht zu Ni . Also sind die Komponenten in Ni paarweise knotendis3 |V (H)| Knoten und geh¨ junkt, woraus folgt, dass die gesamte Laufzeit, die wir ben¨otigen um Komponenten in Ni zu separieren linear in n ist. Daher betr¨ agt die Gesamtlaufzeit O(n · log 1 ). Nun m¨ ussen wir noch die Gr¨ osse von C absch¨atzen. Da die Komponenten in Ni knotendisjunkt sind, gilt  i−1 3 |Ni |

n ≤ n 2 Also gibt es h¨ ochstens 

log 3

1


2  n! |C| ≤ + s i=1

 2 i−1 3

1 

Komponenten in Ni . Also ist

"  i−1 ! ∞  i−1  n 1 n 3 2 2 1 24n (2s − 1) ≤ + (2s − 1) , = + (2s − 1) ≤ 3

s

3 s



i=1

wobei man die G¨ ultigkeit der letzten Ungleichung ¨ahnlich wie im Beweis von Satz 5.4 nachrechnet (hier ben¨ otigt man die Voraussetzung n ≥ 24).

5.2

Anwendungen des Separatorensatzes

Separatoren finden vor allem bei der Entwicklung von Divide-and-Conquer Verfahren ihre Anwendung. Gem¨ ass Definition zerlegt ein Separator den Graphen in zwei Teile die beide um mindestens einen Faktor, beispeilsweise 2/3, kleiner sind. Wendet man den Separatorsatz daher rekursiv auf die jeweils neu entstehenden Komponenten an, so terminiert dieses Verfahren nach sp¨atestens O(log n) Runden. Problematischer ist im Allgemeinen der Conquer“ Schritt, bei dem die L¨osungen der einzelnen Teile wieder ” zusammen gesetzt werden m¨ ussen. ur die im √ Dieser ist meist exponentiell in der Gr¨osse des Separators. F¨ vorigen Abschnitt vorgestellten n-Separatoren wird man daher auf diese Weise meist keine polynomiellen Algorithmen erhalten. Andererseits erh¨alt man damit quasi per Konstruktion sofort subexponentielle Algorithmen, was f¨ ur NP-vollst¨ andige Probleme durchaus nicht offensichtlich ist. In diesem Abschnitt wollen wir die obigen Bemerkungen an einem Beispiel genauer ausf¨ uhren. (Planar) Independent Set Problem Gegeben: Ein (planarer) Graph G = (A  B, E). Gesucht: Eine kardinalit¨ atsmaximale unabh¨angige Menge in G, d.h., eine m¨oglichst grosse Menge X ⊆ V , so dass der von X induzierte Subgraph G[X] keine Kante enth¨alt. F¨ ur dieses Problem ist bekannt, dass es NP-schwer ist.

Satz 5.9 Sowohl Independet Set als auch Planar Independet Set sind NP-schwer.

Es gilt aber: Satz 5.10 In planaren Graphen kann man in Laufzeit 2O( stimmen.

√ n)

einen maximale unabh¨angige Menge be-

F¨ ur den Beweis dieses Satzes betrachten wir den folgenden Algorithmus, der die zu Beginn dieses Abschnittes skizzierten Ideen formalisiert:

5.2. ANWENDUNGEN DES SEPARATORENSATZES

75

Algorithmus PlanarIndSet(G) Eingabe: planarer Graph G = (V, E) Ausgabe: eine maximale unabh¨ angige Menge I if |V (G)| ≤ 1 then I := V (G) else I := ∅;  Berechne einen ( 8|V (G)|, 23 )-Separator C von G, so dass G[V \ C] in nichtadjazente Mengen A und B der Gr¨ osse h¨ ochstens 23 |V (G)| zerf¨allt. for all S ⊆ C, S unabh¨ angig do IA := PlanarIndSet(G[A \ Γ(S)]); IB := PlanarIndSet(G[B \ Γ(S)]); if |S| + |IA | + |IB | > |I| then I := S ∪ IA ∪ IB ; PlanarIndSet := I; ¨ Beweis: Die Korrektheit von Algorithmus PlanarIndSet(G) folgt sofort aus folgender Uberlegung. Wir betrachten eine (beliebige) maximale unabh¨angige Menge X0 und einen Separator C, der den Graphen in zwei Komponenten A und B zerlegt. Dann ist A ∩ X0 eine maximale unabh¨angige Menge in A \ Γ(C ∩ X0 ), denn jede gr¨ ossere unabh¨ angige Menge in A \ Γ(C ∩ X0 ) w¨ urde zusammen mit (C ∪ B) ∩ X0 eine gr¨ ossere (als X0 ) unabh¨ angige Menge f¨ ur G ergeben, im Widerspruch zur Wahl von X0 . Da der Algorithmus alle Teilmengen von C betrachtet, betrachtet er insbesondere auch die Menge C ∩ X0 und die Korrektheit des Algorithmus f¨ ur G folgt daher aus der Korrektheit des Algorithmus f¨ ur G[A \ Γ(C ∩ X0 )] und G[A \ Γ(C ∩ X) ]. Da die beiden letzteren Graphen weniger Knoten als G haben folgt die Korrektheit von PlanarIndSet(G) somit durch Induktion u ¨ber |V (G)|. Betrachten wir nun die Laufzeit von PlanarIndSet(G). Dazu bezeichnen wir mit t(n) die Worst-CaseLaufzeit f¨ ur einen Graphen auf n Knoten, wobei wir ohne Einschr¨ankung annehmen, dass t(n) monoton steigend ist. Nach Konstruktion des Algorithmus gilt offenbar: t(n) ≤ O(n) + 2

√ 8n

2 · O(n) · 2t( n). 3 √

(Der erste O(n)-Term entspricht der Zeit f¨ ur die Bestimmung des Separators, der Faktor 2 8n beschr¨ankt die Anzahl der Teilmengen von C, der zweite O(n)-Term sch¨atzt die Zeit f¨ ur die Berechnung der beiden Graphen G[A \ Γ(S)] und G[B \ Γ(S)] ab.) Sch¨ atzt man die O(·)-Terme durch geeignete Konstanten c1 und c2 ab, so erh¨alt man t(n) ≤ c1 n + 2c2 n · 2

√ 8n

2 · t( n). 3

W¨ ahlt man n0 und c3 ≥ 1 gross genug, so dass (c1 + 2c2 )n ≤ 2(4−

√ √ 8) n

f¨ ur alle n ≥ n0

und t(n) ≤ c3

f¨ ur alle n < n0 ,

¨ so kann per Induktion u dass ¨ ber n leicht nachrechnen (Ubungsaufgabe!), t(n) ≤ c3 2 1−

4 √

2/3

√ n

.

76

KAPITEL 5. SEPARATOREN

Kapitel 6

Beschr¨ ankte Baumweite Welche Eigenschaften charakterisieren einen Baum. Nun zun¨achst einmal seine Kreisfreiheit. Hier wollen wir jedoch drei andere Eigenschaften in den Vordergrund stellen:

(1) In jedem Baum gibt es einen (1, 12 )-Separator (vgl. Lemma 5.2). (2) F¨ ur viele Optimierungsprobleme kann man auf B¨aumen einen dynamischen Programmierungsansatz w¨ ahlen und erh¨ alt einen Algorithmus mit linearer Laufzeit. (3) Es gibt eine Reihenfolge v1 , . . . , vn der Knoten des Baumes, so dass f¨ ur alle 2 ≤ i ≤ n gilt: In dem von den Knoten v1 , . . . , vi induzierten Graphen G[{v1 , . . . , vi }] hat der Knoten vi Grad genau 1.

Betrachten wir diese Eigenschaften etwas genauer: Eigenschaft (3) ist eine unmittelbare Folgerung aus der Tatsache, dass jeder Baum ein Blatt enth¨ alt, dessen Entfernung wiederum zu einem Baum f¨ uhrt. Eigenschaften (1) und (2) zeigen, dass Optimierungsprobleme auf B¨aumen vielfach effizient l¨osbar sind, wobei die Eigenschaft (1) eine top-down Strategie anwendet, w¨ahrend der Eigenschaft (2) eine bottom-up Strategie zu Grunde liegt. Wir illustrieren dies f¨ ur das Problem eine maximale unabh¨angige Menge zu finden. Eigenschaft (1) erlaubt einen rekursiven Ansatz: Algorithmus TreeIndSet(T ) Eingabe: Baum T = (V, E) Ausgabe: eine (kardinalit¨ ats-)maximale unabh¨angige Menge I if |V (T )| ≤ 1 then I := V (T ) else 1 Berechne einen (1, 2 )-Separator x von T . Seien T1 , . . . , T die Teilb¨aume in T \ x. Iin := {x} ∪ 1≤i≤ TreeIndSet(Ti \ Γ(x));  Iout := 1≤i≤ TreeIndSet(Ti ); if |Iin | ≥ |Iout | then return (Iin ) else return (Iout ). 77

¨ KAPITEL 6. BESCHRANKTE BAUMWEITE

78

Die Korrektheit ist offensichtlich, als Laufzeit erh¨alt man O(n2 ). Um letzteres einzusehen stelle man sich den Berechnungsbaum vor. Jeder Knoten des Graphen kommt in h¨ochstens einem der Teilb¨aume ur jeden der B¨ aume Ti werden zwei rekursive Aufrufe gestartet: TreeIndSet(Ti ) T1 , . . . , T vor. F¨ und TreeIndSet(Ti \ Γ(x)). Auf der ersten Rekursionsebene kommt daher jeder Knoten des Graphen h¨ ochstens zweimal vor, auf der zwieten Rekursionsebene h¨ochstens viermal und analog auf der k-ten ur die Bestimmung der Separatoren ben¨otigt man daher in der kRekursionsebene h¨ ochstens 2k mal. F¨ ten Ebene Laufzeit c2k n, wobei c eine geeignet gew¨ahlte Konstante ist. Da sich die Gr¨osse des gr¨ossten Baumes in jeder Ebene halbiert, gibt es insgesamt h¨ochstens log2 n viele Ebenen. Die Laufzeit l¨asst sich daher wie folgt absch¨ atzen: 

log2 n k=1



log2 n

c2 n = O(n · k

) = O(n2 ).

k=1

Den dynamische Programmierungsansatz aus Eigenschaft (2) kann man f¨ ur dieses Problem wie folgt umsetzen:

Wir w¨ ahlen einen beliebigen Knoten r ∈ V (T ) als Wurzel des Baumes. Dies definiert f¨ ur jeden Knoten x ∈ V (T ) einen eindeutigen Unterbaum Tx , der alle Knoten unterhalb von x in dem im Knoten r aufgeh¨ angten“ Baum enth¨ alt. Weiter bezeichne Γsuc (x) die Menge der Nachfolger von x im gewurzelten ” Baum T . Wir definieren nun zwei Funktionen win , wout : V → N0 wie folgt: := max{|S| | S ⊆ V (Tx ), S unabh¨angig, x ∈ S}, := max{|S| | S ⊆ V (Tx ), S unabh¨angig, x ∈ S}.

win (x) wout (x)

Offensichtlich ist max{win (r), wout } die Kardinalit¨at einer maximalen unabh¨angigen Menge in T .1

Die Werte w(x) kann man andererseits leicht bottom-up m¨assig berechnen, denn es gilt:  win (x)

= 

wout (x)

=

1, falls x ein Blatt ist
1 + y∈Γsuc (x) wout (y), sonst 0,


falls x ein Blatt ist y∈Γsuc (x) max{wi n(y), wout (y)}, sonst.

Ziel dieses Kapitels ist es, ein Konzept einzuf¨ uhren, das den Begriff eines Baumes verallgemeinert. Genauer, werden wir zu jedem k ∈ N eine Klasse von Graphen definieren, die sozusagen k-nahe an B¨aumen sind.

1 Wie bei der dynamischen Programmierung ublich, ist es (notatiell) einfacher, nur die Kardinalit¨ at einer optimalen ¨ L¨ osung zu berechnen. F¨ ur die Berechnung der optimalen L¨ osung muss man sich zus¨ atzlich zu den Werten win (x) und wout (x) merken, f¨ ur welches S jeweils das Maximum angenommen wurde.

6.1. BAUMZERLEGUNG UND BAUMWEITE

79

Die entsprechenden Definitionen, man spricht hier von der so genannten Baumweite eines Graphen f¨ uhren wir in Abschnitt 6.1 ein. In Abschnitt 6.2 zeigen wir, dass f¨ ur jedes konstante k ∈ N die Klasse der Graphen mit Baumweite ≤ k ganz ¨ ahnliche Eigenschaften haben wie B¨aume. Genauer zeigen wir, dass f¨ ur diese Klassen ganz ¨ ahnliche Eigenschaften wie die oben beschriebenen Eigenschaften (1) und (2) gelten. In Abschnitt 6.3 zeigen wir dann, dass wir auch eine Verallgemeinerung der Eigenschaft (3) h¨atten verwenden k¨ onnen, um genau die gleichen Klassen der k-baumnahen“ Graphen zu definieren. ”

6.1

Baumzerlegung und Baumweite

Definition 6.1 Ein Tupel (T, W) heisst Baumzerlegung eines Graphen G = (V, E), falls gilt: • T ist ein Baum, • W = (Wx )x∈V (T ) mit Wx ⊆ V ,  • x∈V (T ) Wx = V , • f¨ ur alle e = {u, v} ∈ E gibt es ein x ∈ V (T ) mit u, v ∈ Wx , • f¨ ur alle v ∈ V gilt: T [{x ∈ V (T ) | v ∈ Wx }] ist zusammenh¨angend. Anschaulich kann man sich die f¨ unf Bedingungen aus der Definition einer Baumzerlegung wie folgt klar machen: • T ist ein Baum, daher der Name Baumzerlegung, • jedem Knoten x des Baumes ist eine Teilmenge Wx der Knotenmenge V des Graphen G zugeordnet, • jeder Knoten des Graphen G ist in mindestens einer Knotenmenge des Baumes enthalten [Knoten¨ uberdeckungsbedingung], • f¨ ur jede Kante des Graphen G gibt es (mindestens) einen Knoten x des Baumes, dessen Knotenmenge Wx beide Endknoten der Kante enth¨alt [Kanten¨ uberdeckungsbedingung], • f¨ ur jeden Knoten v des Graphen induzieren die Knoten des Baumes, deren Knotenmenge den Knoten v enth¨alt, einen zusammenh¨ angenden Teilbaum [Zusammenhangsbedingung].

a

a

c

c b

b d

e

b b

d

e

d

e

d

e

f f

Abbildung 6.1: Beispiel einer Baumzerlegung Abbildung 6.1 zeigt ein Beispiel einer Baumzerlegung (rechts) eines Graphen G (links).

¨ KAPITEL 6. BESCHRANKTE BAUMWEITE

80

Man u ¨ berlegt sich leicht, dass es zu jeden Graphen G = (V, E) eine Baumzerlegung gibt. Man k¨onnte beispielsweise einfach einen Baum auf nur einem Knoten t w¨ahlen und diesem als Knotenmenge Wt die gesamte Knotenmenge V zuweisen. Dann sind alle Bedingungen von Definition 6.1 erf¨ ullt – aber eigentlich hat man nichts wirklich spannendes oder aussagekr¨aftiges konstruiert. Man ist daher an Baumzerlegungen oglichst klein sind. Entsprechend definiert man: interessiert, bei denen die Mengen Wx m¨ Definition 6.2 Die Baumweite einer Baumzerlegung (T, W) entspricht der Kardinalit¨at der gr¨ossten Knotenmenge minus Eins. Formal: tw(T, W) := max (|Wx | − 1). x∈V (T )

Die Baumweite eines Graphen G = (W, E) entspricht der kleinsten Baumweite einer Baumzerlegung des Graphen G. Formal: tw(G) := min tw(T, W). (T,W) Baumzerlegung von G Wieso die minus Eins in der Definition der Baumweite? Ganz einfach, man m¨ochte, dass (normale) B¨aume Baumweite 1 haben. Und da es f¨ ur jede Kante des Graphen eine Knotenmenge des Baumes geben muss, die beide Endknoten enth¨ alt, muss es in jeder Baumzerlegung eines nichtleeren Graphen Knotenmengen der Kardinalit¨ at ≥ 2 geben. In der Tat kann man f¨ ur B¨aume aber immer eine Baumzerlegung finden, in der jede Knotenmenge Wx genau zwei Knoten enth¨alt. Abbildung 6.2 zeigt an einem Beispiel wie das geht: Man w¨ ahlt f¨ ur jede Kante des Baumes G = (V, E) einen Knoten der Baumzerlegung, der genau die beiden Knoten der Kante enth¨ alt. B¨ aume haben also Baumweite 1. Wir schliessen diesen Abschnitt mit der Beobachtung, dass man f¨ ur einen Graphen mit Baumweite k immer eine Baumzerlegung finden kann, die nicht zu viele Knoten enth¨alt. Zun¨achst u ¨ berlegen wir uns hierf¨ ur, dass wir ohne Einschr¨ ankung davon ausgehen k¨onnen, dass eine Baumzerlegung nur Kanten {x, y} enth¨ alt mit Wx ⊆ Wy , denn ansonsten k¨onnte man diese Kante durch einen einzigen Knoten ersetzen (die beiden Knoten also zu einem Knoten kontrahieren), ohne die Eigenschaften der Baumzerlegung zu zerst¨ oren. Lemma 6.3 Ist G ein Graph und (T, W) eine Baumzerlegung mit Baumweite k mit Wx ⊆ Wy f¨ ur alle Kanten {x, y} des Baumes, so gilt |V (T )| ≤ |V (G)|. Beweis: Wir w¨ ahlen einen beliebigen Knoten r ∈ V (T ) als Wurzel und ordnen jedem Knoten x ∈ V (T ) \ r einen Knoten v ∈ V (G) wie folgt zu: v ∈ Wx \ Wparent(x) , wobei parent(x) den (eindeutig bestimmten) Vorg¨ anger von x in dem an r gewurzelten ( aufgeh¨angten“) Baum T bezeichne. Den Knoten ” v gibt es, wegen der Annahme Wx ⊆ Wy f¨ ur alle Kanten {x, y} in E(T ). Aus der Zusammenhangsbedingung folgt weiter, dass alle gew¨ ahlten Knoten paarweise verschieden sein m¨ ussen, und dass keine der ausgew¨ ahlten Knoten in Wr vorkommen kann. Es gilt also |V (T )| − 1 ≤ |V (G) \ Wr |, woraus die Behauptung unmittelbar folgt.

6.2

Algorithmische Konsequenzen

Lemma 6.4 Ist G ein Graph und (T, W) eine Baumzerlegung f¨ ur G, so gilt: a) F¨ ur jede Kante {x, y} in T ist Wx ∩ Wy ein Separator in G. b) F¨ ur jeden Knoten x in T ist Wx ein Separator in G. Beweis: a) Die Kante {x, y} zerlegt den Baum T in zwei disjunkte Teilb¨aume Tx und Ty , wobei x ∈ Tx und y ∈ Ty . Setzt man # # Wz und Vy := Wz , Vx := z∈Tx

z∈Ty

so folgt aus der Definition der Baumzerlegung sofort, dass Vx ∩ Vy = Wx ∩ Wy und dass es zu Knoten v ∈ Vx \ (Wx ∩ Wy ) und w ∈ Vy \ (Wx ∩ Wy ) keinen Knoten z ∈ T geben kann mit {v, w} ⊆ Wz . (Denn z m¨ usste zu Tx oder Ty geh¨ oren und dann m¨ usste wegen der Zusammenhangsbedingung der Definition der Baumzerlegung die Menge Wx ∩ Wy auch einen der beiden Knoten v und w enthalten.) Insbesondere kann G somit keine Kante zwischen Vx \ (Wx ∩ Wy ) und Vy \ (Wx ∩ Wy ) enthalten.

6.2. ALGORITHMISCHE KONSEQUENZEN

81 a

a

c

c b

b

b b

d

d

d

e e

Abbildung 6.2: B¨aume haben Baumweite 1

b) Der Beweis folgt analog zu dem Beweis in a), in dem man alle Teilb¨aume T  in T \ x betrachtet.

Satz 6.5 Ist (T, W) eine Baumzerlegung eines Graphen G mit Baumweite k, so kann man in Zeit O(|V (T )|) einen (k + 1, 12 )-Separator in G bestimmen.

Beweis: Wir w¨ ahlen einen beliebigen Knoten r ∈ T als Wurzel von T und definieren eine Gewichtsfunktion w : V (T ) → N0 wie folgt. F¨ ur r setzen wir w(r) := |Wr |. F¨ ur alle u ¨ brigen Knoten x ∈ T \ r bezeichne parent(x) den (eindeutig bestimmten!) Vorg¨anger von x in dem am Knoten r aufgeh¨angten“ ” Baum T . Wir setzen dann w(x) := |Wx \ Wparent(x) |. Beachte, dass auf Grund der Zusammenhangsbedingung in der nach
Definition der Baumzerlegung jeder Knoten v ∈ V insgesamt genau einmal gez¨ ahlt wird. Es gilt daher x∈T w(x) = |V | ist. Nach Satz 5.3 kann man in linearer Zeit einen Knoten x0 ∈ T finden, so dass das Gesamtgewicht
 ochstens 12 |V | ist. u ¨ berz∈T  w(z) eines jeden Teilbaumes T in T \ x0 h¨  Da man sich leicht davon
 zeugt, dass f¨ ur jeden Teilbaum T in T \ x0 die Anzahl Knoten in ( z∈T  Wz ) \ Wx0 durch z∈T  w(z) beschr¨ ankt ist, folgt hieraus zusammen mit Lemma 6.4 sofort die Behauptung.

Geht man ¨ ahnlich wie in Algorithmus PlanarIndSet(G) aus Abschnitt 5.2 vor, so kann man aus Satz 6.5 folgern, dass man in Graphen mit Baumweite h¨ochstens k eine maximale stabile Menge in Zeit O(nk+1 ) berechnen kann, so eine entsprechende Baumzerlegung bekannt ist. Zusammen mit den Resultaten aus Abschnitt 6.4 (in dem wir zeigen werden, dass man eine Baumzerlegung effizient berechnen kann) folgt daher, dass f¨ ur jedes konstante k ∈ N in Graphen mit Baumweite h¨ochstens k eine maximale stabile Menge in polynomieller Zeit berechnet werden kann.

Verwendet man statt Satz 6.5 und Divide-and-Conquer eine dynamische Programmierung l¨asst sich Laufzeit dramatisch verbessern: statt O(nk+1 ) ben¨otigt man damit nur O(n), wobei allerdings die im Gross-Oh verborgene Konstante exponentiell von k abh¨angt.

Um dies einzusehen, gehen wir ¨ ahnlich vor, wie in dem in der Einleitung des Kapitels vorgestellten Algorithmus f¨ ur B¨ aume.

¨ KAPITEL 6. BESCHRANKTE BAUMWEITE

82

Gegeben sei also ein Graph G und eine Baumzerlegung (T, W). Wir w¨ahlen einen Knoten r ∈ V (T ) als Wurzel beliebig aus Dies definiert f¨ ur jeden Knoten x ∈ V (T ) einen eindeutigen Unterbaum Tx , der alle Knoten unterhalb von x in dem im Knoten r aufgeh¨angten“ Baum enth¨alt. Weiter bezeichne Γsuc (x) ” die Menge der Nachfolger von x im gewurzelten Baum T . F¨ ur jeden Knoten x ∈ V (x) definieren wir f¨ ur alle Mengen S ⊆ Wx : # ˜ ˜ | S˜ ⊆ Wy , S˜ unabh¨angig, S ⊆ S}, w(x, S) := max{|S| y∈V (Tx )

Offensichtlich ist maxS⊆Wr w(r, S) die Kardinalit¨at einer maximalen unabh¨angigen Menge in G und man kann die Werte w(x, S) rekursiv bottom-up m¨assig berechnen, denn es gilt: ⎧ ⎪ 0, falls S nicht unabh¨angig ⎪ ⎪ ⎪ ⎨|S|, falls x ein Blatt ist und S unabh¨angig  w(x; S) = ⎪ |S| + max (w(y, S ) − |S ∩ S |), sonst y y ⎪ Sy ⊆Wy ⎪ ⎪ ⎩ y∈Γsuc (x) S∩Wy ⊆Sy Sy ∩Wx ⊂Sy

ur die Anzahl Teilmengen S ⊆ Wx ) mal deg(x) · 2k . Der Der Aufwand f¨ ur einen Knoten x ist 2k (f¨ Gesamtaufwand l¨ asst sich somit durch O(4k · |E(T )|) = O(4k · |V (T )|) = O(4k · |V (G)|) absch¨atzen (wobei die letzte Gleichheit aus Lemma 6.3 folgt). Wir haben also gezeigt: Satz 6.6 In Graphen G, f¨ ur die eine Baumzerlegung (T, W) mit Baumweite k bekannt ist, l¨asst sich eine (kardinalit¨ats-)maximale unabh¨angige Menge mit der dynamischen Programmierung in Zeit O(4k ·|V (G)|) berechnen. ¨ Ahnliche Ans¨ atze funktionieren auch f¨ ur viele andere NP-vollst¨andige Probleme.

6.3

Partielle k-B¨ aume

Eigenschaft (3) der Einleitung dieses Kapitels k¨onnen wir verwenden, um eine Verallgemeinerung der Klasse der B¨ aume der erzielen. Definition 6.7 Ein Graph G = (V, E) ist ein k-Baum, falls es eine Reihenfolge v1 , . . . , vn der Knoten von G gibt, so dass gilt: (i) n ≥ k + 1 und G[{v1 , . . . , vk+1 }] ist eine (k+1)-Clique und (ii) f¨ ur alle k + 2 ≤ i ≤ n gilt: In dem von den Knoten v1 , . . . , vi induzierten Subgraphen G[{v1 , . . . , vi }] bildet die Nachbarschaft von vi eine k-Clique. Ein Graph G = (V, E) ist ein partieller k-Baum, falls es einen k-Baum G0 = (V, E0 ) gibt, so dass G Subgraph von G0 ist. Alternativ kann man sich die Definition eines k-Baumes wie folgt veranschaulichen. Einen k-Baum erh¨ alt man, in dem man mit einer (k+1)-Clique beginnt und dann sukzessive Knoten so hinzuf¨ ugt, dass man sie vollst¨ andig mit einer k-Clique des bereits konstruierten Graphen verbindet. 1-B¨ aume sind genau die B¨ aume im klassischen Sinne. Intuitiv sind daher k-B¨aume um so baum-¨ahn” licher“, je kleiner k ist. Dies werden wir sp¨ater noch genauer formalisieren. Zun¨achst jedoch noch eine ur die BeAnmerkung zur Definition. Die Forderung, dass Γ(vi ) in G[{v1 , . . . , vi }] eine Clique bildet, ist f¨ deutung der k-B¨ aume absolut essentiell. W¨ urde man beispielsweise statt dessen lediglich fordern, dass vi in G[{v1 , . . . , vi }] Grad h¨ ochstens k hat, w¨ urde man eine wesentlich gr¨ossere Klasse erhalten, die bereits f¨ ur kleine k u ¨ berhaupt nicht mehr baum-¨ahnlich“ sind. Beispielsweise w¨are dann jedes Gitter bereits ein ” 2-Baum – was u ¨berhaupt nicht der Intuition entspricht.

¨ 6.3. PARTIELLE K-BAUME

83

Aus der Definition eines k-Baumes folgt sofort: Lemma 6.8 F¨ ur jeden partiellen k-Baum G = (V, E) gilt |E| ≤ k|V |. Beweis: Offenbar gen¨ ugt es die Behauptung f¨ ur k-B¨aume zu zeigen. Wir zeigen dies durch Induktion   u ur n = k + 1 ist |E| = k+1 ≤ k(k + 1). F¨ ur den Induktionsschritt beachte man, dass aus ¨ ber n = |V |. F¨ 2 der Induktionsannahme folgt, dass f¨ ur G := G \ vn gilt: |E(G )| ≤ k|V (G )|. Wegen |V (G )| = |V (G)| − 1 und |E(G)| = |E(G )| + k folgt daraus sofort die Behauptung. Satz 6.9 Sei G = (V, E) ein Graph. Dann sind ¨aquivalent: (i) G ist ein partieller k-Baum. (ii) G hat Baumweite ≤ k. Beweis: Wir halten zun¨ achst fest, dass es gen¨ ugt den Satz f¨ ur zusammenh¨angende Graphen G zu beweisen. ⇐=“: Sei G ein Graph und (T, W) eine Baumzerlegung mit Baumweite k. Wir definieren nun einen ” Graphen GT = (VT , ET ) in dem wir auf jeder Menge Wx der Baumzerlegung eine Clique bilden: # Wx  GT := . 2 x∈T

Gem¨ ass Definition der Baumzerlegung ist VT = V und es gilt E ⊆ ET . Zu zeigen ist also lediglich, dass GT ein partieller k-Baum ist. Dies zeigen wir durch Induktion u ¨ber die Kardinalit¨at t = |V (T )| der Knotenmenge der Baumzerlegung (T, W). F¨ ur t = 1 ist GT eine (k+1)-Clique und die Behauptung somit richtig. F¨ ur den Beweis des Induktionsschrittes t ⇒ t + 1 w¨ ahlen wir ein beliebiges Blatt x0 in T und setzten T  := T \ x0 . Nach Induktions T  auf der Knotenmenge von annahme ist GT  ein partieller k-Baum und es gibt daher einen k-Baum G  GT  , so dass GT  Subgraph von GT  ist. Es sei y0 der (eindeutig bestimmte!) Nachbar von x0 in T . Wir unterscheiden zwei F¨alle. Falls Wx0 = Wy0 , ur jeden Knoten w ∈ Wx0 \ Wy0 : so ist GT = GT  und GT also ein partieller k-Baum. Andernfalls gilt f¨ w ∈ Wz f¨ ur alle z ∈ T \ x0 . Daher ist w in GT nur mit Knoten aus Wx0 verbunden. Da G nach Annahme zusammenh¨ angend ist, kann Wx0 ∩ Wy0 nicht leer sein. Sei u derjenige Knoten aus Wx0 ∩ Wy0 der in T  als letztes eingef¨ ugt wurde. Dann ist (Wx0 ∩ Wy0 ) \ {u} ⊆ ΓG
 (u). Dies bedeutet den k-Baum G T  insbesondere, dass GT  (u) eine (k+1)-Clique mit allen Knoten aus Wx0 ∩ Wy0 enth¨alt. Wir k¨onnen daher  T erweitern, in dem wir die Knoten w1 , . . . , w aus Wx0 \ Wy0 in T  zu einem k-Baum G den k-Baum G  ugen k¨onnen, dass die Nachbarschaft von wi jeweils eine k-Clique ist, beliebiger Reihenfolge so an GT  anf¨ die alle Knoten aus {w1 , . . . , wi−1 } ∪ (Wx0 ∩ Wy0 ) enth¨alt. Nach Konstruktion ist GT ein Subgraph des T , somit ist GT ein partieller k-Baum, was zu zeigen war. k-Baumes G =⇒“: Da jede Baumzerlegung f¨ ur einen Graphen G auch automatisch eine Baumzerlegung f¨ ur alle ” Subgraphen von G darstellt, gen¨ ugt es die Aussage f¨ ur k-B¨aume zu zeigen. Sei also G = (V, E) ein kBaum und v1 , . . . , vn eine Reihenfolge der Knoten von V gem¨ass Definition 6.7. Wir zeigen nun durch Induktion u ¨ ber i: F¨ ur alle k + 1 ≤ i ≤ n gilt: F¨ ur Gi := G[{v1 , . . . , vi }] gibt es eine Baumzerlegung (Ti , Wi ) mit Baumweite k, so dass es f¨ ur alle 1 ≤ j ≤ i einen Knoten xj ∈ T gibt, so dass {vj }∪ΓGj (vj ) ⊆ Wxj . (Hierbei bezeichne ΓGj (v) die Nachbarschaft von v in dem Graphen Gj .) Die Induktionsverankerung f¨ ur i = k + 1 folgt unmittelbar in dem wir als Tk+1 einen Baum auf einem ur Knoten x w¨ ahlen und diesem Knoten als Knotenmenge die Menge Wx := {v1 , . . . , vk+1 } zuordnen. F¨ den Beweis des Induktionsschrittes von i nach i + 1 betrachten wir die Nachbarschaft von vi+1 in Gi+1 . Nach Definition eines k-Baumes bildet diese Nachbarschaft eine k-Clique in Gi . Die Nachbarn seien vj1 , . . . , vjk , wobei 1 ≤ j1 < · · · < jk ≤ i. Nach Induktionsannahme gibt es in der Baumzerlegung (Ti , Wi ) einen Knoten x mit {vjk } ∪ ΓGjk (vjk ) ⊆ Wx . Wir konstruieren nun eine Baumzerlegung (Ti+1 , Wi+1 ) f¨ ur atzlichen Knoten x hinzuf¨ ugen, den wir mit dem Knoten x verbinden. Gi+1 in dem wir zu Ti einen zus¨ Als Knotenmenge Wx w¨ ahlen wir Wx = {vi+1 } ∪ ΓGi+1 (vi+1 ).

84

¨ KAPITEL 6. BESCHRANKTE BAUMWEITE

unschte Baumzerlegung f¨ ur Gi+1 bildet. Man Nachzupr¨ ufen ist nun, dass (Ti+1 , Wi+1 ) in der Tat die gew¨ sieht schnell ein, dass der einzig kritische Fall die Zusammenhangsbedingung aus Definition 6.1 ist. Dass ur v = vi+1 kommt v in keiner diese gilt, sieht man wie folgt ein. Sei v ein beliebiger Knoten aus Wx . F¨ anderen Menge Wy vor. Es ist also nichts zu zeigen. F¨ ur v = vjk gilt v ∈ Wx nach Wahl von x . F¨ ur alle u ¨ brigen v ∈ Wx \ {vi+1 , vjk } ist v ∈ ΓGjk (vjk ), da nach Definition vjk derjenige Nachbar von vi+1 ist, der den h¨ ochsten Index hat. Somit gilt v ∈ Wx und die Zusammenhangsbedingung ist daher f¨ ur jeden ullt. Knoten v ∈ Wx erf¨

6.4

Bestimmung einer Baumzerlegung

In diesem Abschnitt wollen wir uns der Frage zuwenden, wie man zu einem gegebenen Graphen eine Baumzerlegung mit m¨ oglichst kleiner Baumweite bestimmt. Dazu halten wir zun¨ achst ohne Beweis fest, dass dieses Problem in voller Allgemeinheit schwierig ist. Satz 6.10 Das Problem Gegeben ein Graph G = (V, E) und ein k ∈ N, ist die Baumweite von G ” h¨ ochstens k?“ ist NP-vollst¨andig. In diesem Abschnitt werden wir uns daher mit einer einfacheren Variante des Problems besch¨aftigen. Zum einen werden wir nur Graphen mit konstanter Baumweite betrachten. Zum anderen werden wir uns damit zufrieden geben, nicht eine Baumzerlegung mit minimaler Baumweite zu berechnen, sondern wir geben uns f¨ ur Graphen mit Baumweite < k mit mit Baumzerlegungen mit Baumweite ≤ 3k zufrieden. Man beachte, dass dies ausreicht, um die Algorithmen aus Abschnitt 6.2 anzuwenden: Es verschlechtert sich zwar die Laufzeit, aber polynomielle Algorithmen bleiben polynomiell und lineare Algorithmen bleiben linear. Um den zu konstruierenden Algorithmus genauer beschreiben zu k¨onnen ben¨otigen wir zun¨achst noch den Begriff eines S-Separators. Definition 6.11 Sei G = (V, E) und S ⊆ V . Eine Menge C ⊆ V heisst S-Separator, falls es eine Partition von V \ C in Mengen A und B gibt, so dass E ∩ A × B = ∅ (also G keine Kante zwischen A und B enth¨alt) und |A ∩ S| ≤ |B ∩ S| ≤ 12 |S|. Lemma 6.12 Ist G = (V, E) ein Graph mit Baumweite k, dann gibt es f¨ ur jede Menge S ⊆ V einen S-Separator C der Gr¨osse |C| ≤ k + 1. Beweis: Wie gehen ganz analog zum Beweis von Satz 6.5 vor. D.h., wir w¨ahlen einen beliebigen Knoten ur r setzen wir r ∈ T als Wurzel von T und definieren eine Gewichtsfunktion w : V (T ) → N0 wie folgt. F¨ w(r) := |Wr ∩ S|. F¨ ur alle u ¨ brigen Knoten x ∈ T \ r sei w(x) := |(Wx ∩ S) \ Wparent(x) |, wobei parent(x) den (eindeutig bestimmten!) Vorg¨ anger von x in dem am Knoten r gewurzelten Baum T bezeichne. Beachte, dass nach Definition jeder Knoten v ∈ S insgesamt genau einmal gez¨ahlt wird. Es gilt daher
x∈T w(x) = |S| ist. Nach Satz 5.3 kann man in linearer Zeit einen Knoten x0
∈ T finden, so dass das Gesamtgewicht
1 1  w(z) eines jeden Teilbaumes T in T \ x h¨ o chstens  0 z∈T x∈T w(x) = 2 |S| ist. 2  Da man sich leicht  davon
u ur jeden Teilbaum T in T \ x0 die Anzahl Knoten in (( z∈T  Wz ) \ Wx0 ) ∩ S ¨ berzeugt, dass f¨ durch z∈T  w(z) beschr¨ ankt ist, folgt hieraus zusammen mit Lemma 6.4 sofort die Behauptung. Unser Ziel ist es nun, einen Algorithmus f¨ ur das folgende Problem zu konstruieren: Algorithmus TreeFinder(G, k, X) Eingabe: Graph G = (V, E), k ∈ N, X ⊆ V mit |X| ≤ 2k. Ausgabe: Entweder eine Baumzerlegung (T, W) mit Baumweite ≤ 3k und der Eigenschaft X ⊆ Wt f¨ ur ein t ∈ T oder eine Menge S ⊆ V , so dass G keinen S-Separator der Gr¨oße ≤ k besitzt.

6.4. BESTIMMUNG EINER BAUMZERLEGUNG

85

Man beachte, dass es f¨ ur Graphen mit Baumweite < k gem¨ass Lemma 6.12 keine Menge S ⊆ V geben kann, f¨ ur die der Oder-Fall eintritt. D.h. f¨ ur Graphen mit Baumweite < k wird der Algorithmus – unabh¨ angig von der Wahl der Menge X – immer eine Baumzerlegung mit Baumweite ≤ 3k ausgeben. Wir konstruieren den Algorithmus TreeFinder in dem wir das Problem auf drei einfachere Algorithmen zur¨ uckf¨ uhren, die wir jetzt vorstellen und herleiten werden. Algorithmus PathFinder(G, k, s, t) Eingabe: Graph G = (V, E), k ∈ N, Knoten s, t ∈ V mit {s, t} ∈ E. Ausgabe: Entweder k paarweise intern knoten-disjunkte s-t-Pfade oder einen Separator C ⊆ V mit |C| < k, so dass es eine Partition von V \C in Mengen A und B gibt, so dass s ∈ A, t ∈ B und E ∩ (A × B) = ∅.

Satz 6.13 Es gibt einen Algorithmus PathFinder(G, k, s, t) mit Laufzeit O(k · |E|). Beweis: Wir beobachten zun¨ achst, dass das Problem ganz ¨ahnlich zu einem und aus Kapitel 1 gut bekannten Flussproblem ist. Ersetzt man n¨ amlich die Annahme knoten-disjunkt“ durch kanten-disjunkt“, ” ” so entspricht der Entweder“-Teil der Ausgabe genau der Frage, ob es einen Fluss der St¨arke k in dem ” (ungewichteten) Netzwerk N = (V, A, s, t) gibt, wobei A = {(u, v), (v, y) | {u, v} ∈ E}. Zur L¨osung der kanten-disjunkten Variante des Problems k¨onnen wir daher wie folgt vorgehen: • Verwende den Algorithmus von Ford-Fulkerson f¨ ur das Netzwerk N = (V, A, s, t). Beachte, dass sich der Fluss - da der Graph ungewichtet ist - bei in jedem Augmentierungsschritt um genau Eins erh¨ oht. • Falls der Algorithmus nach weniger als k Augmentierungsschritten stoppt, sei (W, W ) ein s-t-Schnitt mit c(W, W ) = w(f ) < k. Setze C := {x ∈ W | ∃y ∈ W mit {x, y} ∈ E}. Dann gilt |C| ≤ k wegen c(W, W ) = w(f ) < k und C ist somit der gesuchte Separator, wobei A = W \ C und B = W .2 • Ansonsten stoppe nach k Augmentierungsschritten: Der dann gefundene Fluss entspricht der Vereinigung der k gesuchten Pfade und die Pfade lassen sich aus dem Fluss leicht rekonstruieren ¨ (Ubungsaufgabe). Die L¨ osung f¨ ur die gesuchte knoten-disjunkte Varianten k¨onnen wir durch einen einfachen Trick auf die kanten-disjunkte Variante zur¨ uckf¨ uhren. Dazu konstruieren wir ausgehend von dem oben eingef¨ uhrten Netzwerk N = (V, A, s, t) ein neues Netzwerk N  = (V  , A , s, t) in dem wir jeden Knoten v ∈ V \ {s, t} durch zwei Knoten vin und vout ersetzen und alle eingehenden Kanten mit vin verbinden und alle ausgehenden Kanten mit vout . Zus¨ atzlich f¨ ugen wir zwischen vin und vout eine von vin nach vout gerichtete Kante ein. Abbildung 6.3 zeigt diese Konstruktion an einem Beispiel.3 Man u ¨ berzeugt sich leicht davon, dass das neue Netzwerk N  die Eigenschaft hat, dass kanten-disjunkte Pfade in N  knoten-disjunkten Pfaden in N entsprechen. Das knoten-disjunkte Problem in N k¨onnen wir somit dadurch l¨ osen, dass wir kanten-disjunkte Pfade in N  suchen – was wir mit dem oben beschriebenen Verfahren tun k¨ onnen. Es bleibt zu zeigen, wie wir einen eventuell gefundenen Separator C  ⊆ V  in einen Separator C ⊆ V umwandeln k¨ onnen. Dazu u ¨ berlegen wir uns, dass in dem Netzwerk N  ein minimaler s-tSchnitt (W, W ) immer so gew¨ ahlt werden kann, dass f¨ ur alle Kanten (x, y) mit x ∈ W und y ∈ W gilt, dass es ein v ∈ V \{s, t} gibt mit x = vin und y = vout . Setzen wir daher C = {v ∈ V | vin ∈ W und vout ∈ W }, so ist C der gesuchte Separator.4 2 Genau genommen, l¨ ost dieser Algorithmus nur eine leichte Verallgemeinerung des angegebenen Problems: Gem¨ ass Konstruktion der Menge C k¨ onnte s ∈ C sein, wir m¨ ussen daher statt s ∈ A den Fall s ∈ A ∪ C erlauben. Dies wird im Weiteren aber nicht st¨ oren. 3 Genau genommen m¨ ¨ ussten wir beim Ubergang vom Graphen G zum Netzwerk N f¨ ur den Knoten s nur ausgehende und f¨ ur den Knoten t nur eingehende Kanten betrachten. Wir haben jeweils beide Richtungen eingef¨ ugt, um die Definition syntaktisch einfach zu halten. 4 Beachte, dass wir im Netzwerk N
immer einen Separator C finden k¨ onnen, der den Knoten s nicht enth¨ alt.

¨ KAPITEL 6. BESCHRANKTE BAUMWEITE

86 a

s

t

b

a in

a

c

s

t

b

G=(V,E)

Netzwerk

out

s

t

c b in

Graph

a

N=(V,A,s,t)

Netzwerk

b

out

c in

c

out

N’=(V’,A’,s,t)

Abbildung 6.3: Konstruktion des Netzwerks N  = (V  , A , s, t) Algorithmus PathFinderForSets(G, k, S, T ) Eingabe: Graph G = (V, E), k ∈ N, disjunkte Mengen S, T ⊆ V mit E ∩ (S × T ) = ∅. Ausgabe: Entweder k paarweise intern knoten-disjunkte S-T -Pfade (also Pfade mit Anfangspunkt in S und Endpunkt in T , so dass alle inneren Knoten der Pfade in V \ (S ∪ T ) liegen und die (inneren) Knoten der Pfaden paarweise verschieden sind) oder einen Separator C ⊆ V mit |C| < k, so dass es eine Partition von V \C in Mengen A und B gibt, so dass S ⊆ A, T ⊆ B und E ∩ (A × B) = ∅. Satz 6.14 Es gibt einen Algorithmus PathFinderForSets(G, k, S, T ) mit Laufzeit O(k · |E|). Beweis: Den gew¨ unschten Algorithmus erh¨alt man ganz einfach dadurch, dass man das Pfadproblem ur Knoten s und t reduziert. Dazu ersetzt man einfach f¨ ur Mengen S und T auf ein Pfadproblem f¨ alle Knoten aus S durch einen neuen Knoten s und verbindet s mit allen Knoten u f¨ ur die es eine Kante zwischen einem Knoten aus S und u gibt. Analog geht man f¨ ur die Menge T vor, ersetzt also die Knoten aus T durch einen neuen Knoten t, der entsprechend angebunden wird. Diese Reduktion l¨ asst sich in Zeit O(|E|) durchf¨ uhren. Jetzt rufen wir f¨ ur den neu konstruierten Graphen G den Algorithmus unschte Ausgabe bestimmt. PathFinder(G , k, s, t) auf, der in Zeit O(k · |E|) die gew¨ Algorithmus SeparatorFinder(G, k, X) Eingabe: Graph G = (V, E), k ∈ N, eine Menge X ⊆ V mit |X| ≤ 2k. Ausgabe: Ein X-Separator C von G mit |C| ≤ k, falls ein solcher existiert. Satz 6.15 Es gibt einen Algorithmus SeparatorFinder(G, k, X) mit Laufzeit O(9k k · |E|). Beweis: Die Idee ist folgende. Nehmen wir an es gibt einen X-Separator C mit |C| ≤ k und einer Partition A ∪ B von V \ C mit den gew¨ unschten Eigenschaften. Setzen wir dann S := X ∩ A, T := X ∩ B und XC := X ∩ C, dann gibt es in G[V \ XC ] sicherlich keine k + 1 − |XC | viele intern knoten-disjunkten Pfade von S nach T , denn alle diese Pfade m¨ ussten einen Knoten aus C \XC enthalten und nach Annahme gilt |C \ XC | = |C| − |XC | ≤ k − |XC |. Wir k¨ onnen das Separator-Problem daher wie folgt l¨osen: • F¨ ur alle Partitionen X = S ∪ XC ∪ T mit |S|, |T |, |XC | ≤ k rufe PathFinderForSets(G[V \ XC ], k + 1 − |XC |, S, T ) auf. • Falls f¨ ur eine solche Partition S ∪ XC ∪ T von Algorithmus PathFinderForSets ein Separator C ausgegeben wird, dann ist C ∪ XC der gesuchten Separator. • Ansonsten wissen wir, dass es in G keinen X-Separator der Gr¨osse ≤ k geben kann. Die behauptete Laufzeit ergibt sich aus Satz 6.14 und der Tatsache, dass sich die Anzahl der zu betrachteten Partitionen durch 3|X| ≤ 9k absch¨ atzen l¨asst.

6.4. BESTIMMUNG EINER BAUMZERLEGUNG

87

Satz 6.16 Es gibt einen Algorithmus TreeFinder(G, k, X) der f¨ ur Graphen G = (V, E) mit m ≤ 3kn Laufzeit O(9k k 2 n) hat.5 Beweis: • Wir rufen SeparatorFinder(G, k, X) auf. • Falls vom Algorithmus SeparatorFinder kein Separator gefunden wird, gebe X als Menge S aus (oder-Fall). • Ansonsten sei C mit |C| ≤ k der vom Algorithmus gefundene Separator. Dann zerf¨allt G[V \ C] in zwei oder mehr Komponenten, wobei jede Komponente h¨ochstens 12 |X| ≤ k Knoten aus X enth¨alt. Wir bezeichnen mit U1 , . . . , U die Knotenmengen der Komponenten in G[V \ C] und setzen: Gi

:= G[C ∪ Ui ]

Xi

:= (Ui ∩ X) ∪ C.

und

• Nun rufen wir f¨ ur alle i = 1, . . . ,  den Algorithmus TreeFinder(Gi , k, Xi ) auf. ur das TreeFinder(Gi0 , k, Xi0 ) eine Menge Si0 ausgibt, f¨ ur die • Falls es ein 1 ≤ i0 ≤  gibt, f¨ osse ≤ k hat, geben wir diese Menge Si0 als Menge S aus, f¨ ur Gi0 keinen Si0 -Separator der Gr¨ die G keinen S-Separator der Gr¨ osse ≤ k hat (denn jeder solche Separator w¨ urde einen f¨ ur Gi0 induzieren). ur alle 1 ≤ i ≤  • Ansonsten erhalten wir f¨ ur alle 1 ≤ i ≤  eine Baumzerlegung (Ti , Wi ) wobei es f¨ einen Knoten ti ∈ V (Ti ) gibt mit Xi ⊆ Wti . • Diese Baumzerlegungen setzen wir nun zu einer Baumzerlegung (T, W) zusammen. Dazu setzen wir # V (Ti ), V (T ) := {t0 } ∪ 1≤i≤

E(T ) :=

{{t0 , t1 }, {t0 , t2 }, . . . , {t0 , t }} ∪ 

Wx

:=

Wx , X ∪ C,

falls x ∈ sonst.

 1≤i≤

#

E(Ti ),

1≤i≤

V (Ti )

F¨ ur die Korrektheit des Algorithmus muss man sich zum einen davon u ¨ berzeugen, dass der Aufruf von TreeFinder(Gi , k, Xi ) zul¨ assig ist, dass also |Xi | ≤ 2k gilt, und zum anderen, dass (T, W) die gesuchte uft man leicht nach. Baumzerlegung ist. Ersteres folgt wegen |Xi | ≤ |Ui ∩ X| + |C| ≤ k + k. Letzteres pr¨ Die Laufzeit ergibt sich wie folgt. F¨ ur den Aufruf von SeparatorFinder(G, k, X) ben¨otigt man gem¨ ass Satz 6.15 Laufzeit O(9k k · |E|) = O(9k k 2 · |V |) Bezeichnen wir daher mit t(n) die maximale Laufzeit von TreeFinder(G, k, X) f¨ ur Graphen G = (V, E) auf |V | = n Knoten und m ≤ 3kn Kanten, so erhalten wir die Rekursionsgleichung  t(ni + c), t(n) ≤ O(9k k 2 n) + max c,ni

1≤i≤

wobei das Maximum u ¨ber alle 1 ≤ c = |C| ≤ k und Partitionen n1 + · · · + n = n − c gebildet wird. Per ¨ Induktion zeigt man nun (Ubungsaufgabe!), dass t(n) = O(9k k 2 n2 ).

5 F¨ ur

Graphen G mit m > 3kn kann nach Lemma 6.8 der Entweder-Fall gar nicht vorkommen.