37
Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult¨ at f¨ ur Mathematik Technische Universit¨ at M¨ unchen

Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

  • Upload
    others

  • View
    25

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Maximaler Fluss = minimaler Schnitt

Oliver Junge

Fakultat fur MathematikTechnische Universitat Munchen

Page 2: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse in Netzwerken

Page 3: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Mathematische Abstraktion

q s

3

1

5

2

2

Kapazität

Quelle Senke

Netzwerk

I gerichteter Graph G = (V , E )

I Quelle q ∈ V , Senke s ∈ V

I Kanten (u, v) haben Kapazitat c(u, v) ≥ 0

Page 4: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Fluss in einem Netzwerk

q s

2/3

1/1

0/5

1/2

2/2

KapazitätFluss

Fluss

f : V × V → R mit

(i) Kapazitatsbeschrankung: f (u, v) ≤ c(u, v)

(ii) Symmetrie: f (u, v) = −f (v , u)

(iii) Flusserhaltung:∑v∈V

f (u, v) = 0 fur u ∈ V − {q, s}

Page 5: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das Optimierungsproblem

q s

2/3

1/1

0/5

1/2

2/2

Wert des Flusses: 2 + 1 = 3

Wert eines Flusses

|f | =∑v∈V

f (q, v)

Optimierungsproblem

Finde Fluss f mit maximalem Wert.

Page 6: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Ein nicht-maximaler Fluss

q s

0/3

1/1

1/5

0/2

1/2

Wert: 0 + 1 = 1

... wie konnen wir die vorhandene Kapazitat besser nutzen?

Page 7: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

Residuale (=“Rest”-)Kapazitat

cf (u, v) = c(u, v)− f (u, v)

Residuales Netzwerk

Gf = (V , Ef ) mit

Ef = {(u, v) | cf (u, v) > 0}

und Quelle q sowie Senke s.

Page 8: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

0/3

1/1

1/5

0/2

1/2

Page 9: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

3

1/1

1/5

0/2

1/2

Page 10: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

3

1/1

1/5

2

1/2

Page 11: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

3

1

1/5

1/2

2r

Page 12: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

3

1

1/5

1/2

2r

... da cf (r , q) = c(r , q)− f (r , q)

= 0 + f (q, r) = 0 + 1

Page 13: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

3

1 2

1/2

4 1

Page 14: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

3

1 2

4 1

1

1

Page 15: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

3

1 2

4 1

1

1

Page 16: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Das residuale Netzwerk

q s

3

1 2

4 1

1

1

Ford-Fulkerson Algorithmus

vergroßere schrittweise den Fluss durch Hinzunahmevergroßernder Pfade = Pfade von q nach s in Gf .

Page 17: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Schnitte

q s

Q

S

Schnitt

Partition der Knoten V in zwei Mengen Q und S , so dass

q ∈ Q und s ∈ S .

Page 18: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Schnitte

q s

2/3

1/1

0/5

1/2

2/2

Q

S

I Fluss uber einen Schnitt:

f (Q, S) =∑

u∈Q,v∈S

f (u, v)

= 1− 0 + 2 = 3

I Kapazitat eines Schnittes:

c(Q, S) =∑

u∈Q,v∈S

c(u, v) = 1 + 2 = 3

I Minimaler Schnitt: c(Q, S) minimal

Page 19: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Schnitte

q s

2/3

1/1

0/5

1/2

2/2

Q

S

I Fluss uber einen Schnitt:

f (Q, S) =∑

u∈Q,v∈S

f (u, v) = 1− 0 + 2 = 3

I Kapazitat eines Schnittes:

c(Q, S) =∑

u∈Q,v∈S

c(u, v) = 1 + 2 = 3

I Minimaler Schnitt: c(Q, S) minimal

Page 20: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Schnitte

q s

2/3

1/1

0/5

1/2

2/2

Q

S

I Fluss uber einen Schnitt:

f (Q, S) =∑

u∈Q,v∈S

f (u, v) = 1− 0 + 2 = 3

I Kapazitat eines Schnittes:

c(Q, S) =∑

u∈Q,v∈S

c(u, v)

= 1 + 2 = 3

I Minimaler Schnitt: c(Q, S) minimal

Page 21: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Schnitte

q s

2/3

1/1

0/5

1/2

2/2

Q

S

I Fluss uber einen Schnitt:

f (Q, S) =∑

u∈Q,v∈S

f (u, v) = 1− 0 + 2 = 3

I Kapazitat eines Schnittes:

c(Q, S) =∑

u∈Q,v∈S

c(u, v) = 1 + 2 = 3

I Minimaler Schnitt: c(Q, S) minimal

Page 22: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Schnitte

q s

2/3

1/1

0/5

1/2

2/2

Q

S

I Fluss uber einen Schnitt:

f (Q, S) =∑

u∈Q,v∈S

