13.3 Transport Networks�The Max-Flow Min-Cut Theorem
Presentation by 0813371 李嘉泰
你老闆把你資遣了，所以你很火。你決定要展開報復，要寄一堆垃圾郵件去騷擾他，一封郵件會經過很多router才會到你老闆的電腦，router之間會有線路，每個router中也會有buffer，你最多能發多少封郵件去騷擾他呢？
DEFINTION 13.1
Def. 13.1 (a)
Def. 13.1 (b)
Def. 13.1 (c)
DEFINTION 13.2
Def. 13.2 (a)
Def. 13.2 (b)
EXAMPLE 13.6 (流量守恆)
a
b
g
d
h
z
(5,3)
(7,5)
(5,2)
(4,1)
(6,4)
(5,2)
(5,2)
(2,1)
(6,5)
a
b
g
d
h
z
(5,3)
(7,5)
(5,2)
(4,2)
(6,3)
(5,3)
(5,4)
(2,2)
(6,4)
流量不守恆，流入頂點 g 的流量有5，但流出g的流量只有2+2=4
流量守恆
DEFINTION 13.3
EXAMPLE 13.7 (value of the flow)
a
b
g
d
h
z
(5,3)
(7,5)
(5,2)
(4,2)
(6,3)
(5,3)
(5,4)
(2,2)
(6,4)
Discussion: 有辦法找到一個 flow 使得 val(f) > 8嗎?
DEFINTION 13.4
EXAMPLE 13.8 (cut)
a
b
g
d
h
z
(5,3)
(7,5)
(5,2)
(4,2)
(6,3)
(5,3)
(5,4)
(2,2)
(6,4)
EXAMPLE 13.8 (cut)
a
b
g
d
h
z
(5,3)
(7,5)
(5,2)
(4,2)
(6,3)
(5,3)
(5,4)
(2,2)
(6,4)
a
b
(5,3)
g
d
h
z
(5,3)
(5,4)
(2,2)
(6,4)
EXAMPLE 13.8 (cut)
a
b
g
d
h
z
(5,3)
(7,5)
(5,2)
(4,2)
(6,3)
(5,3)
(5,4)
(2,2)
(6,4)
Undirected edges : {a, g}, {b, g}, {b, h}, {b, d}
a
b
(5,3)
g
d
h
z
(5,3)
(5,4)
(2,2)
(6,4)
THEOREM 13.3
a
b
g
d
h
z
(5,3)
(7,5)
(5,2)
(4,2)
(6,3)
(5,3)
(5,4)
(2,2)
(6,4)
8 < 17
Proof
Adding the results in the above equations yields
Proof cont.
Proof cont.
Proof cont.
Proof cont.
Proof cont.
Proof cont.
Proof cont.
Theorem 13.3 : 從起點流出的流量，不會超過任何一個cut的capacity
COROLLARY 13.2
Proof
EXAMPLE 13.9
a
b
g
d
z
(8,4)
(8,6)
(5,1)
(4,1)
(6,3)
(5,2)
(6,4)
+2
+2
(8,6)
(8,8)
EXAMPLE 13.9
a
b
g
d
z
(8,6)
(8,8)
(5,1)
(4,1)
(6,3)
(5,2)
(6,4)
+2
+2
+2
(6,6)
(6,5)
(6,4)
EXAMPLE 13.9
a
b
g
d
z
(8,6)
(8,8)
(5,1)
(4,1)
(6,5)
(5,4)
(6,6)
Maximum flow = 6 + 6 = 12
?
EXAMPLE 13.9
a
b
g
d
z
(8,6)
(8,8)
(5,1)
(4,1)
(6,5)
(5,4)
(6,6)
+1
+1
+1
-1
EXAMPLE 13.9
a
b
g
d
z
(8,7)
(8,8)
(5,1)
(4,0)
(6,6)
(5,5)
(6,6)
Maximum flow = 7 + 6 = 13
DEFIFITION 13.6
a
(8,6)
b
d
g
z
(4,1)
(6,5)
(5,4)
DEFIFITION 13.7
THEOREM 13.4
Proof
Proof cont.
1.
2.
3.
4.
Proof cont.
且
Proof cont.
Proof cont.
且
THEOREM 13.5
Proof cont.
Transport network
Maximum flow value
No
f-augmenting path
Minimum cut
Minimum capacity
Example 13.10
a
b
z
d
(10,0)
(10,0)
(10,0)
(10,10)
(1,0)
+10
+10
(10,10)
(10,10)
(10,0)
+10
+10
(10,10)
Example 13.10
a
b
z
d
a
b
z
d
(10,0)
(10,0)
(10,0)
(1,0)
-1
(10,0)
+1
+1
+1
(1,1)
(10,1)
(10,1)
+1
+1
Example 13.10
a
b
z
d
a
b
z
d
(10,1)
(10,1)
(10,1)
(1,0)
(10,1)
Example 13.10
a
b
z
d
a
b
z
d
(10,1)
(10,1)
(10,1)
(1,0)
(10,1)
經過2次迭代
b
z
d
b
z
d
(10,10)
(10,10)
(10,10)
(1,0)
(10,10)
a
經過20次迭代
觀察 :
對於每一次的迭代，使用經過路徑數最少的 f-augmenting path，會更有效率。
a
b
z
d
(10,0)
(10,0)
(10,0)
(1,0)
(10,0)
a
b
z
a
z
d
a
b
z
d
(10,10)
(10,10)
(1,0)
(10,10)
(10,10)
a
b
z
d
a
b
z
d
The Edmonds-Karp Algorithm
The Ford-Fulkerson Algorithm
The Ford-Fulkerson Algorithm
Step 2
Thank you