39
Flussprobleme in Flussprobleme in Graphen Graphen und ihre Anwendung auf und ihre Anwendung auf 0/1-Netzwerke 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

Embed Size (px)

Citation preview

Page 1: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

Flussprobleme in Flussprobleme in GraphenGraphen

und ihre Anwendung auf und ihre Anwendung auf 0/1-Netzwerke0/1-Netzwerke

Informatikseminar WS04/05Claudia Padberg WI4409

Page 2: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

22

Flüsse in NetzwerkenFlüsse in Netzwerken

Transport von Datenmengen durch ein Netzwerk

Netzwerke besitzen obere Kapazitätsbeschränkungen

Suche nach Verfahren zur Bestimmung maximaler Flüsse

Page 3: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

33

ÜbersichtÜbersicht

Theoretische Grundlagen Satz von Ford und Fulkerson Bestimmung von

Erweiterungswegen Algorithmus von Edmonds und Karp Algorithmus von Dinic 0-1-Netzwerke

Page 4: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

44

ÜbersichtÜbersicht

Theoretische Grundlagen q-s-Netzwerk q-s-Fluss Wert eines Flusses q-s-Schnitt Erweiterungswege

Satz von Ford und Fulkerson Bestimmung von Erweiterungswegen Algorithmus von Edmonds und Karp Algorithmus von Dinic 0-1-Netzwerke

Page 5: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

55

Theoretische Theoretische GrundlagenGrundlagen q-s-Netzwerk

kantenbewerteter, gerichteter Graph mit ausgezeichneten Ecken q und sN = (G, q, s, c)mit G = (E, K ) E = {e1...en} Eckenmenge

K = {k1...km}Kantenmenge

c (e) = Kapazität c der Kante e q = Quelle s = Senke

Page 6: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

66

Theoretische Theoretische GrundlagenGrundlagen q-s-Netzwerk

q

64

s

321

5

40

37

30

50

10

54

20 32

17

22

Page 7: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

77

Theoretische Theoretische GrundlagenGrundlagen q-s-Fluss

Funktion f, die jeder Kante k des Netzwerkes eine nichtnegative, reelle Zahl zuordnet

Bedingungen Der Fluss entspricht maximal der Kapazität

der Kante Der Fluss in eine Ecke e ist gleich dem

Fluss aus dieser Ecke

Page 8: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

88

Theoretische Theoretische GrundlagenGrundlagen q-s-Fluss

q

64

s

321

5

30/40

20/37

30/30

0/50

10/10

0/54

0/20 20/32

0/17

10/22

Page 9: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

99

Theoretische Theoretische GrundlagenGrundlagen Wert eines Flusses |f |

Summe aller Flüsse aus der Quelle Summe aller Flüsse in die Senke→ Was aus der Quelle hinaus fließt, fließt in

die Senke hinein

EqikEiqk

kfkff),(),(

)()(

Page 10: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1010

Theoretische Theoretische GrundlagenGrundlagen Wert eines Flusses |f |

q

64

s

321

5

30/40

20/37

30/30

0/50

10/10

0/54

0/20 20/32

0/17

10/22

|f |= 30

Page 11: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1111

Theoretische Theoretische GrundlagenGrundlagen q-s-Schnitt von G

Eine Partition von E in die Mengen X und X, so dass q ε X und s ε X

XjXiEjik

kcXXC

,),(

)(),(

XjXiEjik

kfXXf

,),(

)(),(

Page 12: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1212

Theoretische Theoretische GrundlagenGrundlagen q-s-Schnitt von G

q

64

s

321

5

30/40

20/37

30/30

0/50

10/10

0/54

0/20 20/32

0/17

10/22

C(X, X)= 101 f(X, X)= 30

X={q,1,2,4}

X={3,5,6,s}

Page 13: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1313

Theoretische Theoretische GrundlagenGrundlagen Erweiterungsweg EW

Weg auf dem zu G entsprechenden ungerichteten Graphen Gu, über den ein neuer Fluss mit höherem Wert erzeugt werden kann

Bedingungen bei Vorwärtskanten ist f(k) < c(k) bei Rückwärtskanten ist f(k) > 0

Page 14: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1414

Theoretische Theoretische GrundlagenGrundlagen Erweiterungsweg EW

q

64

s

321

5

30/40

20/37

30/30

0/50

10/10

0/54

0/20 20/32

0/17

10/22

Page 15: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1515

Theoretische Theoretische GrundlagenGrundlagen „engste Stelle“ f∆ des Erweiterungsweges

finden durch fv = min {c(k) – f(k) | k ist VWK des EW}

fr = min {f(k) | k ist RWK des EW}

gibt es keine RWK im EW, setzt manfr = ∞

f∆ = min {fv , fr} Fluss auf VWK um f∆ erhöhen Fluss auf RWK um f∆ senken

Page 16: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1616

Theoretische Theoretische GrundlagenGrundlagen Erweiterungsweg EW

q

64

s

321

5

30/40

20/37

30/30

0/50

10/10

0/54

0/20 20/32

0/17

10/22

fv = 12 fr = 10 f∆= 10

10/20

10/54

10/50

0/10

30/37

30/32

Page 17: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1717

ÜbersichtÜbersicht

Theoretische Grundlagen Satz von Ford und Fulkerson Bestimmung von

Erweiterungswegen Algorithmus von Edmonds und Karp Algorithmus von Dinic 0-1-Netzwerke

Page 18: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1818

Der Satz von Der Satz von Ford und FulkersonFord und Fulkerson Satz

a) Es sei f ein Fluss eines Netzwerkes. Genau dann ist f ein maximaler Fluss, wenn es keinen Erweiterungsweg bezüglich f gibt.

