Vorlesung Algorithmen II - KIT - ITI Algorithmik I · KIT – Universitat des Landes Baden-W¨urttemberg und nationales Forschungszentrum in der Helmholtz-Gemeinschaft INSTITUT FUR¨

Algorithmen II – Wintersemester 2013/2014Institut fur Theoretische InformatikProf. Dr. Dorothea Wagner

Algorithmen IIUbung am 12.11.2013

www.kit.eduKIT – Universitat des Landes Baden-Wurttemberg undnationales Forschungszentrum in der Helmholtz-Gemeinschaft

INSTITUT FUR THEORETISCHE INFORMATIK · PROF. DR. DOROTHEA WAGNER

Flusse und Schnitte


Algorithmus von Goldberg & Tarjan


Ein Beispiel

s t Namedist

Uberschuss e

Fluss f / Kapazitat c

0 / 4 0 / 7

0 / 10 / 5

0 / 3 0 / 1

0 / 3

Aktiv

a

c

b


Ein Beispiel

s t Namedist

Uberschuss e


0 / 4

Fuhre Gegenkanten ein

0 / 7

0 / 10 / 5

0 / 3 0 / 1

0 / 0 0 / 0

0 / 0 0 / 0

0 / 30 / 0

Aktiv

a

c

b


Ein Beispiel

s[5]−9

t[0]0

[0]5

[0]0

[0]4

Namedist

Uberschuss e



Initialisiere dist und f

Aktiv4 / 4 0 / 7

0 / 15 / 5

0 / 3 0 / 1

0 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

a

c

b


Ein Beispiel

s[5]−9

t[0]0

[0]5

[0]0

[0]4

Namedist

Uberschuss e




Aktiv

Betrachte Residualnetzwerk

s

a

c t

b

4

35 1 3

7

1

Residualnetzwerk Df :

4 / 4 0 / 7

0 / 15 / 5

0 / 3 0 / 1

0 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

a

c

b


Ein Beispiel

s[5]−9

t[0]0

[0]5

[0]0

[0]4

Namedist

Uberschuss e




Aktiv


s

a

c t

b

4

35 1 3

7

1

Wahle aktiven Knoten und fuhre PUSH / RELABEL aus:Residualnetzwerk Df :

4 / 4 0 / 7

0 / 15 / 5

0 / 3 0 / 1

0 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

a

c

b


Ein Beispiel

s[5]−9

t[0]0

[0]5

[0]0

[0]4

Namedist

Uberschuss e




Aktiv


s

a

c t

b

4

35 1 3

7

1


Bedingungen zum Ausfuhren von RELABEL fur a:Fur alle Kanten (a, v ) in Df gilt: dist(a) ≤ dist(v )

Setze Label dist(a) auf. . .∞, falls es in Df keine Kante (a, v ) gibt.

Minimum von dist(v ) + 1 uber alle Kanten (a, v ) in Df .

4 / 4 0 / 7

0 / 15 / 5

0 / 3 0 / 1

0 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

a

c

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b

4

35 1 3

7

1


Bedingungen zum Ausfuhren von RELABEL fur a:Fur alle Kanten (a, v ) in Df gilt: dist(a) ≤ dist(v )

Setze Label dist(a) auf. . .∞, falls es in Df keine Kante (a, v ) gibt.

Minimum von dist(v ) + 1 uber alle Kanten (a, v ) in Df .

[5]−9

[0]0

[1]5

[0]0

[0]4

4 / 4 0 / 7

0 / 15 / 5

0 / 3 0 / 1

0 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

a

c

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b

4

35 1 3

7

1


[5]−9

[0]0

[1]5

[0]0

[0]4

Bedingungen zum Ausfuhren von PUSH fur a:Df enthalt Kante (a, v ) mit dist(a) = dist(v ) + 1

Erhohe Fluss auf dieser Kante (a, v ) moglichst stark.

4 / 4 0 / 7

0 / 15 / 5

0 / 3 0 / 1

0 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

a

c

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


Bedingungen zum Ausfuhren von PUSH fur a:Df enthalt Kante (a, v ) mit dist(a) = dist(v ) + 1

Erhohe Fluss auf dieser Kante (a, v ) moglichst stark.

4 / 4 0 / 7

0 / 15 / 5

3 / 3 0 / 1

−3 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

4

3

5 1 3

7

1

