close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Diskrete Strukturen Skript zum Kapitel `Gerichtete Graphen`

EinbettenHerunterladen
Diskrete Strukturen
Skript zum Kapitel ‘Gerichtete Graphen’
Manuel Bodirsky,
Institut f¨
ur Algebra, TU Dresden,
Manuel.Bodirsky@tu-dresden.de
3. Februar 2015
1
1
Gerichtete Graphen
Ein gerichteter Graph ist ein Paar G = (V, E) wobei
• V eine beliebige Menge ist, deren Elemente wir Knoten nennen, und
• E ⊆ V 2 eine Menge von Knotenpaaren ist, die wir (gerichtete) Kanten nennen.
Mit anderen Worten, ein gerichteter Graph ist eine Menge zusammen mit einer bin¨aren
Relation auf dieser Menge.
Ist (v, w) eine Kante im gerichteten Graphen (V, E), so nennen wir w einen Nachfolger
von v und v einen Vorg¨
anger von w. Ein Knoten v ∈ V ist eine Quelle, wenn er keinen
Vorg¨anger hat, und eine Senke, wenn er keinen Nachfolger hat. Ein gerichteter Pfad ist
eine Folge v1 , v2 , . . . , vn so dass (vi , vi + 1) ∈ E f¨
ur alle i ∈ {1, . . . , n − 1}. Wir sprechen
in diesem Fall auch von einem gerichteten Pfad von v1 nach v2 (in (V, E)), und v2 ist ein
Nachfahre von v1 , und v1 ein Vorfahre von v2 . Wir sagen in diesem Fall auch, dass v2 von
v1 aus (in (V, E)) erreichbar ist, und schreiben v1 v2 .
Ein (gerichteter) Kreis ist in gerichteten Graphen (V, E) eine Folge v0 , . . . , vn−1 von
Knoten aus V mit (vi , vi+1 ) ∈ E f¨
ur alle i ∈ Zn . Ein gerichteter Graph ist ein Wald, wenn
jeder Knoten h¨
ochstens einen Vorg¨anger hat. W¨alder mit nur einer Quelle heißen B¨
aume
(und die Quelle heißt die Wurzel des Baumes). W¨alder sind also disjunkte Vereinigungen
von B¨aumen.
Wir definieren die Erreichbarkeitsrelation in (V, E) wie folgt: x y gelte genau
dann, wenn es in (V, E) einen gerichteten Pfad von x nach y gibt. In der Terminologie von
Abschnitt ?? ist also der transitive Abschluss der Kantenrelation E. Zwei Knoten u und
v sind also genau dann unvergleichbar in dieser Ordnung, wenn u weder Vorfahre noch
Nachfahre von v ist.
Proposition 1. Die Erreichbarkeitsrelation in einem Graphen G ist eine Quasiordnung.
Falls G kreisfrei ist, so ist eine partielle Ordnung. In B¨
aumen ist eine semilineare
Ordnung.
1.1
Tiefensuche
Tiefensuche ist ein Verfahren, um einen gegebenen ungerichteten oder gerichteten Graphen
zu durchsuchen. Die Suche kann bei einem beliebigen Knoten v des Graphen begonnen
werden. Das besondere bei der Tiefensuche ist, dass f¨
ur jeden betretenen Knoten zuerst die
von diesem Knoten aus erreichbaren Knoten so weit wie m¨oglich erkundet werden, bevor
man wieder zur¨
uck geht (‘backtracking’). Das Verfahren ist in Pseudocode in Abbildung 1
dargestellt. Im Verfahren wird jeder Knoten, der betreten wird, markiert. Auf diese Weise
weiss man am Ende des Verfahrens, welche Knoten von v aus erreichbar sind, n¨amlich
genau die markierten. F¨
ur manche Anwendungen der Tiefensuche werden wir sp¨ater noch
mehr Informationen in den Markierungen abspeichern.
2
Tiefensuche(G, v).
Eingabe: G = (V, E), v ∈ V .
Ausgabe: Markiere alle von v aus in G erreichbaren Knoten.
Markiere v.
F¨
ur alle Kanten von v zu einem w in G:
Falls w noch nicht markiert
Tiefensuche(G, w).
Abbildung 1: Tiefensuche.
Diese simple Idee ist ausgesprochen m¨achtig und n¨
utzlich. Wir werden von einfachen
Dingen, die man mit Tiefensuche bewerkstelligen kann, zu immer trickreicheren Anwendungen der Tiefensuche kommen.
Jede Tiefensuche definiert gewisse lineare Ordnungen auf der Menge der Knoten V .
Dazu starten wir die Tiefensuche in einem beliebigen Knoten. Wann immer die Tiefensuche
abbricht, aber noch nicht alle Knoten markiert wurden, starten wir die Tiefensuche in einem
noch unmarkierten Knoten neu, solange bis alle Knoten des Graphen markiert sind. Nun
betrachten wir die folgenden linearen Ordnungen auf V :
• zum einen ist dies die Ordnung, in der die Knoten zum ersten Mal betreten werden.
Wir nummerieren die Knotenmenge N bez¨
uglich dieser Ordnung mit 1 bis n = |V |
durch, und schreiben s(v) f¨
ur die Nummer von v in dieser Nummerierung. Die Zahl
s(v) ∈ {1, . . . , n} heißt auch die Startzeit von v.
• zum anderen ist dies die Ordnung, in der die Knoten das letzte Mal betrachtet werden. Erneut nummerieren wir die Knoten gem¨aß dieser Ordnung, und schreiben f (v)
f¨
ur die Nummer von v in dieser zweiten Nummerierung. Die Zahl f (v) heißt die
Schlusszeit von v.
Diese Ordnungen sind f¨
ur einen gegebenen Graphen G selbstverst¨andlich nicht eindeutig, sondern h¨
angen vom Verlauf der Tiefensuche auf G ab. Das oben beschriebene Verfahren (Tiefensuche mit Neustarts bis alle Knoten markiert sind) werden wir vollst¨
andige
Tiefensuche nennen. In der vollst¨andigen Tiefensuche markieren wir jeden Knoten sowohl
mit s(v) als auch mit f (v).
Anhand einer vollst¨
andigen Tiefensuche kann jede Kante (u, v) ∈ E des Graphen in
vier verschiedene Typen eingeteilt werden (siehe auch Abbildung 2):
1. Baumkanten. Dies sind die Kanten, entlang derer die Tiefensuche von einem markierten Knoten zu einem neuen unmarkierten Knoten schreitet. Es gilt
s(u) < s(v) und f (u) > f (v) .
3
2. Vorw¨
artskanten. Sind die Kanten, die nicht Baumkanten sind, und die einen Knoten
des Baumes mit einem seiner Nachfahren verbindet. Es gilt
s(u) < s(v) und f (u) > f (v) .
3. R¨
uckw¨
artskanten. Sind die Kanten, die von einem Knoten zu einem seiner Vorfahren
im gleichen Baum zeigen. Es gilt
s(u) > s(v) und f (u) > f (v) .
4. Querkanten. Alle u
¨brigen Kanten. Diese k¨onnen zwischen verschiedenen B¨aumen des
Tiefensuchwaldes verlaufen, oder im gleichen Baum zwischen Knoten, die unvergleichbar sind bez¨
uglich der Erreichbarkeitsrelation im Tiefensuchwald. Es gilt
s(u) < s(v) und f (u) < f (v) .
Wir bemerken, dass der Graph mit Knotenmenge V und genau den Baumkanten einen
Wald bildet, den Tiefensuchwald. Auch dieser Wald ist selbstverst¨andlich im allgemeinen
nicht eindeutig, sondern h¨
angt vom Verlauf der Tiefensuche ab.
Mit Hilfe dieser Information k¨onnen wir zum Beispiel einfach feststellen, ob ein gegebener Graph einen Kreis enth¨
alt oder kreisfrei ist: ein Graph hat genau dann einen Kreis,
wenn er eine R¨
uckw¨
artskante enth¨
alt.
1.2
Starke Zusammenhangskomponenten
Sei (V, E) ein gerichteter Graph. Wir definieren x ∼ y falls es in (V, E) einen gerichteten
Pfad von x nach y und einen von y nach x gibt. In der obigen Schreibweise gilt also x y
¨
und y x. Die Relation ∼ ist eine Aquivalenzrelation
auf V (siehe Abschnitt ??).
Definition 2. Sei G ein gerichteter Graph. Eine starke Zusammenhangskomponente (SZ¨
Komponente) von G ist eine Aquivalenzklassen
der oben definierten Relation ∼. Der Graph
¨
heißt stark zusammenh¨
angend, wenn ∼ nur eine Aquivalenzklasse
hat.
Das bedeutet, G ist genau dann stark zusammenh¨angend, wenn es f¨
ur alle a, b ∈ V
einen gerichteten Pfad von a nach b gibt. Entsprechend sind die SZ-Komponenten eines
Graphen genau die maximalen stark zusammenh¨angenden Subgraphen von G. Ein paar
einfache Beobachtungen.
• Wenn G = (V, E) ein gerichteter Graph ist, dann hat der invertierte Graph
G−1 := (V, {(v, u) | (u, v) ∈ E})
die gleichen SZ-Komponenten wie G.
4
Abbildung 2: Illustration einer vollst¨andigen Tiefensuche und der verschiedenen Kantentypen.
• Jede SZ-Komponente muss enthalten sein in nur einem Baum der Tiefensuche im
Tiefensuchwald (denn Kanten aus E, die zwischen verschiedenen B¨aumen im Tiefensuchwald verlaufen, gehen immer in die gleiche Richtung; siehe wieder Abbildung 2).
Wie kann man die SZ-Komponenten von G berechnen? Man w¨
unscht sich einen Algorithmus, der die Knoten so mit Zahlen beschriftet, dass zwei Knoten genau dann die gleiche
Zahl tragen, wenn sie in der gleichen SZ-Komponente sind.
Wir wollen im folgenden einen einfachen und effizienten Algorithmus angeben, der die
starken Zusammenhangskomponenten mit einer Laufzeit berechnet, die blos linear ist in
der Gr¨oße des Graphen (definiert als die Anzahl der Knoten plus die Anzahl der Kanten).
¨
Uberraschenderweise
kommen wir hierf¨
ur mit insgesamt nur zwei Tiefensuchen aus. Das
Verfahren ist in Abbildung 3 angegeben, und stammt aus [?]. Die Idee vom eleganten
Korrektheitsbeweis dagegen ist von Ingo Wegener1 .
Korrektheitsbeweis f¨
ur den Algorithmus. Es wird gezeigt, dass der Algorithmus aus Abbildung 3 genau dann zwei Knoten mit der gleichen Zahl beschriftet, wenn sie in der selben
SZ-Komponente liegen. Wir f¨
uhren dazu einen Induktionsbeweis u
¨ber die Anzahl der starken Zusammenhangskomponenten. Falls G stark zusammenh¨angend ist, dann sind alle
Knoten im gleichen Baum der zweiten Tiefensuche, und die Antwort des Algorithmus ist
korrekt.
Ansonsten betrachten wir den ersten Baum B der zweiten Tiefensuche. Die Wurzel
dieses Baumes r ist die Wurzel des letzten Baumes L der ersten Tiefensuche. Da es Pfade
gibt von r zu allen Knoten von L, liegt ein Knoten v aus L genau dann in der gleichen
SZ-Komponente wie r, wenn es einen Pfad von v zu r gibt. Dies ist genau dann der Fall,
wenn es einen Pfad von r zu v in G−1 gibt, was wiederum genau dann der Fall ist, wenn v
in B liegt. Knoten v ∈ V \ L k¨
onnen von r aus in G−1 nicht erreicht werden, und k¨onnen
auch nicht zur gleichen SZ-Komponente geh¨oren wie r.
1
Ingo Wegener; geboren am 4. Dezember 1950 in Bremen; gestorben am 26. November 2008 in Bielefeld.
5
Eingabe: G = (V, E).
0: Weise z den Wert 0 zu.
1: F¨
uhre eine vollst¨
andige Tiefensuche auf G durch.
2: Es sei v der Knoten mit der gr¨oßten Schlusszeit.
3: F¨
uhre eine Tiefensuche auf G−1 aus.
Alle Knoten, die von v aus erreichbar sind, liegen
in der gleichen SZ-Komponente wie v, und werden mit z beschriftet.
Weise z den Wert z + 1 zu.
4: Sei v derjenige in der zweiten Suche unmarkierte Knoten
mit der gr¨
oßten Schlusszeit bez¨
uglich der ersten Suche.
5: Fahre mit Schritt 3 fort.
Abbildung 3: Berechnung der starken Zusammenhangskomponenten.
Wir betrachten nun den Graphen G − B; dieser Graph eine SZ-Komponente weniger
als G. Die Knoten von B sind die Knoten, die von der ersten Tiefensuche zuletzt besucht
wurden. Also ist die Einschr¨
ankung dieser Tiefensuche auf G − B eine Tiefensuche auf
G − B. Die Ausgabe des Algorithmus stimmt daher auf den Knoten V \ B mit der Ausgabe
des Algorithmus u
uhrt wird. Nach Induktionsvorraussetzung
¨berein, der auf G − B ausgef¨
aber ist der Algorithmus korrekt auf G − B.
Die Nummerierung der Knoten, die vom Algorithmus aus Abbildung 3 f¨
ur einen gegebenen gerichteten Graphen G berechnet wird, hat eine weitere interessante Eigenschaft:
wenn die Nummer von Knoten v kleiner ist als die von Knoten u, dann kann es keinen
Pfad geben in G von v zu u. Eine solche Nummerierung nennen wir auch eine umgekehrte
topologische Ordnung.
1.3
Breitensuche
Die typische Situation, wo man Breitensuche einsetzt, und nicht Tiefensuche, ist die Suche
nach einem k¨
urzesten Pfad von einem gegebenen Knoten s zu einem gegebenen Knoten
t in einem gerichteten Graphen. Breitensuche kann auch dazu verwendet werden, um die
k¨
urzesten Kreise in einem gegebenen Graphen zu berechnen.
Man kann die Breitensuche als Ab¨anderung der Tiefensuche verstehen. Dazu kommen
wir auf ein Implementierungsdetail der Tiefensuche. Wie entscheiden wir in der Tiefensuche,
welche Kante wir als n¨
achstes betrachten wollen? Dazu kann man einen Stapel verwenden.
Immer wenn wir einen neuen Knoten v betreten, werden alle Kanten (v, u) ∈ E in beliebiger Reihenfolge auf den Stapel gelegt. Wenn wir dann entscheiden m¨
ussen, welche Kante
wir zun¨
achst betrachten wollen, nehmen wir die oberste Kante vom Stapel (also die, die
zuletzt in den Stapel eingef¨
ugt wurde). Auf diese Weise kann man das rekursive Program in
6
100
100
t
1
s
100
100
Abbildung 4: Ein kleines Transportnetzwerk.
Abbildung 1 in ein Programm mit einer einzigen Schleife verwandeln, die so oft durchlaufen
wird, bis der Stapel leer ist.
Nun zur Breitensuche. Wir ersetzen hierzu einfach den Stapel der Tiefensuche durch eine
Liste, und anstatt dass wir die oberste Kante w¨ahlen, nehmen wir die unterste (also die, die
zuerst in die Liste eingef¨
ugt wurde). Das ist der ganze Unterschied zwischen Breitensuche
und Tiefensuche.
Die Schw¨
ache der Breitensuche ist der Speicherplatzverbrauch; der linear sein kann in
der Anzahl der Kanten. Der Speicherplatzverbrauch der Tiefensuche dagegen ist linear in
der Anzahl der Knoten; da es in vielen Graphen viel weniger Knoten als Kanten gibt, ist
das sehr viel besser.
1.4
Transportnetze
Ein Transportnetz (oft auch Netzwerk ) (V, E, s, t, w) ein ein gerichteter Graph (V, E), in
dem es genau eine Quelle gibt, n¨
amlich s, und genau eine Senke, n¨amlich t, zusammen mit
einer positiven Gewichtsfunktion
w : E → R≥0 .
Statt vom ‘Gewicht’ spricht man bei Transportnetzen gern von der Kapazit¨
at einer Kante.
Definition 3 (Fl¨
usse). Ein Fluss in einem Transportnetz (V, E, s, t, w) ist eine nichtnegative Kantenbewertung
f : E → R≥0
mit der Eigenschaft, dass f¨
ur alle Knoten v ∈ V \ {s, t} die folgende Gleichung gilt:
X
X
f (u, v) =
f (v, u)
(Was in v reinfließt, fließt auch wieder hinraus.)
(u,v)∈E
(v,u)∈E
Ein Fluss heißt zul¨
assig, wenn f (v, w) ≤ f (v, u) f¨
ur alle (v, u) ∈ E gilt. Wenn f ein
Fluss ist, und U eine Teilmenge von V \ {s, t}, dann sieht man durch Aufsummieren u
¨ber
7
die Elemente in U , dass gelten muss
X
f (u, v) =
X
f (v, u) .
(v,u)∈E,v∈U,u∈U
/
(u,v)∈E,u∈U,v∈U
/
Wenn man U = V \ {s, t} w¨
ahlt, erhalt man daraus insbesondere, dass was aus der Quelle
herausfließt, in die Senke hineinfließen muss:
X
X
f (u, t) .
f (s, u) =
(u,t)∈E
(s,u)∈E
Man gibt diesem Betrag die Abk¨
urzung ||f || und nennt ||f || die St¨
arke des Flusses f .
Partitioniert man die Knotenmenge V in beliebiger Weise in zwei Mengen M, N , von denen
die eine die Quelle und die andere die Senke enth¨alt, also
V = M ∪ N,
M ∩ N = ∅,
dann erh¨
alt man die Flussst¨
arke auch wie folgt:
X
||f || =
f (v, u) −
(v,u)∈E,v∈M,u∈N
s ∈ M, t ∈ N
X
f (u, v)
(1)
(u,v)∈E,v∈M,u∈N
In Worten: was von M nach N fließt und nicht zur¨
uck, ist genau so viel, wie von der Quelle
zur Senke fließt.
Min-Cut Max-Flow
Definition 4 (Schnitte). Ein Schnitt in einem Netzwerk ist eine Menge S ⊆ E mit der
Eigenschaft, dass es im gerichteten Graphen (V, E \ S) keinen gerichteten Weg von s nach
t gibt.
Anders formuliert ist ein Schnitt eine Kantenmenge, die aus jedem gerichteten Weg von
der Quelle zur Senke mindestens eine Kante enth¨alt. Die Kapazit¨
at eines Schnittes S ist
definiert als
X
w(S) :=
w(e) .
e∈S
Lemma 5. Ist S ein Schnitt des endlichen Transportnetzwerks (V, E, s, t, w) und f ein
zul¨
assiger Fluss, dann gilt ||f || ≤ w(S).
Satz 6 (Ford2 und Fulkerson3 ; Max Flow = Min Cut). Es sei (V, E, s, t, w) ein endliches
Transportnetz. Dann gilt
max
f zul¨
assiger Fluss
||f || =
2
min w(S)
S Schnitt
Lester Randolph Ford junior; geboren am 23. September 1927 in Houston.
Delbert Ray Fulkerson; geboren am 14. August 1924 in Tamms, Illinois. Gestorben am 10. Januar 1976
in Ithaca, New York.
3
8
In Worten: der gr¨
oßte zul¨
assige Fluss ist genau so groß wie die Kapazit¨
at des kleinsten
Schnitts.
Zum Beweis dieses Satzes stellen wir eine Methode vor, die ebenfalls nach Ford und
Fulkerson benannt ist, und die zu einem gegebenen Netzwerk einen zul¨assigen Fluss f und
einen Schnitt S der Kapazit¨
at w(S) = ||f || konstruiert. Nach dem Hilfssatz muss dieser
Fluss maximal stark und der Schnitt von minimaler Kapazit¨at sein. Der Satz ist damit also
bewiesen.
Flussverbesserung
Unser Algorithmus leistet bei einem Durchlauf folgendes: ausgehend von einem zul¨assigen
Fluss im gegebenen Netzwerk konstruiert der Algorithmus einen st¨arkeren zul¨assigen Fluss,
oder einen Schnitt, dessen Kapazit¨at gleich der St¨arke des gegebenen Flusses ist. Sind
die auftretenden Gewichte und Flussst¨arken ganzzahlig, dann ist auch die Verbesserung
ganzzahlig. Damit kann man zeigen, dass der Algorithmus irgendwann (nach endlich vielen
Durchl¨
aufen) den Fluss nicht mehr verbessern kann und deshalb einen minimalen Schnitt
gefunden haben muss.
Dazu werden die Knoten des Netzwerks, ausgehend von der Quelle, nach bestimmten
Regeln nacheinander markiert. Erreicht man dabei die Senke, kann der vorliegende Fluss
verbessert werden, wenn nicht, wird der gesuchte Schnitt gefunden. Eine Marke ist ein
Paar, in dem eine anliegende Kante notiert ist, sowie die m¨ogliche Flussverbesserung. Zu
Beginn, bei der Quelle, gibt es allerdings keinen Vorg¨angerknoten, und die Verbesserung
ist noch potentiell unbegrenzt.
Gegeben sei nun also ein endliches Transportnetz (V, E, s, t, w).
1. Markiere die Quelle q mit der Marke (−, ∞).
2. Sobald die Senke s markiert wurde, stoppe. Solange die Senke nicht markiert ist,
wiederhole die Schritte (3) und (4), bis weder (3) noch (4) zu einer weiteren Marke
f¨
uhren.
3. Falls es eine Kante (a, b) ∈ E gibt, so dass a die Marke (x, δ) tr¨agt, b unmarkiert ist,
und w(a, b)−f (a, b) > 0 ist, markiere b mit der Marke ((a, b), min(δ, w(a, b)−f (a, b)).
4. Falls es eine Kante (a, b) ∈ E gibt, so dass b die Marke (b0 , δ) tr¨agt, a unmarkiert ist,
und f (a, b) > 0 ist, markiere a mit der Marke ((a, b), min(δ, f (a, b)).
Die Idee von Schritt (4) ist, dass wir auch untersuchen m¨
ussen, ob es Kanten gibt,
bei denen der Fluss ‘in die falsche Richtung’ fließt, das heißt, von einem nicht markierten
Knoten zu einem markierten. In solchen F¨allen wird ein solcher R¨
uckfluss verringert.
Dazu betrachten wir das Beispiel in Abbildung 5. Dort finden wir ein kleines Netzwerk,
mit einem Fluss der St¨
arke 1 in rot eingezeichnet. Es gibt keinen Pfad, der entlang von
9
u
1
1
11 1
t
s
1
1
1
v
Abbildung 5: Ein Beispiel zur Frage: Warum durchlaufen wir Kanten bei der Suche nach
einer Flussverbesserung manchmal r¨
uckw¨arts?
Kanten u
uhrt. Aber trotzdem
¨ber nicht voll ausgelastete Kanten von der Quelle zur Senke f¨
ist der Fluss nicht maximal, denn wenn man den Fluss u
¨ber die Kante (u, v) um 1 verringert,
kann man ihn auf den Kanten (s, u) und (v, t) um 1 vergr¨oßern.
Falls der Markierungsalgorithmus die Senke erreicht. Falls bei der Ausf¨
uhrung des
Markierungsalgorithmus ein Knoten v markiert wird, so gibt es eine Folge s = v0 , v1 , . . . , vr =
v mit der Eigenschaft, dass f¨
ur all i ∈ {0, . . . , r−1} einer der beiden Folgenden F¨alle eintritt:
• vi+1 ist mit ((vi , vi+1 ), δ(vi+1 )) markiert und der Fluss durch die Kante (vi , vi+1 ) ist
um mindestens δ(v) kleiner als die Kapazit¨at dieser Kante, oder
• vi+1 ist mit ((vi+1 , vi ), δ(vi+1 )) markiert und der Fluss durch die Kante (vi+1 , vi ) ist
mindestens δ(v).
Eine solche Folge nennen wir augmentierenden Pfad der St¨arke δ(v). (Dass wir den gleichen
Ausdruck bereits im Zusammenhang von Paarungen verwendet haben, ist Absicht; der
Zusammenhang wird in Abschnitt 1.6 besprochen.)
Um diese Folge zu finden, durchl¨auft man die Kante (vr−1 , vr ) der Markierung von
t = vr . Der Knoten vr−1 muss wieder markiert sein, und wir durchlaufen wieder die Kante,
die in der Markierung von vr−1 abgespeichert ist (diese Kante wird vorw¨arts oder r¨
uckw¨arts
durchlaufen). Wir fahren so fort, bis wir irgendwann die Quelle s erreichen, und haben
somit den gew¨
unschten Pfad gefunden. Die Eigenschaften, die wir oben f¨
ur δ bez¨
uglich des
Flusses und der Kapazit¨
aten formuliert haben, beweist man per Induktion u
¨ber die Anzahl
der Schritte im Algorithmus.
Falls der Markierungsalgorithmus die Senke nicht erreicht. Wenn der Markierungsalgorithmus die Senke nicht erreicht, dann beginnt jeder gerichtete Weg von der Quelle
zur Senke mit einem markierten Knoten (n¨amlich q) und endet mit einem unmarkierten
10
(n¨amlich s). Deshalb enth¨
alt jeder solche Weg eine Kante, die von einem markierten Knoten
zu einem unmarkierten f¨
uhrt.
Sei nun M die Menge der markierten Knoten, und N die Menge der nicht markierten.
Dann ist nach obiger Beobachtung die Menge S := E ∩ (M × N ) ein Schnitt. Ist (v, w)
eine Kante aus S, dann muss, weil Schritt (3) des Markierungsalgorithmus nicht ausgef¨
uhrt
werden konnte, w(v, w) = f (v, w) gelten. Daraus erhalten wir
X
f (v, w) .
(2)
w(S) =
(u,w)∈S
Der Schnitt S ist also ‘voll ausgelastet’.
Aber Vorsicht: Das bedeutet nicht zwingend, dass der betrachtete Fluss bereits maximal
ist! Wir verweisen dazu wieder auf das Beispiel in Abbildung 5. Hier gibt es einen voll ausgelasteten Schnitt der Kapazit¨
at 2, n¨amlich {(u, t), (s, v)}, obwohl der in rot eingezeichnete
Fluss nicht maximal ist.
Die Kanten, die von Knoten aus N zu Knoten auf M f¨
uhren, werden vom Markierungsalgorithmus in Schritt (4) angesprochen. Der Algorithmus stoppt nur, wenn all diese
Kanten den Fluss f (u, w) = 0 haben. Also
X
0=
f (v, w) .
(3)
(w,v)∈E,v∈M,w∈N
Nun k¨
onnen wir die Gr¨
oße des Flusses berechnen.
X
X
||f || =
f (v, w) −
f (w, v)
(v,w)∈E,v∈M,w∈N
(Gleichung (1))
(w,v)∈E,v∈M,w∈N
= w(S) − 0
(Gleichungen (2), (3))
Wenn die Kapazit¨
aten alle ganzzahlig sind, so ist die berechnete Flussverbesserung
im Markierungsalgeborithmus auch ganzzahlig. Der Algorithmus terminiert also nach einer endlichen Anzahl von Schritten. Damit haben wir gezeigt, dass die Kapazit¨at von S
gleich der St¨
arke von f ist; also ist f gr¨oßtm¨oglich und Satz 6 bewiesen. Eine ausf¨
uhrliche
Darstellung der Thematik findet sich zum Beispiel in [?].
Allerdings ist dieses Verfahren zur Berechnung eines st¨arksten Flusses ist nicht effizient.
Das sieht man bereits am Beispiel aus Abbildung 4: denn wenn wir Pech haben, erhalten wir
in jeder Runde mit dem Markierungsalgorithmus eine Ver¨anderung des Flusses der mittleren Kante, mit δ(t) = 1. In dem Fall ben¨otigen wir zur Berechnung des gr¨oßtm¨oglichen
Flusses 200 Durchl¨
aufe des Markierungsalgorithmus. Und wenn die Kapazit¨aten irrational
sein d¨
urfen, so kann es sogar passieren, dass das Verfahren u
¨berhaupt nicht terminiert!
Oder dass es gegen einen Fluss konvergiert, dessen St¨arke gar nicht maximal ist.
11
1.5
Algorithmus von Edmonds-Karp
Die Idee, um aus der Methode von Ford-Fulkerson einen effizienten Algorithmus zu gewinnen, besteht darin, den Fluss stets entlang von k¨
urzesten augmentierenden Pfaden zu
verbessern. Die L¨
ange eines Pfades ist hier die Anzahl der Kanten auf dem Pfad – wir
beachten also die Gewichte der Kanten hierbei nicht.
Der Algorithmus wurde (in einer schnelleren Variante) zuerst von Dinitz4 publiziert,
blieb aber im Westen unbekannt, bis ihn Edmonds5 und Karp6 1972 wiederentdeckten, in
der Variante, die wir hier vorstellen.
Definition 7. Sei (V, E, s, t, w) ein Transportnetzwerk, und f ein zul¨
assiger Fluss. Der
Residualgraph Gf ist der gerichtete Graph mit Knotenmenge V und den nicht voll ausgelasteten Kanten in E, den Vorw¨artskanten, erg¨
anzt um R¨
uckkanten, das sind Kanten
(v, u) so dass (u, v) ∈ E und f (e) > 0.
Bei der Methode von Ford-Fulkerson berechnen wir eine Flussverbesserung, indem wir
einen gerichteten Pfad von s nach t in Gf berechnen. Im Algorithmus von EdmondsKarp w¨
ahlen wir hier einen k¨
urzesten Pfad; einen solchen k¨onnen wir mit Breitensuche
(Abschnitt 1.3) berechnen.
F¨
ur u, v ∈ V schreiben wir distf (u, v) f¨
ur die L¨ange (wir z¨ahlen die Anzahl der Kanten)
des k¨
urzesten Pfades von u nach v in Gf .
Lemma 8. Sei (V, E, s, t, w) ein Transportnetzwerk, f ein zul¨
assiger Fluss, und f 0 ein
Fluss nach einer Flussverbesserung im Algorithmus von Edmonds Karp. Dann gilt f¨
ur alle
v ∈ V \ {s, t} dass distf 0 (s, v) ≥ distf (s, v).
Beweis. Angenommen, es g¨
abe einen Knoten v ∈ V \ {s, t} mit distf 0 (s, v) < distf (s, v).
Wir w¨ahlen v aus allen Knoten mit dieser Eigenschaft so, dass distf 0 (s, v) minimal ist.
Betrachte einen k¨
urzesten Pfad p0 von s zu v in Gf 0 , und es sei (u, v) die letzte Kante auf
diesem Pfad. Dann gilt distf 0 (s, v) = distf 0 (s, u) + 1 da p0 k¨
urzest m¨oglich. Wegen der Wahl
von v gilt allerdings dass distf 0 (s, u) ≥ distf (s, u). Daher kann (u, v) keine Vorw¨artskante
in Gf gewesen sein, denn ansonsten w¨are
distf (s, v) ≤ distf (s, u) + 1
≤ distf 0 (s, u) + 1
= distf (s, v)
im Widerspruch zur Annahme. Also muss der augmentierende Pfad p in Gf , der verwendet
wurde, um den Fluss f 0 zu bilden, die Kante (u, v) als R¨
uckw¨artskante enthalten. Dann
4
Yefim A. Dinitz.
Jack R. Edmonds; geboren am 5. April 1934.
6
Richard Manning Karp; geboren am 3. Januar 1935 in Boston.
5
12
aber gilt
distf (s, v) = distf (s, u) − 1
≤ distf 0 (s, u) − 1
= distf (s, v) − 2
< distf 0 (s, v)
ebenfalls im Widerspruch zur Annahme.
Proposition 9. Der Algorithmus von Edmonds-Karp f¨
uhrt auf einem Transportnetzwerk
(V, E, s, t, w) h¨
ochstens |V | · |E| viele Flussverbesserungen durch.
Beweis. Es sei f ein Fluss und p ein augmentierender Pfad der St¨arke δ. Eine Kante (u, v) in
einem Residualnetzwerk Gf heißt kritisch auf p falls entweder (u, v) eine Vorw¨artskante in
Gf ist und c(u, v) = f (u, v)+δ gilt, oder (u, v) eine R¨
uckw¨artskante in Gf ist, und f (v, u) =
δ gilt. Das bedeutet, dass nach der Flussverbesserung die Kante (u, v) verschwindet. Auf
jedem augmentierenden Pfad ist mindestens eine Kante kritisch.
Wir betrachten nun (u, v) ∈ E, und fragen uns, wie oft (u, v) w¨ahrend der Ausf¨
uhrung
des Algorithmus kritisch sein kann. Wenn (u, v) zum ersten Mal kritisch wird, haben wir
distf (s, v) = distf (s, u) + 1, da wir bei Edmonds-Karp einen k¨
urzesten augmentierenden
Pfad w¨ahlen. Die Kante (u, v) verschwindet dann im Residualnetzwerk, und kann nur dann
wieder auftauchen, falls die Kante (v, u) als R¨
uckw¨artskante in einem augmentierenden
Pfad ausgew¨
ahlt wird. Es sei f 0 der Fluss, den wir mit diesem augmentierenden Pfad
berechnen. Dann haben wir
distf 0 (s, u) = distf 0 (s, v) + 1
≥ distf (s, v) + 1
(Lemma 8)
= distf (s, u) + 2
Da distf 0 (s, u) h¨
ochstens |V | betragen kann, kann diese Situation h¨ochstens |V | mal eintreten. Daher kann (u, v) h¨
ochstens |V | mal kritisch werden. Da es h¨ochstens |E| Kanten
gibt, werden maximal |E||V | Flussverbesserungen durchgef¨
uhrt.
Jede Iteration der Methode von Ford-Fulkerson kann mit Hilfe von Breitensuche so
implementiert werden, dass die Laufzeit linear ist in der Anzahl der Kanten. Die gesamte
Laufzeit des Algorithmus von Edmonds-Karp ist dann also linear in |V | · |E|2 .
1.6
Nochmal Paarungen
Viele Argumente im Kapitel zu Fl¨
ussen f¨
uhlen sich ¨ahlich an wie Argumente, die wir
beim Studium von Paarungen kennengelernt haben. Das ist kein Zufall. Es gibt hier viele
Querbez¨
uge. Den Satz von K¨
onig (Satz ??) beispielsweise kann man mit dem Min-Cut
Max-Flow Satz beweisen.
13
Der Satz von K¨
onig besagt, dass in einem bipartiten Graphen G die Gr¨oße einer
gr¨oßtm¨
oglichen Paarung gleich der Gr¨oße einer kleinstm¨oglichen Kanten¨
uberdeckung von
G ist.
¨
Ubersetzung
in ein Flussproblem. Man verwandelt den gegebenen bipartiten Graphen G in ein Transportnetz. Zun¨achst werden die Kanten orientiert: wenn A, B eine
Bipartition von G ist, dann werden Kanten {u, v} mit u ∈ A und v ∈ B zu gerichteten
Kanten (u, v). Diese Kanten erhalten die Kapazit¨at |V | + 1. Dann f¨
ugt man eine Quelle s
und eine Senke t hinzu, und verbindet s u
¨ber eine gerichtete Kante mit Kapazit¨at 1 mit
allen Knoten in A, und alle Knoten in B u
¨ber eine gerichtete Kante mit t. Wir bezeichnen
das resultierende Transportnetzwerk mit (V, E, s, t, w).
Von Flu
¨ ssen zu Paarungen und Andersrum. Wir berechnen nun mit dem Verfahren aus Abschnitt 1.4 einen gr¨
oßtm¨oglichen Fluss im oben beschriebenen Transportnetzwerk. Weil der Markierungsalgorithmus bei ganzzahligen Kapazit¨aten auch ganzzahlige
Fl¨
usse liefert, so fließt zu jedem Knoten aus A entweder ein Fluss der St¨arke eins oder
null. Entsprechend kann auch zu jedem Knoten aus B nur ein Fluss der St¨arke eins oder
null, und die Kanten (u, v) zwischen A und B mit f (u, v) = 1 teilen sich keine Knoten.
Also ist die entsprechende Menge an Kanten {u, v} in G eine Paarung in G. Die Anzahl
der Kanten in diesem Matching ist gleich der St¨arke des Flusses. Umgekehrt erh¨alt man
aus jedem Matching einen Fluss der entsprechenden St¨arke. Wir k¨onnen also insbesondere Algorithmen zur Berechnung von st¨arsten Fl¨
ussen zur Berechnung von gr¨oßtm¨oglichen
Paarungen verwenden.
Von Schnitten zu Knotenu
¨ berdeckungen und Andersrum. Alle Knoten der
Gestalt (s, u) mit u ∈ A bilden einen Schnitt S in (V, E, s, t, w); also gilt |S| ≤ |V |. Daraus
folgt, dass jeder Schnitt minimaler Kapazit¨at keine Kante von A nach B verwenden darf,
denn jede solche Kante hat die Kapazit¨at |V | + 1. Ein minimaler Schnitt besteht also nur
aus Kanten, die in der Quelle starten oder in der Senke enden. Setze f¨
ur eine Menge C von
solchen Kanten
X := {v ∈ V | (s, v) ∈ C}
Y := {u ∈ U | (u, t) ∈ C} .
Dann ist C genau dann ein Schnitt in (V, E, s, t, w), wenn es keine Kante von X nach Y
¨
gibt, also wenn X ∪ Y eine Knoten¨
uberdeckung von G ist. Die Gr¨oße dieser Uberdeckung
¨
ist gleich der Kapazit¨
at des Schnittes. Also ist die Gr¨oße der kleinsten Uberdeckung
von
G gleich der Gr¨
oße eines minimalen Schnittes in (V, E, s, t, w).
Wegen dem Max-Cut Min-Flow Satzes ist die Gr¨oße des kleinsten Schnittes gleich der
Gr¨oße des gr¨
oßtm¨
oglichen Flusses, und die wiederum, wie wir oben gesehen haben, gleich
der gr¨oßtm¨
oglichen Paarung in G. Wir haben also den Satz von K¨onig (ein weiteres Mal)
bewiesen.
14
Autor
Document
Kategorie
Uncategorized
Seitenansichten
14
Dateigröße
293 KB
Tags
1/--Seiten
melden