b) Der Wert des maximalen Flusses in einem Netzwerk ist gleich der minimalen Kapazität eines Schnittes

Page 19: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

1919

ÜbersichtÜbersicht

Theoretische Grundlagen Satz von Ford und Fulkerson Bestimmung von

Erweiterungswegen Konstruktion eines Erweiterungsweges Beispiel

Algorithmus von Edmonds und Karp Algorithmus von Dinic 0-1-Netzwerke

Page 20: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2020

Bestimmung von Bestimmung von ErweiterungswegenErweiterungswegen Aus dem Netzwerk G wird ein Restnetzwerk

Gf konstruiert.

Gf besitzt die gleiche Eckenmenge wie G und folgende Kanten: k, falls f(k) < c(k),

mit der Bewertung c(k) – f(k) ¬k, falls f(k) > 0,

mit der Bewertung f(k)

Page 21: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2121

Bestimmung von Bestimmung von ErweiterungswegenErweiterungswegen

q

64

s

321

5

30/40

20/37

30/30

0/50

10/10

0/54

0/20 20/32

0/17

10/22G

Gf

q

64

s

321

5

30

20

30

50

10

5420

20

10

17

10

17

12

12

Bestimmung von EW mit minimaler Anzahl von Kanten mit Hilfe der Breitensuche auf Gf mit Startecke q

EW gefunden, sobald s erreicht wurde

Endet die Breitensuche, bevor s erreicht ist, so ist der Fluss bereits maximal

Page 22: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2222

ÜbersichtÜbersicht

Theoretische Grundlagen Satz von Ford und Fulkerson Bestimmung von Erweiterungswegen Algorithmus von Edmonds und Karp

Vorgehensweise Beispiel

Algorithmus von Dinic 0-1-Netzwerke

Page 23: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2323

Der Algorithmus vonDer Algorithmus vonEdmonds und KarpEdmonds und Karp Vorgehensweise

Konstruiere für den Graphen G mit Fluss f den entsprechenden Restgraph Gf

Finde auf Gf mit Hilfe der Breitensuche einen Erweiterungsweg

Erhöhe den Fluss um f∆ auf dem EW Wiederhole solange, bis es keinen

Erweiterungsweg mehr von q nach s gibt, und damit der maximale Fluss gefunden ist

Page 24: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2424

Der Algorithmus vonDer Algorithmus vonEdmonds und KarpEdmonds und Karp

q

64

s

321

5

0/40

0/37

0/30

0/50

0/10

0/54

0/20 0/32

0/17

0/22G0

q

64

s

321

5

40

37

30

50

10

54

20 32

17

22Gf0|f0 |= 0

EW = q, 1, 2, 3, s

fv = 10 ; fr = ∞ ; f∆ = 10

Page 25: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2525

Der Algorithmus vonDer Algorithmus vonEdmonds und KarpEdmonds und Karp

q

64

s

321

5

10/40

0/37

10/30

0/50

10/10

0/54

0/20 0/32

0/17

10/22

q

64

s

321

5

30

37

20

50

10

54

20 32

17

10|f1 |= 10

EW = q, 1, 2, 6, s

fv = 20 ; fr = ∞ ; f∆ = 20

G1

Gf1

10

10

12

Page 26: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2626

Der Algorithmus vonDer Algorithmus vonEdmonds und KarpEdmonds und Karp

q

64

s

321

5

30/40

20/37

30/30

0/50

10/10

0/54

0/20 20/32

0/17

10/22

q

64

s

321

5

10

17

50

10

54

2012

17

10|f2 |= 30

EW = q, 4, 5, 3, s

fv = 12 ; fr = ∞ ; f∆ = 12

G2

Gf2

30

30

12

20

20

Page 27: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2727

Der Algorithmus vonDer Algorithmus vonEdmonds und KarpEdmonds und Karp

q

64

s

321

5

30/40

20/37

30/30

12/50

10/10

12/54

12/20 20/32

0/17

22/22

q

64

s