[5]−9

[0]0

[1]2

[0]3

[0]4

a

c

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


4 / 4 0 / 7

0 / 15 / 5

3 / 3 0 / 1

−3 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

4

3

5 1 3

7

1

[5]−9

[0]0

[1]2

[0]3

[0]4

a

c

RELABEL(a)

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


4 / 4 0 / 7

0 / 15 / 5

3 / 3 0 / 1

−3 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

4

3

5 1 3

7

1

a

c

RELABEL(a)

[5]−9

[0]0

[6]2

[0]3

[0]4

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


4 / 4 0 / 7

0 / 15 / 5

3 / 3 0 / 1

−3 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

4

3

5 1 3

7

1

a

c[5]−9

[0]0

[6]2

[0]3

[0]4

RELABEL(b)

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


4 / 4 0 / 7

0 / 15 / 5

3 / 3 0 / 1

−3 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

4

3

5 1 3

7

1

a

c

RELABEL(b)

[5]−9

[0]0

[6]2

[1]3

[0]4

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


4 / 4 0 / 7

0 / 15 / 5

3 / 3 0 / 1

−3 / 0 0 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

4

3

5 1 3

7

1

a

c[5]−9

[0]0

[6]2

[1]3

[0]4

PUSH(b, t )

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

PUSH(b, t )4

3

5 1 3

7

1

4 / 4 0 / 7

0 / 15 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

[5]−9

[0]1

[6]2

[1]2

[0]4

b


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

4

3

5 1 3

7

1

4 / 4 0 / 7

0 / 15 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 0 / 0

0 / 3−5 / 0

[5]−9

[0]1

[6]2

[1]2

[0]4

b

PUSH(b, c)


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

b

PUSH(b, c)4

3

5 3 1

7

1

4 / 4 0 / 7

−2 / 15 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 0 / 0

2 / 3−5 / 0

[5]−9

[0]1

[6]2

[1]0

[0]6


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

b

4

3

5 3 1

7

1

4 / 4 0 / 7

−2 / 15 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 0 / 0

2 / 3−5 / 0

[5]−9

[0]1

[6]2

[1]0

[0]6

PUSH(a, s)


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

b

PUSH(a, s)

4 / 4 0 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 0 / 0

2 / 3−3 / 0

4

3

3 3 1

7

1

[5]−7

[0]1

[6]0

[1]0

[0]6

2


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

b

4 / 4 0 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 0 / 0

2 / 3−3 / 0

4

3

3 3 1

7

1

[5]−7

[0]1

[6]0

[1]0

[0]6

2

RELABEL(c)


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

b

4 / 4 0 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 0 / 0

2 / 3−3 / 0

4

3

3 3 1

7

1

2

RELABEL(c)

[5]−7

[0]1

[6]0

[1]0

[1]6


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

b

4 / 4 0 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 0 / 0

2 / 3−3 / 0

4

3

3 3 1

7

1

2

[5]−7

[0]1

[6]0

[1]0

[1]6

PUSH(c, t )


Ein Beispiel

s t Namedist

Uberschuss e




Aktiv


s

a

c t

b


a

c

b

PUSH(c, t )

4 / 4 6 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 −6 / 0

2 / 3−3 / 0

4

3

3 3 1

1

1

2

[5]−7

[0]7

[6]0

[1]0

[1]0

6


Problem 1

Gegeben sei ein Flussnetzwerk zusammen mit dem Ergebnis des Push-Relabel-Algorithmus. D.h. es stehen folgende Informationen zur Verfugung:

Ein maximaler Fluss f .Residualnetzwerk zu f .Uberschusse aller Knoten.Label dist(v ) fur alle Knoten.

s t

a

c

b

4 / 4 6 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 −6 / 0

2 / 3−3 / 0

[5]−7

[0]7

[6]0

[1]0

[1]0

Gesucht: Algorithmus der einen minimalen s-t-Schnitt (S, V \ S) berechnet.

s

a

c t

b

4

3

3 3 1

1

1

2

6


Problem 1



s t

a

c

b

4 / 4 6 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 −6 / 0

2 / 3−3 / 0

[5]−7

[0]7

[6]0

[1]0

[1]0


s

a

c t

b

4

3

3 3 1

1

1

2

6

Eine Partition (S, V \ S) tut das richtige genau dann wenns ∈ S und t ∈ V \ SDas Residualnetzwerk Df enthalt keine Kante von S nach V \ S.