f (u, v) = 1− 0 + 2 = 3

I Kapazitat eines Schnittes:

c(Q, S) =∑

u∈Q,v∈S

c(u, v) = 1 + 2 = 3

I Minimaler Schnitt: c(Q, S) minimal

Page 23: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse und Schnitte

Lemma 1

Sei (Q, S) ein Schnitt, dann gilt f (Q, S) = |f |.

Beweis: Ubung!

Also gilt

|f | = f (Q, S) =∑

u∈Q,v∈S

f (u, v) ≤∑

u∈Q,v∈S

c(u, v) = c(Q, S)

Lemma 2

Fur jeden Fluss f und jeden Schnitt (Q, S) gilt

|f | ≤ c(Q, S).

Also: maximaler Fluss ≤ minimaler Schnitt

Page 24: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse und Schnitte

Lemma 1

Sei (Q, S) ein Schnitt, dann gilt f (Q, S) = |f |.

Beweis: Ubung!

Also gilt

|f | = f (Q, S) =∑

u∈Q,v∈S

f (u, v) ≤∑

u∈Q,v∈S

c(u, v) = c(Q, S)

Lemma 2

Fur jeden Fluss f und jeden Schnitt (Q, S) gilt

|f | ≤ c(Q, S).

Also: maximaler Fluss ≤ minimaler Schnitt

Page 25: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse und Schnitte

Lemma 1

Sei (Q, S) ein Schnitt, dann gilt f (Q, S) = |f |.

Beweis: Ubung!

Also gilt

|f | = f (Q, S)

=∑

u∈Q,v∈S

f (u, v) ≤∑

u∈Q,v∈S

c(u, v) = c(Q, S)

Lemma 2

Fur jeden Fluss f und jeden Schnitt (Q, S) gilt

|f | ≤ c(Q, S).

Also: maximaler Fluss ≤ minimaler Schnitt

Page 26: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse und Schnitte

Lemma 1

Sei (Q, S) ein Schnitt, dann gilt f (Q, S) = |f |.

Beweis: Ubung!

Also gilt

|f | = f (Q, S) =∑

u∈Q,v∈S

f (u, v)

≤∑

u∈Q,v∈S

c(u, v) = c(Q, S)

Lemma 2

Fur jeden Fluss f und jeden Schnitt (Q, S) gilt

|f | ≤ c(Q, S).

Also: maximaler Fluss ≤ minimaler Schnitt

Page 27: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse und Schnitte

Lemma 1

Sei (Q, S) ein Schnitt, dann gilt f (Q, S) = |f |.

Beweis: Ubung!

Also gilt

|f | = f (Q, S) =∑

u∈Q,v∈S

f (u, v) ≤∑

u∈Q,v∈S

c(u, v)

= c(Q, S)

Lemma 2

Fur jeden Fluss f und jeden Schnitt (Q, S) gilt

|f | ≤ c(Q, S).

Also: maximaler Fluss ≤ minimaler Schnitt

Page 28: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse und Schnitte

Lemma 1

Sei (Q, S) ein Schnitt, dann gilt f (Q, S) = |f |.

Beweis: Ubung!

Also gilt

|f | = f (Q, S) =∑

u∈Q,v∈S

f (u, v) ≤∑

u∈Q,v∈S

c(u, v) = c(Q, S)

Lemma 2

Fur jeden Fluss f und jeden Schnitt (Q, S) gilt

|f | ≤ c(Q, S).

Also: maximaler Fluss ≤ minimaler Schnitt

Page 29: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse und Schnitte

Lemma 1

Sei (Q, S) ein Schnitt, dann gilt f (Q, S) = |f |.

Beweis: Ubung!

Also gilt

|f | = f (Q, S) =∑

u∈Q,v∈S

f (u, v) ≤∑

u∈Q,v∈S

c(u, v) = c(Q, S)

Lemma 2

Fur jeden Fluss f und jeden Schnitt (Q, S) gilt

|f | ≤ c(Q, S).

Also: maximaler Fluss ≤ minimaler Schnitt

Page 30: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Flusse und Schnitte

Lemma 1

Sei (Q, S) ein Schnitt, dann gilt f (Q, S) = |f |.

Beweis: Ubung!

Also gilt

|f | = f (Q, S) =∑

u∈Q,v∈S

f (u, v) ≤∑

u∈Q,v∈S

c(u, v) = c(Q, S)

Lemma 2

Fur jeden Fluss f und jeden Schnitt (Q, S) gilt

|f | ≤ c(Q, S).

Also: maximaler Fluss ≤ minimaler Schnitt

Page 31: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Maximaler Fluss = minimaler Schnitt

Satz

Der Fluss f ist genau dann maximal, wenn es einen Schnitt (Q, S)gibt, so dass

|f | = c(Q, S).

1. Sei f maximaler Fluss. Dann enthalt Gf keinen vergroßernden Pfad, alsokeinen Pfad von q nach s.