321

5

10

1742

10

12

812

17

22

|f3 |= 42

EW = q , 4, 5, 3, 2, 6, s

fv = 8 ; fr = 10 ; f∆ = 8

G3

Gf3

30

30

12 20

2038

12

Page 28: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2828

Der Algorithmus vonDer Algorithmus vonEdmonds und KarpEdmonds und Karp

q

64

s

321

5

30/40

28/37

30/30

20/50

2/10

20/54

20/20 28/32

0/17

22/22

q

64

s

321

5

10

934

2

20

204

17

22

|f4 |= 50

Kein Erweiterungsweg

Maximaler Fluss erreicht

G4

Gf4

30

30

28

2830

20

8

Page 29: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

2929

Der Algorithmus vonDer Algorithmus vonEdmonds und KarpEdmonds und Karp

q

64

s

321

5

30/40

28/37

30/30

20/50

2/10

20/54

20/20 28/32

0/17

22/22G4

|f4 |= 50

Page 30: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3030

ÜbersichtÜbersicht

Theoretische Grundlagen Satz von Ford und Fulkerson Bestimmung von Erweiterungswegen Algorithmus von Edmonds und Karp Algorithmus von Dinic

Vorgehensweise Beispiel

0-1-Netzwerke

Page 31: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3131

Der Algorithmus von Der Algorithmus von DinicDinic Betrachtung geeigneter Hilfsnetzwerke

→ Niveaunetzwerke Konstruktion eines Flusses, der nicht

maximal sein muss, für den es aber keinen EW gibt, der nur aus VWK besteht. → blockierender Fluss

Erhöhung des Flusses auf dem gesamten Netzwerk

Page 32: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3232

Der Algorithmus von Der Algorithmus von DinicDinic Vorgehen:

Aus dem Netzwerk G wird das Restnetzwerk Gf gebildet

Aus dem Restnetzwerk Gf wird das Niveaunetzwerk Gf‘

konstruiert, wobei „überflüssige Kanten“ entfernt werden

Gf‘ enthält die Kanten k =(e,f ) von Gf , für die gilt

Niv(e)+1 = Niv(f)

In Gf‘ gilt g-(q) = g+(s) = 0

Alle möglichen Erweiterungswege werden mit der

Breitensuche auf Gf‘ bestimmt und geschichtet

Page 33: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3333

Der Algorithmus vonDer Algorithmus vonDinicDinic

q

64

s

321

5

0/40

0/37

0/30

0/50

0/10

0/54

0/20 0/32

0/17

0/22G0

q

64

s

321

5

40

37

30

50

10

54

20 32

17

22Gf0

q

64

s

321

5

10/40

20/37

10/30

12/50

10/10

12/5412/20 20/32

10/22

Gf0

‘20/4

0

20/30

12/22

Page 34: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3434

Der Algorithmus vonDer Algorithmus vonDinicDinic

q

64

s

321

5

30/40

20/37

30/30

12/50

10/10

12/54

12/20 20/32

22/22G1

q s

321

5

10

1742

10

12

812

22

Gf1

30

30

12 20

2038

12

64

q

64

s

321

5

10

17

38

10

428 12

Gf1

Page 35: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3535

Der Algorithmus vonDer Algorithmus vonDinicDinic

q

64

s

321

5

30/40

28/37

30/30

20/50

2/10

20/54

20/20 28/32

22/22G2

q

64

s

321

5

10

934

2

20

204

22

Gf2

30

30

28

2830

20

8

q

64

s

321

5

10Gf2

Page 36: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3636

Der Algorithmus vonDer Algorithmus vonDinicDinic

q

64

s

321

5

30/40

28/37

30/30

20/50

2/10

20/54

20/20 28/32

22/22G2

Im Niveaunetzwerk gibt es keinen weiteren Erweiterungsweg

Maximaler Fluss erreicht mit |f2 |= 50

Page 37: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3737

ÜbersichtÜbersicht

Theoretische Grundlagen Satz von Ford und Fulkerson Bestimmung von

Erweiterungswegen Algorithmus von Edmonds und Karp Algorithmus von Dinic 0-1-Netzwerke

Page 38: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3838

0-1-Netzwerke0-1-Netzwerke

Spezialfall von allgemeinen Netzwerken

Jede Kante besitzt die Kapazität 0 oder 1

Es existiert ein maximaler Fluss f, der auf jeder Kante den Wert 1 oder 0 hat

Es gibt |f | Wege von q nach s, welche paarweise keine Kante gemeinsam haben

→ |f | kantendisjunkte Wege

Page 39: Flussprobleme in Graphen und ihre Anwendung auf 0/1-Netzwerke Informatikseminar WS04/05 Claudia Padberg WI4409

3939

Vielen Dank für Ihre Vielen Dank für Ihre Aufmerksamkeit!Aufmerksamkeit!