S V \ S


Problem 1



s t

a

c

b

4 / 4 6 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 −6 / 0

2 / 3−3 / 0

[5]−7

[0]7

[6]0

[1]0

[1]0


s

a

c t

b

4

3

3 3 1

1

1

2

6


S V \ S

Ermittle mittels Breitensuche in Df alle von s aus erreichbaren Knoten.⇒ O(|E |) Zeit.


Problem 1



s t

a

c

b

4 / 4 6 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 −6 / 0

2 / 3−3 / 0

[5]−7

[0]7

[6]0

[1]0

[1]0


s

a

c t

b

4

3

3 3 1

1

1

2

6


S V \ S

Ermittle mittels Breitensuche in Df alle von s aus erreichbaren Knoten.⇒ O(|E |) Zeit.

Hinweis: Es gibt einen Algorithmus Laufzeit O(|V |).


Problem 1



s t

a

c

b

4 / 4 6 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 −6 / 0

2 / 3−3 / 0

[5]−7

[0]7

[6]0

[1]0

[1]0


s

a

c t

b

4

3

3 3 1

1

1

2

6

S V \ S

Behauptung 1: Es gibt eine Zahl 0 < x < |V |, sodass kein Knoten x als Label hat.


Problem 1



s t

a

c

b

4 / 4 6 / 7

−2 / 13 / 5

3 / 3 1 / 1

−3 / 0 −1 / 0

−4 / 0 −6 / 0

2 / 3−3 / 0

[5]−7

[0]7

[6]0

[1]0

[1]0


s

a

c t

b

4

3

3 3 1

1

1

2

6

S V \ S


Behauptung 2: Die Partitionierung S = {v ∈ V | dist(v ) > x} und V \ S = {v ∈V | dist(v ) < x} ist ein minimaler s-t-Schnitt.


Problem 1



dist(s) = |V | und dist(t) = 0

Die restlichen |V |−2 Knoten konnen nicht alle |V |−1 moglichen x mit 0 < x <|V | abdecken.


Problem 1





Zeige: Es gibt keine Kante (u, v ) im Residualnetzwerk mit u ∈ S und v ∈ V \ S.


Problem 1






Angenommen (u, v ) ist eine solche Kante, dann gilt dist(u) ≥ dist(v ) + 2


Problem 1





Eine zulassige Markierung erfullt immer die folgende Eigenschaft: Wenn dasResidualnetzwerk die Kante (u, v ) enthalt, dann gilt dist(u) ≤ dist(v ) + 1.


Angenommen (u, v ) ist eine solche Kante, dann gilt dist(u) ≥ dist(v ) + 2


Flusse mit komplizierten Kosten


Problem 2 (a)

In der Vorlesung:konstante Kosten pro Flusseinheit

Jetzt:bel. Kostenfunktion fur jede Kante

Fluss f

cost(f )

0 1 2 3012345 e1

e2cost(e2) = 1cost(e1) = 2

Fluss f

cost(f )

0 1 2 3012345

e1

e2 coste1 (0) = 0coste1 (1) = 2coste1 (2) = 2coste1 (3) = 4

coste2 (0) = 0coste2 (1) = 1coste2 (2) = 3coste2 (3) = 5

(a) Wenn coste fur alle e ∈ E konvex ist, dann kann MINCOSTFLOW effizient gelostwerden. (unter der Voraussetzung, dass die Kapazitaten polynomiell beschrankt sind).Hinweis: Modellieren sie ein aquivalentes Flussnetzwerk mit herkommlichen Kos-ten. Sie durfen Mehrfachkanten benutzen.


Problem 2 (a)

In der Vorlesung:konstante Kosten pro Flusseinheit

Jetzt:bel. Kostenfunktion fur jede Kante

Fluss f

cost(f )

0 1 2 3012345 e1

e2cost(e2) = 1cost(e1) = 2

Fluss f

cost(f )

0 1 2 3012345

e1

e2 coste1 (0) = 0coste1 (1) = 2coste1 (2) = 2coste1 (3) = 4

coste2 (0) = 0coste2 (1) = 1coste2 (2) = 3coste2 (3) = 5