2. Betrachte den Schnitt (Q, S) mit

Q = {v ∈ V | es gibt einen Pfad von q nach v in Gf } .

3. Fur u ∈ Q und v ∈ S gilt c(u, v) = f (u, v).(Ansonsten ware cf (u, v) > 0, also (u, v) ∈ Ef und damit v ∈ Q.)

4. Wir haben also c(Q, S) = f (Q, S) und (Lemma 1) f (Q, S) = |f |.

Page 32: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Maximaler Fluss = minimaler Schnitt

Satz

Der Fluss f ist genau dann maximal, wenn es einen Schnitt (Q, S)gibt, so dass

|f | = c(Q, S).

1. Sei f maximaler Fluss. Dann enthalt Gf keinen vergroßernden Pfad, alsokeinen Pfad von q nach s.

2. Betrachte den Schnitt (Q, S) mit

Q = {v ∈ V | es gibt einen Pfad von q nach v in Gf } .

3. Fur u ∈ Q und v ∈ S gilt c(u, v) = f (u, v).(Ansonsten ware cf (u, v) > 0, also (u, v) ∈ Ef und damit v ∈ Q.)

4. Wir haben also c(Q, S) = f (Q, S) und (Lemma 1) f (Q, S) = |f |.

Page 33: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Maximaler Fluss = minimaler Schnitt

Satz

Der Fluss f ist genau dann maximal, wenn es einen Schnitt (Q, S)gibt, so dass

|f | = c(Q, S).

1. Sei f maximaler Fluss. Dann enthalt Gf keinen vergroßernden Pfad, alsokeinen Pfad von q nach s.

2. Betrachte den Schnitt (Q, S) mit

Q = {v ∈ V | es gibt einen Pfad von q nach v in Gf } .

3. Fur u ∈ Q und v ∈ S gilt c(u, v) = f (u, v).(Ansonsten ware cf (u, v) > 0, also (u, v) ∈ Ef und damit v ∈ Q.)

4. Wir haben also c(Q, S) = f (Q, S) und (Lemma 1) f (Q, S) = |f |.

Page 34: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Maximaler Fluss = minimaler Schnitt

Satz

Der Fluss f ist genau dann maximal, wenn es einen Schnitt (Q, S)gibt, so dass

|f | = c(Q, S).

1. Sei f maximaler Fluss. Dann enthalt Gf keinen vergroßernden Pfad, alsokeinen Pfad von q nach s.

2. Betrachte den Schnitt (Q, S) mit

Q = {v ∈ V | es gibt einen Pfad von q nach v in Gf } .

3. Fur u ∈ Q und v ∈ S gilt c(u, v) = f (u, v).

(Ansonsten ware cf (u, v) > 0, also (u, v) ∈ Ef und damit v ∈ Q.)

4. Wir haben also c(Q, S) = f (Q, S) und (Lemma 1) f (Q, S) = |f |.

Page 35: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Maximaler Fluss = minimaler Schnitt

Satz

Der Fluss f ist genau dann maximal, wenn es einen Schnitt (Q, S)gibt, so dass

|f | = c(Q, S).

1. Sei f maximaler Fluss. Dann enthalt Gf keinen vergroßernden Pfad, alsokeinen Pfad von q nach s.

2. Betrachte den Schnitt (Q, S) mit

Q = {v ∈ V | es gibt einen Pfad von q nach v in Gf } .

3. Fur u ∈ Q und v ∈ S gilt c(u, v) = f (u, v).(Ansonsten ware cf (u, v) > 0, also (u, v) ∈ Ef und damit v ∈ Q.)

4. Wir haben also c(Q, S) = f (Q, S) und (Lemma 1) f (Q, S) = |f |.

Page 36: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Maximaler Fluss = minimaler Schnitt

Satz

Der Fluss f ist genau dann maximal, wenn es einen Schnitt (Q, S)gibt, so dass

|f | = c(Q, S).

1. Sei f maximaler Fluss. Dann enthalt Gf keinen vergroßernden Pfad, alsokeinen Pfad von q nach s.

2. Betrachte den Schnitt (Q, S) mit

Q = {v ∈ V | es gibt einen Pfad von q nach v in Gf } .

3. Fur u ∈ Q und v ∈ S gilt c(u, v) = f (u, v).(Ansonsten ware cf (u, v) > 0, also (u, v) ∈ Ef und damit v ∈ Q.)

4. Wir haben also c(Q, S) = f (Q, S) und (Lemma 1) f (Q, S) = |f |.

Page 37: Maximaler Fluss = minimaler Schnitt - WebHome · Maximaler Fluss = minimaler Schnitt Oliver Junge Fakult at f ur Mathematik Technische Universit at M unchen

Material/Ubungen

I Skript: http://www-m3.ma.tum.de

I Ubung: Beweise Lemma 1