Embed Size (px)
Citation preview
Entstanden im Rahmen einer Projektarbeit im FachOOP (Objekt Orientierte Programmierung)
Projektleiter: Prof. Jürgen Sauer
Projekt erstellt von:
Dietmar Drexler und Klaus Hort
Der Knoten
Knotenint nodeNameVector edgesToPoint pboolean Lboolean Sint lambdaint fatherboolean color
color wird zur Veranschaulichung im Applet verwendet:color: Knoten, der einen neuen Baum erzeugt
Name des Knotens
Vektor, in dem Kanten gespeichert sind,die auf andere Knoten zeigen
Koordinaten des Knotens
ist der Knoten in der Menge L und/oder S
Kennzeichnung des Knotens
der Vater des Knotens
Die Kante
Kanteint startWeightint endWeightboolean Aint toNodeNameboolean selectedboolean color
Kapazität
Fluß
ist die Kante in der Menge A
Name des Knotens, auf den gezeigt wird
Kapazität
Fluß
selected und color werden zur Veranschaulichungim Applet verwendet:selected: Kante wird gerade bearbeitetcolor: Kanten, die einen Durch-
bruch erzielten.
Schritt 1:Man setze für jeden Bogen xy in N f(xy) = 0.
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Fluß = 0
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 2:Man setze A` = Ø. (A`ist die Menge der Bögen in dem ungesättigten Baum.)Für die Quelle s von N setze man (s) = .Man setze L = {s}. (L ist die Menge der gekennzeichneten Knoten.)Man setze S = Ø. (S ist die Menge der Knoten in L, die überprüft worden sind.)
S0
2,3x,ytruefalse
-1-1
false
t1
x,yfalsefalse
-1-1
false
12
2,4x,y
falsefalse
-1-1
false
S->240
false3
falsefalse
S->160
false2
falsefalse
startWeightendWeight
AtoNodeName
selectedcolor
nodeNameedgesTo
pLS
lambdafathercolor
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 3:Es sei F die Menge der Bögen xy in N, so daß c(xy) > f(xy) ist.(F besteht aus Vorwärtsbögen.)Es sei R die Menge der Bögen xy in N, so daß f(xy) > 0 ist.(R setzt sich aus Rückwärtsbögen zusammen.)
Vorwärtskante
Rückwärtskante
Vorwärts- und Rückwärtskantenwerden immer aktuell bestimmt, indem man den ausgewählten Knotenals Ausgangspunkt betrachtet.
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 4:Wenn L - S = Ø gilt, gehe man zu Schritt 10.
12
3,5x,ytruetrue
3s
false
S0
2,3x,ytruetrue-1-1
false
456
x,ytruetrue
11
true
nodeNameedgesTo
pLS
lambdafathercolor
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 5:Man wähle x L - S.
S0
2,3x,ytruetrue-1-1
false
456
x,ytruefalse
31
false
nodeNameedgesTo
pLS
lambdafathercolor
567
x,yfalsefalse
0-1
false
34
2,6x,y
falsefalse
-1-1
false
12
3,4x,ytruetrue
60
true
23
4,6,7x,ytruefalse
40
false
Von Knoten 1 erreichbarer Knoten
t1
x,yfalsefalse
0-1
false
Knoten 2 wurde von s gekennzeichnet,d.h. dieser Knoten kann vonKnoten 1 nicht mehr erreicht werden
Knoten 3 kann von Knoten 1 nicht erreicht werden, dadieser nur mit einer Rückwärtskante ohne Fluß ver-bunden ist (siehe Schritt 7)
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 6:Wenn es kein y L gibt, so daß xy F ist und die Menge der Bögen A` {xy} einenunterliegenden Baum induziert, dann gehe man zu Schritt 7.Wenn es ein y nicht L gibt, so daß xy F istund die Menge der Bögen A` {xy} einenunterliegenden Baum induziert, dannkennzeichne man y mit
(y) = min{ (x), c(xy) - f(xy)}.Man ersetze A` durch A` {xy}und L durch L {y}.Nun wiederhole mandiesen Schritt.
456
x,ytruefalse
31
false
S0
2,3x,ytruetrue-1-1
false
nodeNameedgesTo
pLS
lambdafathercolor 5
67
x,ytruefalse
12
false
34
2,6x,ytruefalse
52
false
12
3,5x,ytruetrue
60
false
23
4,6,7x,ytruefalse
01
true
Von Knoten 1 erreichbarer Knoten
Von Knoten 2 erreichbare Knoten
Diese Kante erfüllt die Kriterien einer Vor-wärtskante nicht mehr.
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 7:Wenn es kein y nicht L gibt, so daß yx R ist und die Menge der Bögen A` {xy} einenunterliegenden Baum induziert, dann gehe man zu Schritt 8.Wenn es ein y nicht L gibt, so daß xy R ist und die Mengeder Bögen A` {xy} einen unterliegenden Bauminduziert, dann kennzeichne man y mit
(y) = min{ (x), f(xy)}.Man ersetze A` durch A` {xy} undL durch L {y}.Nun ist dieser Schrittzu wiederholen. Vorwärtskannte (siehe Schritt 6)
Rückwärtskante
567
x,ytruefalse
23
false
23
4,6,7x,ytruefalse
23
false
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 8:Man ersetze S durch S {x}. Wenn t L gilt, kehre man zu Schritt 4 zurück.
456
x,ytruefalse
31
false
S0
2,3x,ytruetrue-1-1
false
nodeNameedgesTo
pLS
lambdafathercolor 5
67
x,ytruefalse
12
false
34
2,6x,ytruefalse
52
false
12
3,5x,ytruetrue
60
false
23
4,6,7x,ytruetrue
01
true
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 9:(Wir erreichen diesen Schritt wenn die Quelle t gekennzeichnet wurde, d.h. wenn wir einenDurchbruch erzielt haben.)Unter Anwendung einer rückführenden Prozedur identifiziere man die zunehmende KantenfolgeW von s nach t in N, indem die Bögen von A` verwendet werden und für jedes a in W f(a) durchf( a) + (t) ersetzt wird, falls a F, bzw. durch f(a) - (t) ersetzt wird, falls a R.Man kehre nun zu Schritt 2 zurück.
t1
x,ytruefalse
25
false
S->16
1+2true
2truetrue
1->43
0+2true
5truetrue
4->52
0+2true
6truetrue
5->t5
1+2true
1truetrue
Der Algorithmus von Ford und Fulkerson
in 10 Schritten
Schritt 10:(Wir erreichen diesen Schritt, wenn alle gekennzeichneten Knoten überprüft worden sind, undes keinen Durchbruch gibt.)Der Wert f(xy) für jeden Bogen xy in N liefert einen maximalen Fluß in N, und die Menge derKnoten L ergibt einen minimalen Schnitt.
Der maximale Fluß beträgt: 7
4 + 3 = 7