(a) Wenn coste fur alle e ∈ E konvex ist, dann kann MINCOSTFLOW effizient gelostwerden. (unter der Voraussetzung, dass die Kapazitaten polynomiell beschrankt sind).Hinweis: Modellieren sie ein aquivalentes Flussnetzwerk mit herkommlichen Kos-ten. Sie durfen Mehrfachkanten benutzen.

Fluss f

cost(f )

0 1 2 3012345

e ee1

e2

cost(e1) = 1, c(e1) = 2

cost(e2) = 2, c(e2) = 1


Problem 2 (b)

(b) Fur potentiell nicht konvexe Kostenfunktionen ist das Entscheidungsproblem vonMINCOSTFLOW NP-vollstandig.

Hinweis: 3-DIMENSIONAL-MATCHING ist NP-vollstandig.

(offensichtlich ist MINCOSTFLOW inNP)


Problem 2 (b)


3-DIMENSIONAL-MATCHING

Geg.: Endliche, disjunkte Mengen X , Y und Z mit einer Menge von Tripeln T ⊆X × Y × Z , sowie Zahl k ∈ N.Ges.: Teilmenge M ⊆ T mit |M| ≥ k , sodass jedes Element aus X , Y bzw. Z inmaximal einem Tripel in M auftaucht.




Problem 2 (b)





Beispiel:

x1

x3

x2

y1

y2y3

z1

z2

z3

(x1, y1, z1) ∈ T

(x1, y3, z3) ∈ T

(x2, y3, z2) ∈ T (x3, y2, z2) ∈ T

Fur M ausgewahlte Tripel durfensich nicht uberlappen!



Problem 2 (b)





Beispiel:

x1

x3

x2

y1

y2y3

z1

z2

z3

(x1, y1, z1) ∈ T

(x1, y3, z3) ∈ T

(x2, y3, z2) ∈ T (x3, y2, z2) ∈ T

Fur M ausgewahlte Tripel durfensich nicht uberlappen!

|M| ≥ 2 ist moglich.

|M ≥ 3 nicht.



Problem 2 (b)

x3

y2

z3

Ziel: Konstruiere eine Flussnetzwerk D, sodass ein Fluss f mit cost(f ) ≤ k existiert,genau dann wenn es ein 3DM M mit |M| ≥ k gibt.

x1

z1y1

x2y3

z2


Problem 2 (b)

x3

y2

z3


Erstelle fur jedes Element einen Knoten.

x1

x3

x2

y1

y2

y3

z1

z2

z3

x1

z1y1

x2y3

z2


Problem 2 (b)

x3

y2

z3



x1

x3

x2

y1

y2

y3

z1

z2

z3

Erstelle fur jedes Tripel (x , y , z) einen Knoten mit Kantenzu x , y und z mit Kapazitat 1 und konstanten Kosten 0.

(x1, y3, z3)

(x3, y2, z2)

x1

z1y1

x2y3

z2

(x1, y1, z1)

(x2, y3, z2)


Problem 2 (b)

x3

y2

z3



x1

x3

x2

y1

y2

y3

z1

z2

z3


(x1, y3, z3)

(x3, y2, z2)

Erstelle eine Senke t mit Bedarf 3k und Kanten von den

”Elementknoten“ mit Kapazitat 1 und konstanten Kosten 0.

t

x1

z1y1

x2y3

z2

(x1, y1, z1)

(x2, y3, z2)


Problem 2 (b)

x3

y2

z3



x1

x3

x2

y1

y2

y3

z1

z2

z3


(x1, y3, z3)

(x3, y2, z2)



t

Erstelle Quelle s mit Uberschuss 3k und Kanten zu den ”Tripelknoten“ mitKapazitaten 3 und Kosten coste(0) = 0, coste(1) = coste(2) = coste(3) = 1.

s

x1

z1y1

x2y3

z2

(x1, y1, z1)

(x2, y3, z2)


Problem 2 (b)

x3

y2

z3



x1

x3

x2

y1

y2

y3

z1

z2

z3


(x1, y3, z3)

(x3, y2, z2)



t


s

x1

z1y1

x2y3

z2

(x1, y1, z1)

(x2, y3, z2)


Problem 2 (b)

x3

y2

z3



x1

x3

x2

y1

y2

y3

z1

z2

z3


(x1, y3, z3)

(x3, y2, z2)



t


s

Nachrechnen!

x1

z1y1

x2y3

z2

(x1, y1, z1)

(x2, y3, z2)


Flusse mit Mindestfluss


Problem 3

Sei D = (V , E) ein Flussnetzwerk wobei zusatzlich auf jeder Kante ein Mindestflussgefordert ist. Das heißt, gegeben ist eine Abbildung ` : E → R+

0 und ein Flussf muss zusatzlich zur Kapazitats- und Flusserhaltungsbedingung die Ungleichung`(e) ≤ f (e) (fur alle e ∈ E) erfullen.Zeigen Sie, dass ein Flussproblem mit gefordertem Mindestfluss in ein Flusspro-blem ohne diese zusatzliche Bedingung transformiert werden kann.


Problem 3



Betrachte eine einzelne Kanten e(u, v ) mit Mindestfluss `(e) und Kapazitat c(e).

u v`(e)c(e)


Problem 3




u v`(e)

Konstruktion des Flussnetzwerks D′:Setze den Mindestfluss von e auf 0 und die Kapazitat von e auf c(e)− `(e).

die Bedarfe von u und v auf b(u) = `(e) bzw. b(v ) = −`(e)

u v0

`(e) −`(e)c(e) c(e)− `(e)


Problem 3




u v`(e)

Konstruktion des Flussnetzwerks D′:Setze den Mindestfluss von e auf 0 und die Kapazitat von e auf c(e)− `(e).

die Bedarfe von u und v auf b(u) = `(e) bzw. b(v ) = −`(e)

u v0

`(e) −`(e)c(e) c(e)− `(e)

Zeige: Gultiger Fluss f in D liefert gultigen Fluss f ′ in D′ und umgekehrt, wobeif (e) = f ′(e) + `(e).


Matchings – Erhohende Wege


Wiederholung: Motivation

FlugPilot

Pilot darf Flugzeug fliegen



FlugPilot


Zuordnung der Piloten



FlugPilot





FlugPilot



Ziel: Finde eine Zuordnung, sodass:Jeder Pilot maximal ein Flugzeug fliegt, jedes Flugzeug von maxi-mal einem Pilot geflogen wird.Moglichst viele Flugzeuge besetzt (bzw. Piloten beschaftigt) sind.



FlugPilot



Ziel: Finde eine Zuordnung, sodass:Jeder Pilot maximal ein Flugzeug fliegt, jedes Flugzeug von maxi-mal einem Pilot geflogen wird.Moglichst viele Flugzeuge besetzt (bzw. Piloten beschaftigt) sind.

maximalesMatching


Berechnung mithilfe eines Flusses

bipartiter Graph G zugehoriges Flussnetzwerk G′

s t

(Kapazitaten sind 1)




s t

mit maximalem Matching mit maximalem Fluss





s t

mit maximalem Matching mit maximalem Fluss


Der maximale Fluss kann schrittweise mithilfe von erhohenden Wegen berechnetwerden (Ford-Fulkerson-Algorithmus). In jedem dieser Schritte induziert der aktu-elle Fluss f ein (nicht notwendigerweise maximales) Matching.Erklaren Sie inwiefern dieses Matching sich im Verlauf der Berechnung von fandert. Gehen Sie hierzu insbesondere auf die Rolle der erhohenden Wege ein.

Problem 4


Problem 4



s t

Residualnetzwerk

s t


Problem 4



Residualnetzwerk

s t

s t


Problem 4



Residualnetzwerk

s t

s t


Problem 4



Residualnetzwerk

s t

s t


Problem 4



Residualnetzwerk

s t

s t


Problem 4



Residualnetzwerk

s t

s t


Problem 4



Residualnetzwerk

s t

s t


Problem 4



Residualnetzwerk

s t

s t


Problem 4



Residualnetzwerk

s t

s t


Problem 4


Problem 4

Ein erhohender Pfad im Residualnetzwerk entspricht einem Pfad Π im Graph, so-dass . . .


Problem 4


der erste und letzte Knoten in Π nicht gematched sind (d.h. sie sind zu keinerMatchingkante inzident)

und Π aus abwechselnd ungematchten und gematchten Kanten besteht.


Problem 4


der erste und letzte Knoten in Π nicht gematched sind (d.h. sie sind zu keinerMatchingkante inzident)

und Π aus abwechselnd ungematchten und gematchten Kanten besteht.

Man konnte auch iterativ nach solchen Pfaden suchen, statt nach erhohenden Pfa-den im Residualnetzwerk.


Schnitte in Graphen


Problem 5

Zwei Schnitte (S, V \S) und (T , V \T ) in einem (ungerichteten) Graphen G = (V , E)kreuzen sich, wenn keine der Mengen A = S ∩ T , B = S \ T , C = T \ S undD = V \ (S ∪ T ) leer ist. Sei c : E → R+

0 eine Kantengewichtsfunktion auf G.(a) Seien (S, V \ S) und (T , V \ T ) zwei sich kreuzende s-t-Schnitte mit s ∈ S und

t ∈ T . Zeigen Sie: Es gilt s ∈ B und t ∈ C.

S V \ S

TV \ T

A

B D

C


Problem 5




S V \ S

TV \ T

A

B D

C

s liegt in S = A ∪ B und t in T = A ∪ C⇒ Es gibt vier mogliche Kombinationen:

s ∈ A, t ∈ Cs ∈ A, t ∈ As ∈ B, t ∈ Cs ∈ B, t ∈ A


Problem 5




S V \ S

TV \ T

A

B D

C



T ist kein s-t-Schnitt

s

t


Problem 5




S V \ S

TV \ T

A

B D

C



T ist kein s-t-Schnitt

s

t

T & S keine s-t-Schnitte


Problem 5




S V \ S

TV \ T

A

B D

C



T ist kein s-t-SchnittT & S keine s-t-Schnittes

t

S ist kein s-t-Schnitt


Problem 5




S V \ S

TV \ T

A

B D

C



T ist kein s-t-SchnittT & S keine s-t-Schnitte

S ist kein s-t-Schnitt

s

t


Problem 5


0 eine Kantengewichtsfunktion auf G.(b) Seien (S, V \ S) und (T , V \ T ) zwei sich kreuzende minimale s-t-Schnitte mit

s ∈ S und t ∈ T . Zeigen Sie: (B, V \B) und (C, V \C) sind zwei kreuzungsfreieminimale s-t-Schnitte.

S V \ S

TV \ T

A

B D

C

s

t


Problem 5




S V \ S

TV \ T

A

B D

C

s

t

Offensichtlich: (B, V \ B) und (C, V \ C)sind kreuzungsfreie s-t-Schnitte.

Zeige:c(B, V \B) = c(C, V \C) = c(S, V \S) = c(T , V \T )


Problem 5




S V \ S

TV \ T

A

B D

C

s

t




Problem 5




S V \ S

TV \ T

A

B D

C

s

t



c(B, V \ B) = c(B, A) + c(B, C) + c(B, D)

c(C, V \ C) = c(C, A) + c(C, B) + c(C, D)

c(S, V \ S) = c(A, C) + c(A, D) + c(B, C) + c(B, D)

c(T , V \ T ) = c(A, B) + c(A, D) + c(C, B) + c(C, D)


Problem 5




S V \ S

TV \ T

A

B D

C

s

t



⇒ c(B, V \ B) + c(C, V \ C) ≤ c(S, V \ S) + c(T , V \ S)

c(B, V \ B) = c(B, A) + c(B, C) + c(B, D)

c(C, V \ C) = c(C, A) + c(C, B) + c(C, D)




Problem 5




S V \ S

TV \ T

A

B D

C

s

t



⇒ c(B, V \ B) + c(C, V \ C) ≤ c(S, V \ S) + c(T , V \ S)

c(B, V \ B) = c(B, A) + c(B, C) + c(B, D)

c(C, V \ C) = c(C, A) + c(C, B) + c(C, D)



⇒ c(B, V \ B) = c(C, V \ C) = c(S, V \ S) = c(T , V \ S) (da c(S, V \ S) und c(T , V \ T ) minimal)


Problem 6 – Algorithmus von Stoer & Wagner

Phase 1G1 = GS1 = {1} (Startknoten 1)

1

3

2

4

5

33

2

2

111




1

3

2

4

5

33

2

2

111S1 = {1, 2} (2 am starksten zu {1} verbunden)




1

3

2

4

5

33

2

2


S1 = {1, 2, 5}




1

3

2

4

5

33

2

2


S1 = {1, 2, 5}S1 = {1, 2, 5, 4}




1

3

2

4

5

33

2

2


S1 = {1, 2, 5}S1 = {1, 2, 5, 4}S1 = {1, 2, 5, 4, 3}

s tSchnitt der Phase: {V1 \ {3}, {3}}

→ Gewicht 4

Verschmelzen von s und t ergibt G2

1 2

5

33

3

11

3, 4



Phase 2G2 = G1 mit 3 und 4 verschmolzenS2 = {2} (Startknoten 2)

2

5

3

3

11

31

3, 4




2

5

3

3

11S2 = {2, 5}

31

3, 4




2

5

3

3

11S2 = {2, 5}

3

S2 = {2, 5, {3, 4}}

1

3, 4




2

5

3

3

11S2 = {2, 5}

3

S2 = {2, 5, {3, 4}}S2 = {2, 5, {3, 4}, 1}

s t

1

3, 4

Schnitt der Phase: {V2 \ {1}, {1}}→ Gewicht 4




2

5

3

3

11S2 = {2, 5}

3

S2 = {2, 5, {3, 4}}S2 = {2, 5, {3, 4}, 1}

s t

1

3, 4



2

5

36

11, 3, 4



Phase 3G3 = G2 mit 1 und {3, 4} verschmolzenS3 = {{1, 3, 4}} (Startknoten {1, 3, 4})

36

11, 3, 4

2

5




36

11, 3, 4S3 = {{1, 3, 4}, 2}

2

5




36

11, 3, 4S3 = {{1, 3, 4}, 2}S3 = {{1, 3, 4}, 2, 5}

s t

2

5



7

1, 3, 4

2, 5



Phase 4G4 = G3 mit 2 und 5 verschmolzenS4 = {{1, 3, 4}} (Startknoten {1, 3, 4}) 7

1, 3, 4

2, 5




S3 = {{1, 3, 4}, {2, 5}}

s t

1, 3, 4

2, 5

Schnitt der Phase: {V3 \ {2, 5}, {2, 5}}→ Gewicht 7




S3 = {{1, 3, 4}, {2, 5}}

s t

1, 3, 4

2, 5

Schnitt der Phase: {V3 \ {2, 5}, {2, 5}}→ Gewicht 7

Phase 1 Schnitt der Phase: {V \ {3}, {3}} → Gewicht 4Phase 2 Schnitt der Phase: {V \ {1}, {1}} → Gewicht 4Phase 3 Schnitt der Phase: {V \ {5}, {5}} → Gewicht 4Phase 4 Schnitt der Phase: {V \ {{2, 5}}, {{2, 5}}} → Gewicht 7

1

3

2

4

5

33

2

2

111

Zusammenfassung:Drei minimale Schnitte gefunden.


Problem 6

(b) Liefert der Algorithmus von Stoer & Wagner auch fur negative Kantengewichteeinen global minimalen, nichttrivialen Schnitt? Begrunden Sie Ihre Antwort.


Problem 6


11 13

14

12

−9

−8−16

−16−16 −10

Startknoten 1

Nein, denn:


Problem 6


11 13

14

12

−9

−8−16

−16−16 −10

Startknoten 1

Nein, denn:


Problem 6


11 13

14

12

−9

−8−16

−16−16 −10

Startknoten 1

Nein, denn:


Problem 6


11 13

14

12

−9

−8−16

−16−16 −10

Startknoten 1

Nein, denn:

⇒ Schnitt der Phase 1:(V \ {4}, {4})

Gewicht −42


Problem 6


11 13

14

12

−9

−8−16

−16−16 −10

Startknoten 1

Nein, denn:


Gewicht −42

11

12

13, 4

−8

−25

−26


Problem 6


11 13

14

12

−9

−8−16

−16−16 −10

Startknoten 1

Nein, denn:


Gewicht −42

11

12

13, 4

−8

−25

−26

minimaler Schnitt hat Gewicht −51


Problem 6


11 13

14

12

−9

−8−16

−16−16 −10

Startknoten 1

Nein, denn:


Gewicht −42

11

12

13, 4

−8

−25

−26

minimaler Schnitt hat Gewicht −51

Aber:

11 13

14

12

−9

−8−16

−16−16 −10

Schnitt mit Gewicht −56

Documents

Vorlesung Algorithmen II - KIT - ITI Algorithmik I · KIT – Universitat des Landes Baden-W¨urttemberg und nationales Forschungszentrum in der Helmholtz-Gemeinschaft INSTITUT FUR¨