Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại - Nguyễn Đức Nghĩa

Chương 6  Bài toán luồng cực đại  Maximum Flow Problem 
w 
s 
v 
u 
t 
z 
3 / 3 
1 / 9 
1 / 1 
3 / 3 
4 / 7 
4 / 6 
3 / 5 
1 / 1 
3 / 5 
2 / 2 
c 
Bài toán luồng cực đại  Maximum Flow Problem 
w 
s 
v 
u 
t 
z 
3 / 3 
1 / 9 
1 / 1 
3 / 3 
4 / 7 
4 / 6 
3 / 5 
1 / 1 
3 / 5 
2 / 2 
c 
3 
NỘI DUNG 
 Bài toán luồng cực đại trong mạng. 
 Lát cắt, Đường tăng luồng. 
 Định lý về luồng cực đại và lát cắt hẹp nhất. 
 Thuật toán Ford-Fulkerson 
 Thuật toán Edmond-Karp. 
 Các ứng dụng 
4 
L. R. Ford; D. R. Fulkerson (1962). Flows in Networks . Princeton, NJ: Princeton University Press. 
5 
Lester Randolph Ford, Jr (1927 ~) 
Lester Randolph Ford, Jr. (born September 23, 1927), son of Lester R. Ford, Sr., is an American mathematician specializing in network flow programming. His 1956 paper with D. R. Fulkerson on the maximum flow problem established the maxflow-mincut theorem. 
6 
Delbert Ray Fulkerson  (August 14, 1924 - January 10, 1976) 
Delbert Ray Fulkerson was a mathematician who co-developed the Ford-Fulkerson algorithm, one of the most used algorithms to compute maximal flows in networks. 
Ph.D, Univ. of Wisconsin-Madison, 1951. 
In 1956, he published his famous paper on the Ford-Fulkerson algorithm together with Lester Randolph Ford. 
In 1979, the renowned Fulkerson Prize was established which is now awarded every three years for outstanding papers in discrete mathematics jointly by the Mathematical Programming Society and the American Mathematical Society. 
2008/5/2 
Network Flows 
s 
t 
3 
1 
1 
4 
3 
2 
2 
2 
1 
1 
1 
1 
2 
1 
864 pages! 
Ravindra K. Ahuja, Thomas Magnanti and James Orlin. Network Flows. Prentice Hall, 1993. 
8 
Mạng và luồng trong mạng 
9 
 MẠNG (Network) 
Mạng là đồ thị có hướng G = (V,E) : 
Có duy nhất một đỉnh s không có cung đi vào gọi là đỉnh phát (nguồn) và duy nhất một đỉnh t không có cung đi ra gọi là đỉnh thu (đích). 
Mỗi cung e của G được gắn với một số không âm c ( e ) được gọi là khả năng thông qua của e. 
Ví dụ: 
w 
s 
v 
u 
t 
z 
3 
9 
1 
3 
7 
6 
5 
1 
5 
2 
10 
LUỒNG TRONG MẠNG 
 Định nghĩa. Luồng f trong mạng G =( V,E ) là phép gán số f ( e ) cho mỗi cạnh e ( f ( e ) được gọi là luồng trên cạnh e ) thoả mãn các điều kiện: 
1) Hạn chế về khả năng thông qua (Capacity Rule): 
 Với mỗi cung e , 0 f ( e ) c ( e ) 
2) Điều kiện cân bằng luồng (Conservation Rule): Với mỗi v s, t  
 trong đó E - ( v ) và E + ( v ) tương ứng là tập các cung đi vào và đi ra khỏi đỉnh v . 
Định nghĩa. Giá trị của luồng f là 
(Đẳng thức (*) thu được bằng cách cộng tất cả các điều kiện cân bằng luồng.) 
11 
LUỒNG TRONG MẠNG – Ví dụ 
Trong 2 số viết bên mỗi cạnh: giá trị luồng trên cạnh là số màu đỏ, số còn lại là khả năng thông qua. 
Các điều kiện 1) và 2) được thoả mãn => f là luồng trên mạng. 
Giá trị luồng là: 
 8 = f ( s,v ) + f ( s,u ) + f ( s,w ) = f ( v,t ) + f ( w,t ) + f ( z,t ) 
w 
s 
v 
u 
t 
z 
3/ 3 
2/ 9 
1/ 1 
1/ 3 
3/ 7 
2/ 6 
4/ 5 
1/ 1 
3/ 5 
2/ 2 
Ví dụ: 
12 
Bài toán luồng cực đại 
Luồng trong mạng G được gọi là luồng cực đại nếu trong số tất cả các luồng trong mạng G nó là luồng có giá trị lớn nhất 
Bài toán tìm luồng cực đại trong mạng G được gọi là bài toán luồng cực đại 
w 
s 
v 
u 
t 
z 
3/ 3 
2/ 9 
1/ 1 
1/ 3 
3/ 7 
2/ 6 
4/ 5 
1/ 1 
3/ 5 
2/ 2 
w 
s 
v 
u 
t 
z 
3/ 3 
2/ 9 
1/ 1 
3/ 3 
3/ 7 
4/ 6 
4/ 5 
1/ 1 
3/ 5 
2/ 2 
Luồng với giá trị 8 = 2 + 3 + 3 = 1 + 3 + 4 
Luồng cực đại có giá trị 10 = 4 + 3 + 3 = 3 + 3 + 4 
13 
Mạng: G = (V, E, s, t, c) . 
(V, E) = đồ thị có hướng, không có cung lặp. 
Có hai đỉnh đặc biệt: s = phát/nguồn (source), t = thu/đích (sink). 
c(e) = khả năng thông qua (capacity) của cung e. 
Mạng 
Capacity 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
14 
Luồng từ s đến t là hàm f: E R thoả mãn: 
Với mỗi e E :	 0 f ( e ) c ( e ) (hạn chế kntq) 
Với mỗi v V – { s, t }: 	 (cân bằng luồng) 
Luồng 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
4 
0 
0 
0 
0 
0 
0 
0 
4 
4 
0 
4 
0 
0 
0 
kntq 
Capacity 
Luồng 
Flow 
15 
Bài toán luồng cực đại: Tìm luồng có tổng luồng trên các cạnh đi ra khỏi đỉnh phát là lớn nhất: 
Luồng 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
4 
0 
0 
0 
0 
0 
0 
0 
4 
4 
0 
4 
0 
Giá trị = 4 
0 
0 
kntq 
Luồng 
16 
Luồng có giá trị 24 trong mạng: 
Luồng 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
10 
6 
6 
11 
11 
1 
10 
3 
8 
8 
0 
4 
0 
Giá trị = 24 
0 
0 
kntq 
Luồng 
17 
Luồng có giá trị 28 trong mạng: 
Luồng 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
10 
9 
9 
14 
14 
4 
10 
4 
8 
9 
1 
0 
0 
Giá trị = 28 
0 
0 
kntq 
Luồng 
18 
Luồng trong mạng 
truyền thông 
Mạng 
trạm giao dịch,máy tính, vệ tinh 
Đỉnh 
Cung 
cáp nối, cáp quang, 
Luồng 
voice, video,packets 
mạng điện 
cổng, registers,processors 
dây dẫn 
dòng điện 
cơ khí 
joints 
rods, beams, springs 
heat, energy 
thuỷ lợi 
hồ chứa, trạm bơm, 
nguồn nước 
đường ống 
dòng nước, 
chất lỏng 
tài chính 
nhà băng 
giao dịch 
tiền 
giao thông 
sân bay, ga tàu,giao lộ 
đường cao tốc, ray,đường bay 
hàng hoá,phương tiện,hành khách 
hoá học 
sites 
bonds 
energy 
19 
Luồng trong mạng 
communication 
Mạng 
telephone exchanges,computers, satellites 
Đỉnh 
Cung 
cables, fiber optics,microwave relays 
Luồng 
voice, video,packets 
circuits 
gates, registers,processors 
wires 
current 
mechanical 
joints 
rods, beams, springs 
heat, energy 
hydraulic 
reservoirs, pumpingstations, lakes 
pipelines 
fluid, oil 
financial 
stocks, currency 
transactions 
money 
transportation 
airports, rail yards,street intersections 
highways, railbeds,airway routes 
freight,vehicles,passengers 
chemical 
sites 
bonds 
energy 
20 
Network reliability. 
Security of statistical data. 
Distributed computing. 
Egalitarian stable matching. 
Distributed computing. 
Many many more . . . 
Các ứng dụng/qui dẫn 
Network connectivity. 
Bipartite matching. 
Data mining. 
Open-pit mining. 
Airline scheduling. 
Image processing. 
Project selection. 
Baseball elimination. 
21 
Lát cắt – Đường tăng luồng 
22 
Lát cắt là cách phân hoạch tập đỉnh (S, T) sao cho s S, t T. 
Khả năng thông qua cap ( S,T ) của lát cắt (S, T) là số: 
Lát cắt (Cuts) 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
kntq = 30 
Lát cắt nhỏ nhất (hẹp nhất) là lát cắt với kntq nhỏ nhất. 
23 
Lát cắt (S 1 , T 1 ), S 1 ={s,2,3,4}, T={5,6,7,t) có khả năng thông qua 62: 
Lát cắt 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
cap(S 1 ,T 1 )= 62 
24 
Lát cắt (S 2 , T 2 ), S 2 ={s,3,4,7}, T 2 ={2,5,6,t) có khả năng thông qua 28: 
Lát cắt 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
cap(S 2 ,T 2 ) = 28 
25 
Bổ đề 1. Giả sử f là luồng, và ( S, T ) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: 
trong đó S T = {( v,w ) E : v S , w T } và T S = {( v,w ) E : v T , w S } 
Luồng và lát cắt 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
Giá trị = 24 
10 
6 
6 
10 
10 
0 
10 
4 
8 
8 
0 
4 
0 
0 
0 
26 
Bổ đề 1. Giả sử f là luồng, và ( S, T ) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: 
Luồng và lát cắt 
10 
6 
6 
10 
10 
0 
10 
4 
8 
8 
0 
4 
0 
0 
0 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
Giá trị = 24 
27 
Bổ đề 1. Giả sử f là luồng, và ( S, T ) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: 
Luồng và lát cắt 
10 
6 
6 
10 
10 
0 
10 
4 
8 
8 
0 
4 
0 
0 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
Giá trị = 24 
0 
28 
Luồng và lát cắt 
Chứng minh bổ đề: Giả sử f là luồng còn (S, T) là lá cắt. Khi đó 
S 
CM. Cộng tất cả các ràng buộc cân bằng luồng theo mọi v S, đơn giản biểu thức ta thu được: 
s 
v 
t 
u 
w 
từ đó suy ra đẳng thức cần chứng minh 
tổng theo các cung xanh 
tổng theo các cung tím 
T 
29 
Bổ đề 2. Giả sử f là luồng, còn (S, T) là lát cắt. Khi đó, val(f) cap(S, T). 
CM. 
Luồng và lát cắt 
s 
t 
S 
T 
 7 
6 
 8 
4 
30 
Luồng cực đại và lát cắt nhỏ nhất Max Flow and Min Cut 
Hệ quả. Giả sử f là luồng, còn (S, T) là lát cắt. Nếu val(f) = cap(S, T) , thì f là luồng cực đại còn (S, T) là lát cắt hẹp nhất. 
CM. Xét f’ là luồng bất kỳ và (S’,T’) là lát cắt bất kỳ. Theo bổ đề ta có 
 val(f’) cap(S,T) = val(f) cap(S’,T’). 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
10 
9 
9 
14 
14 
4 
10 
4 
8 
9 
1 
0 
0 
Giá trị luồng = 28 
0 
0 
kntq của lát cắt = 28 
31 
Định lý về luồng cực đại và lát cắt nhỏ nhất Max-Flow Min-Cut Theorem 
Đinh lý (Ford-Fulkerson, 1956): Trong mạng bất kỳ, giá trị của luồng cực đại luôn bằng khả năng thông qua của lát cắt nhỏ nhất. 
Proof (muộn hơn). 
s 
2 
3 
4 
5 
6 
7 
t 
 15 
 5 
 30 
 15 
 10 
 8 
 15 
 9 
 6 
 10 
 10 
 10 
 15 
 4 
 4 
10 
9 
9 
15 
15 
4 
10 
4 
8 
9 
1 
0 
0 
Flow value = 28 
0 
0 
Cut capacity = 28 
32 
Ý tưởng thuật toán 
Thuật toán tham lam: 
Bắt đầu từ luồng 0 (Luồng có giá trị = 0). 
Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e). 
Tăng luồng dọc theo đường đi P. 
Lặp lại cho đến khi gặp bế tắc. 
s 
4 
2 
5 
3 
t 
 4 
0 
0 
0 
0 
0 
0 
 4 
0 
 4 
 4 
Luồng có giá trị = 0 
 10 
 13 
 10 
33 
Ý tưởng thuật toán 
Thuật toán tham lam: 
Bắt đầu từ luồng 0 (Luồng có giá trị = 0). 
Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e). 
Tăng luồng dọc theo đường đi P. 
Lặp lại cho đến khi gặp bế tắc. 
s 
4 
2 
5 
3 
t 
 4 
0 
0 
0 
0 
0 
0 
 4 
0 
 4 
 4 
Giá trị luồng = 10 
 10 
 13 
 10 
10 
10 
10 
X 
X 
X 
34 
Ý tưởng thuật toán 
Thuật toán tham lam: 
Bắt đầu từ luồng 0 (Luồng có giá trị = 0). 
Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e). 
Tăng luồng dọc theo đường đi P. 
Lặp lại cho đến khi gặp bế tắc. 
Thuật toán tham lam cho luồng với giá trị 10. 
s 
4 
2 
5 
3 
t 
 10 
 13 
 10 
 4 
0 
0 
10 
10 
10 
0 
 4 
0 
 4 
 4 
35 
Ý tưởng thuật toán 
Thuật toán tham lam không cho lời giải tối ưu. 
s 
4 
2 
5 
3 
t 
 10 
 13 
 10 
 4 
0 
0 
10 
10 
10 
0 
 4 
0 
 4 
 4 
TT tham lam: 
Giá trị luồng = 10 
s 
4 
2 
5 
3 
t 
 10 
 13 
 10 
 4 
4 
4 
10 
6 
10 
4 
 4 
4 
 4 
4 
Tối ưu: 
Giá trị luồng = 14 
36 
Đồ thị tăng luồng – Đường tăng luồng 
37 
Đồ thị tăng luồng – Tập cung 
Mạng đã cho G = (V, E). 
Luồng f(e), e E . 
Cung e = (v, w) E. 
Đồ thị tăng luồng: G f = (V, E f ). 
“thu lại" luồng đã gửi. 
E f = {e: f(e) 0 }. 
Khả năng thông qua 
v 
w 
 17 
6 
kntq 
Luồng 
Kntq 
Kntq 
v 
w 
 11 
 6 
e = (u,v) e R = (v,u) 
38 
Đồ thị tăng luồng - Ví dụ 
Đồ thị tăng luồng: G f = (V, E f ). 
E f = {e : f(e) 0}. 
c f (e) cho biết lượng lớn nhất có thể tăng luồng trên cung e. 
c f (e R ) cho biết lượng lớn nhất có thể giảm luồng trên cung e. 
s 
4 
2 
5 
3 
t 
 10 
 13 
 10 
 4 
0 
0 
10 
10 
10 
0 
 4 
0 
 4 
 4 
G 
s 
4 
2 
5 
3 
t 
 10 
 10 
 10 
 4 
 4 
 4 
 4 
 3 
G f 
39 
Đường tăng luồng 
Đường tăng luồng = đường đi từ s đến t trên đồ thị tăng luồng G f . 
Khả năng thông qua của đường đi P là 
 c f ( P ) = min { c f ( e ): e P }. 
s 
4 
2 
5 
3 
t 
 10 
 13 
 10 
 4 
0 
0 
10 
10 
10 
0 
 4 
0 
 4 
 4 
 3 
G 
4 
4 
6 
4 
4 
X 
X 
X 
X 
X 
s 
4 
2 
5 
3 
t 
 10 
 10 
 10 
 4 
 4 
 4 
 4 
G f 
c f ( P ) = 4 
40 
Đường tăng luồng 
Đường tăng luồng = đường đi từ s đến t trên đồ thị tăng luồng. 
Luồng là cực đại không tìm được đường tăng luồng ??? 
Giá trị luồng = 14 
s 
4 
2 
5 
3 
t 
 10 
 13 
 10 
 4 
4 
4 
10 
6 
10 
4 
 4 
4 
 4 
 4 
G 
s 
4 
2 
5 
3 
t 
 10 
 6 
 10 
 4 
 4 
 4 
 4 
 7 
G f 
41 
Định lý về luồng cực đại và lát cắt nhỏ nhất 
Định lý đường tăng luồng (Ford-Fulkerson, 1956): Luồng là cực đại khi và chỉ khi không tìm được đường tăng luồng. 
Định lý về luồng cực đại và lát cắt nhỏ nhất (Ford-Fulkerson, 1956): Giá trị của luồng cực đại bằng khả năng thông qua của lát cắt nhỏ nhất. 
Ta sẽ chứng minh định lý tổng hợp sau: 
Định lý. Giả sử f là luồng trong mạng. Ba mệnh đề sau là tương đương 
 (i)	Tìm được lát cắt (S, T) sao cho val(f) = cap(S, T). 
 (ii)	f là luồng cực đại. 
 (iii)	Không tìm được đường tăng luồng f. 
42 
Chứng minh định lý 
Chứng minh. 
(i) (ii) 
Suy từ hệ quả của Bổ đề 2. 
(ii) (iii) 
Chứng minh bằng lập luận phản đề (contrapositive): Nếu tìm được đường tăng thì f không là luồng cực đại. 
Thực vậy, nếu tìm được đường tăng P, thì tăng luồng dọc theo P ta thu được luồng f’ với giá trị lớn hơn. 
43 
Chứng minh định lý 
(iii) (i) 
Giả thiết: f là luồng và G f không chứa đường đi từ s đến t. 
Gọi S là tập các đỉnh đạt tới được từ s trong G f . 
Theo định nghĩa s S, và theo giả thiết t S 
Ta có 
 f ( e ) = 0 , e T S, 
 f ( e ) = c ( e ) , e S T 
Từ đó suy ra 
Mạng đã cho G 
s 
t 
S 
T 
44 
Thuật toán Ford – Fulkerson 
Augment(f,P) 
b  c f (P) 
FOR e P DO 
 IF (e E) THEN // cạnh thuận 
 f(e)  f(e) + b 
 ELSE // cạnh nghịch 
 f(e R )  f(e) – b 
RETURN f 
Tăng luồng f dọc theo đường tăng P 
Ford_Fulkerson(G,c,s,t); 
FOR e E DO // Khởi tạo luồng 0 
 f(e)  0 
G f  đồ thị tăng luồng f 
WHILE (tìm được đường tăng luồng P) DO 
 f  augment(f, P) 
 Sửa lại G f 
RETURN f 
Thuật toán Ford-Fulkerson 
Ví dụ 
45 
Thời gian tính 
Giả thiết: tất cả các khả năng thông qua là các số nguyên trong khoảng từ 0 đến C. 
Bất biến: mỗi giá trị luồng f(e) và mỗi khả năng thông qua c f (e) luôn luôn là số nguyên trong quá trình thực hiện thuật toán. 
Định lý: Thụât toán dừng sau không quá val( f *) nC lần lặp. 
CM. Sau mỗi lần tăng luồng, giá trị của luồng tăng thêm ít nhất 1. 
Hệ quả. Thời gian tính của thuật toán F-F là O(m.n.C) 
Hệ quả: Nếu C = 1, thì thuật toán đòi hỏi thời gian O(mn). 
46 
Thời gian tính 
Giả thiết: tất cả các khả năng thông qua là các số nguyên trong khoảng từ 0 đến C. 
Bất biến: mỗi giá trị luồng f(e) và mỗi khả năng thông qua c f (e) luôn luôn là số nguyên trong quá trình thực hiện thuật toán. 
Định lý: Thụât toán dừng sau không quá val( f *) nC lần lặp. 
CM. Sau mỗi lần tăng luồng, giá trị của luồng tăng thêm ít nhất 1. 
Hệ quả: Nếu C = 1, thì thuật toán đòi hỏi thời gian O(mn). 
Định lý về tính nguyên: Nếu kntq là các số nguyên, thì luôn tồn tại luồng cực đại với giá trị luồng trên các cung là các số nguyên. 
Chú ý: Thuật toán có thể không dừng nếu kntq là không nguyên. Hơn thế nữa thuật toán còn không hội tụ đến lời giải tối ưu. 
47 
Thuật toán Ford-Fulkerson: Thời gian hàm mũ 
Question: Thuật toán Ford-Fulekerson có phải là thuật toán đa thức? (thuật toán với thời gian tính bị chặn bởi đa thức bậc cố định của độ dài dữ liệu vào) 
Answer: Không phải. Nếu kntq lớn nhất là C thì thuật toán có thể phải thực hiện cỡ C bước lặp. 
Ví dụ: 
48 
10 9 
0 
0 
s 
4 
2 
t 
 1 
10 9 
10 9 
0 
0 
0 
Thuật toán F-F không là thuật toán đa thức 
10 9 
49 
10 9 
0 
0 
s 
4 
2 
t 
 1 
10 9 
10 9 
0 
0 
0 
Thuật toán F-F không là thuật toán đa thức 
10 9 
1 
1 
1 
X 
X 
X 
50 
10 9 
1 
0 
s 
4 
2 
t 
10 9 
1 
1 
0 
Thuật toán F-F không là thuật toán đa thức 
10 9 
10 9 
 1 
51 
10 9 
1 
0 
s 
4 
2 
t 
 1 
10 9 
10 9 
1 
1 
0 
Thuật toán F-F không là thuật toán đa thức 
10 9 
1 
0 
1 
X 
X 
X 
52 
s 
4 
2 
t 
 1 
10 9 
10 9 
10 9 
10 9 
0 
1 
1 
1 
1 
Thuật toán F-F không là thuật toán đa thức 
2 1 0 9 lần lặp. 
Ví dụ 
 Zwick xây dựng ví dụ sau đây cho thấy thuật toán F-F có thể không dừng, nếu như khả năng thông qua là số vô tỷ 
53 
 Có 6 cung với khả năng thông qua X, 2 cung khả năng thông qua 1 và một cung khả năng thông qua 
  = (sqrt(5)-1)/2 0.618034... 
s 
t 
X 
1 
X 
X 
1 
 
X 
X 
X 
Để chỉ ra thuật toán không dừng, ta có thể theo dõi khả năng thông qua của 3 cung nằm ngang của đồ thị tăng luồng trong quá trình thực hiện thuật toán. (Khả năng thông qua của 6 cung còn lại ít nhất là X-3). 
54 
s 
t 
X 
1 
X 
X 
1 
 
X 
X 
X 
Thực hiện thuật toán FF 
Thuật toán FF bắt đầu bởi việc sử dụng đường tăng luồng trung tâm trong hình vẽ trên. Giá trị luồng tăng thêm được 1. Val(f)=1. 
Trên đồ thị tăng luồng: Các cung nằm ngang theo thứ tự từ trái sang có khả năng rút gọn là 1, 0,  
55 
s 
t 
X 
1 
X 
X 
1 
 
X 
X 
X 
s 
t 
1 
0 
 
Thực hiện thuật toán FF 
56 
s 
t 
B 
s 
t 
s 
t 
s 
t 
X 
1 
X 
X 
1 
 
X 
X 
X 
C 
A 
Thực hiện thuật toán FF 
Giả sử ở đầu lần lặp k các cung đó có khả năng thông qua là  k -1 , 0,  k . Khi đó 
1) Tăng luồng dọc theo B thêm  k , kntq của chúng trở thành  k +1 ,  k , 0 
2) Tăng luồng dọc theo C thêm  k , kntq của chúng trở thành  k +1 , 0,  k , 
3) Tăng luồng dọc theo B thêm  k+ 1 , kntq của chúng trở thành 0,  k +1 ,  k +2 , 
4) Tăng luồng dọc theo A thêm  k+ 1 , kntq của chúng trở thành  k +1 , 0,  k +2 , 
Sau 4 lần tăng, giá trị của luồng tăng thêm là 2(  k +  k+ 1 )=2  k+ 2 
Sau 4 n +1 lần tăng luồng, khả năng thông qua sẽ là  2 n- 2 , 0,  2 n -1 , Khi số lần tăng luồng ra vô cùng, giá trị của luồng sẽ là 
Mặc dù dễ thấy là giá trị của luồng cực đại trong mạng này là 2X+1. 
57 
58 
Chọn đường tăng luồng như thế nào? 
Cần hết sức cẩn thận khi lựa chọn đường tăng, bởi vì 
Một số cách chọn dẫn đến thuật toán hàm mũ. 
Cách chọn khôn khéo dẫn đến thuật toán đa thức. 
Nếu kntq là các số vô tỷ, thuật toán có thể không dừng 
Mục đích: chọn đường tăng sao cho: 
Có thể tìm đường tăng một cách hiệu quả. 
Thuật toán đòi hỏi thực hiện càng ít bước lặp càng tốt. 
Chọn đường tăng với (Edmonds-Karp 1972, Dinitz 1970) 
khả năng thông qua lớn nhất.	 (đường béo - fat path) 
khả năng thông qua đủ lớn. 	 (thang độ hoá kntq – capacity scaling) 
số cạnh trên đường đi là ít nhất. (đường ngắn nhất - shortest path) 
59 
Thang độ hoá kntq (Capacity Scaling) 
Trực giác: chọn đường đi với kntq lớn nhất sẽ tăng giá trị luồng lên nhiều nhất. 
Không cần quan tâm đến tìm đường với kntq lớn nhất. 
Chọn thông số thang độ . 
Gọi G f ( ) là đồ thị con của đồ thị tăng luồng chỉ gồm các cung có kntq ít nhất là . 
110 
s 
4 
2 
t 
 1 
170 
102 
122 
G f 
110 
s 
4 
2 
t 
170 
102 
122 
G f (100) 
60 
Thuật toán Capacity Scaling 
  / 2 
RETURN f 
WHILE ( tìm được đường đi P từ s đến t trong G f ( ) ) 
 f  augment(f, P) 
 Hiệu chỉnh G f ( ) 
ScalingMaxFlow(V, E, s, t, c) 
FOR e E, f(e)  0 
q = min { k Z : 2 k C }; = 2 q 
WHILE ( 1) 
 Xây dựng đồ thị G f ( ) 
Pha nấc 
61 
Tính đúng đắn của thuật toán Capacity Scaling 
Giả thiết. Khả năng thông qua của các cung là các số nguyên trong khoảng từ 1 đến C. 
Tính bất biến. Mọi luồng và khả năng thông qua trong suốt quá trình thực hiện thuật toán luôn là số nguyên. 
Tính đúng đắn: Nếu thuật toán kết thúc thì f là luồng cực đại. 
Chứng minh. 
Theo tính bất biến, khi = 1 G f ( ) = G f 
Pha nấc = 1 kết thúc khi không tìm được đường tăng luồng 
Vậy f là luồng cực đại. 
62 
Thời gian tính của Capacity Scaling 
Bổ đề 1. Vòng lặp ngoài lặp 1 + log 2 C lần. 
CM. Thoạt tiên C < 2C, và chỉ còn một nửa sau mỗi lần lặp. 
Bổ đề 2. Giả sử f là luồng tại thời điểm kết thúc pha nấc . Thế thì giá trị của luồng cực đại không vượt quá val( f ) + m . 
CM. Xem Silde tiếp theo 
Bổ đề 3. Có nhiều nhất là 2m lần tăng luồng tại mỗi pha nấc . 
Gọi f là luồng tại cuối pha nấc 2 (là pha ngay trước pha nấc ). 
Từ BĐ2 val(f*) val( f ) + m (2 ). 
Mỗi lần tăng trong pha nấc tăng giá trị cuả val( f ) lên ít nhất . 
Định lý. Thuật toán Scaling max-flow kết thúc sau không quá O(m log C) lần tăng luồng và có thể cài đặt với thời gian O(m 2 log C ). 
63 
Capacity Scaling: Analysis 
Bổ đề 2. Giả sử f là luồng tại thời điểm kết thúc pha nấc . Thế thì giá trị của luồng cực đại không vượt quá val( f ) + m . 
CM. 
Ta sẽ chỉ ra là khi kết thúc pha nấc phải tìm được lát cắt (S, T) sao cho cap(S, T) val( f ) + m . 
Gọi S là tập các đỉnh đạt tới được từ s trong G f ( ) . 
rõ ràng s S, và t S theo định nghĩa của S 
s 
t 
Mạng đã cho 
S 
T 
64 
10 9 
0 
0 
s 
4 
2 
t 
 1 
10 9 
10 9 
0 
0 
0 
Ví dụ 
C = 10 9 ; q = 30; 0 = 2 30 = 1 073 741 824; G f (2 30 ) = (V,) 
10 9 
65 
Ví dụ 
Đường tăng luồng: s, 4, t 
10 9 
s 
4 
2 
t 
10 9 
10 9 
10 9 
G f (2 29 ) 
10 9 
10 9 
0 
s 
4 
2 
t 
10 9 
10 9 
0 
10 9 
10 9 
G 
 1 
 0 
66 
Ví dụ 
Đường tăng luồng: s, 2, t 
s 
4 
2 
t 
10 9 
G f (2 29 ) 
10 9 
10 9 
10 9 
s 
4 
2 
t 
10 9 
10 9 
10 9 
10 9 
10 9 
 G 
 1 
 0 
10 9 
10 9 
10 9 
67 
Ví dụ 
Kết thúc pha nấc 2 29 
s 
4 
2 
t 
G f (2 29 ) 
10 9 
10 9 
10 9 
s 
4 
2 
t 
10 9 
10 9 
10 9 
10 9 
10 9 
G 
 1 
 0 
10 9 
10 9 
10 9 
10 9 
68 
Ví dụ 
G f (2 k ), k = 28, 27, ..., 2, 1 như nhau. Các pha nấc 2 k kết thúc mà không tăng được luồng 
s 
4 
2 
t 
G f (2 k ), k=28, 27, ...,,2,1 
10 9 
10 9 
10 9 
s 
4 
2 
t 
10 9 
10 9 
10 9 
10 9 
10 9 
G 
 1 
 0 
10 9 
10 9 
10 9 
10 9 
69 
Ví dụ 
Trên G f (1) không tìm được đường đi từ s đến t. Thuật toán kết thúc. 
s 
4 
2 
t 
G f (1) 
10 9 
10 9 
10 9 
s 
4 
2 
t 
10 9 
10 9 
10 9 
10 9 
10 9 
 G 
 1 
 0 
10 9 
10 9 
10 9 
10 9 
1 
Do G f (1) ≡ G f nên trên G f không tìm được đường đi từ s đến t. Vậy luồng đang có trong mạng là cực đại. 
70 
Chọn đường tăng luồng như thế nào? 
Cần hết sức cẩn thận khi lựa chọn đường tăng, bởi vì 
Một số cách chọn dẫn đến thuật toán hàm mũ. 
Cách chọn khôn khéo dẫn đến thuật toán đa thức. 
Nếu kntq là các số vô tỷ, thuật toán có thể không dừng 
Mục đích: chọn đường tăng sao cho: 
Có thể tìm đường tăng một cách hiệu quả. 
Thuật toán đòi hỏi thực hiện càng ít bước lặp càng tốt. 
Chọn đường tăng với (Edmonds-Karp 1972, Dinitz 1970) 
khả năng thông qua lớn nhất.	 (đường béo - fat path) 
khả năng thông qua đủ lớn.	 (thang độ hoá kntq – capacity scaling) 
số cạnh trên đường đi là ít nhất. (đường ngắn nhất - shortest path) 
2008/5/2 
Edmonds – Karp Algorithm 
Edmonds and Karp, JACM 1972 
Nếu đường tăng được chọn là đường ngắn nhất từ s đến t , thì thời gian tính của thuật toán sẽ là O (| E | 2 | V |). 
2008/5/2 
Jack Edmonds 
Jack Edmonds is a Canadian mathematician, regarded as one of the most important contributors to the field of combinatorial optimization. He was the recipient of the 1985 John von Neumann Theory Prize. 
From 1969 on, with the exception of 1991-1993, he held a faculty position at the Department of Combinatorics and Optimization at the University of Waterloo's Faculty of Mathematics. Edmonds retired in 1999. 
2008/5/2 
Richard Karp, 1935~ 
 “Reducibility Among Combinatorial Problems”, 1972 
 Turing Award in 1985. 
 Harvard University,Bachelor's degree in 1955, Master's degree in 1956, and Ph.D. in applied mathematics in 1959. 
 IBM's Thomas J. Watson Research Center 
 Professor, UC Berkeley, 1968. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. 
74 
Thuật toán đường tăng ngắn nhất 
Ý tưởng: Tìm đường tăng luồng nhờ thực hiện BFS. 
Dễ thực hiện. 
Đường tăng có ít cạnh nhất. 
FOREACH e E 
 f(e)  0 
G f  đồ thị tăng luồng (residual graph) 
WHILE (tồn tại đường tăng) 
 tìm đường tăng P bởi BFS 
 f  augment(f, P) 
 hiệu chỉnh G f 
RETURN f 
ShortestAugmentingPath(V, E, s, t) 
75 
Đường tăng ngắn nhất: Các kết quả 
Bổ đề 1. Trong suốt thuật toán, độ dài đường tăng ngắn nhất không khi nào bị giảm. 
CM sau. 
Bổ đề 2. Sau nhiều nhất m đường tăng ngắn nhất, độ dài đường tăng ngắn nhất sẽ tăng ngặt. 
CM sau. 
Định lý. Thuật toán đường tăng luồng ngắn nhất đòi hỏi thời gian tính O(m 2 n). 
CM 
O(m+n) thời gian để tìm đường ngắn nhất nhờ sử dụng BFS. 
O(m) lần tăng đối với đường đi có đúng k cung. 
Nếu có đường tăng thì luôn tìm được đường tăng là đơn. 1 k < n O(mn) lần tăng 
 Thời gian của thuật toán là O(mn(m+n)) = O(m 2 n). 
76 
Phân tích thuật toán ĐTNN 
Đồ thị mức L G của G=(V, E, s). 
Với mỗi đỉnh v, xác định  (v) là độ dài (theo số cung) của đường đi ngắn nhất từ s đến v. 
Gọi L G = (V, E G ) là đồ thị con của G chỉ chứa các cung (v,w) E với  (w) =  (v) + 1. 
s 
2 
3 
5 
6 
t 
 = 0 
 = 1 
 = 2 
 = 3 
s 
2 
3 
5 
6 
t 
 L G : 
G: 
77 
Phân tích thuật toán ĐTNN 
Đồ thị mức L G của G=(V, E, s). 
Với mỗi đỉnh v, xác định  (v) là độ dài (theo số cung) của đường đi ngắn nhất từ s đến v. 
Gọi L G = (V, E G ) là đồ thị con của G chỉ chứa các cung (v,w) E với  (w) =  (v) + 1. 
Có thể tính L G với thời gian O(m+n) nhờ sử dụng BFS. 
P là đường đi ngắn nhất từ s đến v trên G khi và chỉ khi nó là đường đi từ s đến v trên L G . 
s 
2 
3 
5 
6 
t 
 = 0 
 = 1 
 = 2 
 = 3 
 L: 
78 
Phân tích thuật toán ĐTNN 
Bổ đề 1. Trong suốt thuật toán, độ dài đường tăng ngắn nhất không khi nào bị giảm. 
CM . Giả sử f và f' là luồng trước và sau khi tăng luồng theo đường ngắn nhất. Gọi L và L' là hai đồ thị mức của G f và G f ' 
Chỉ có cung nghịch được bổ sung vào G f ' 
đường đi với cung nghịch có độ dài lớn hơn độ dài trước ■ 
s 
2 
3 
5 
6 
t 
 = 0 
 = 1 
 = 2 
 = 3 
 L 
s 
2 
3 
5 
6 
t 
 L' 
79 
Phân tích thuật toán ĐTNN 
Bổ đề 2. Sau nhiều nhất m đường tăng ngắn nhất, độ dài đường tăng ngắn nhất sẽ tăng ngặt. 
CM: Có ít nhất một cung (cung có kntq bé nhất) bị loại khỏi L sau mỗi lần tăng luồng. 
Không có cung mới được thêm vào L cho đến khi độ dài đường ngắn nhất là tăng ngặt. ■ 
s 
2 
3 
5 
6 
t 
 = 0 
 = 1 
 = 2 
 = 3 
 L 
s 
2 
3 
5 
6 
t 
 L' 
80 
Đường tăng ngắn nhất: Các kết quả 
Bổ đề 1. Trong suốt thuật toán, độ dài đường tăng ngắn nhất không khi nào bị giảm. 
Bổ đề 2. Sau nhiều nhất m đường tăng ngắn nhất, độ dài đường tăng ngắn nhất sẽ tăng ngặt. 
Định lý. Thuật toán đường tăng luồng ngắn nhất đòi hỏi thời gian tính O(m 2 n). 
O(m+n) thời gian để tìm đường ngắn nhất nhờ sử dụng BFS. 
O(m) lần tăng đối với đường đi có đúng k cung. 
 O(mn) lần tăng. 
Chú ý: (mn) lần tăng là cần thiết đối với một số mạng cụ thể. 
Cố gắng tìm cách giảm số lần tăng. 
Cây động O(mn log n) Sleator-Tarjan, 1983 
Ý tưởng khác O(mn 2 ) Dinitz, 1970 
81 
Tổng kết: Lựa chọn đường tăng 
4 qui tắc đầu đòi hỏi khả năng thông qua nằm trong khoảng từ 0 đến C. 
Phương pháp 
Số lần tăng 
Augmenting path 
nC 
Max capacity 
m log C 
Capacity scaling 
m log C 
Shortest path 
mn 
Thời gian tính 
mnC 
m log C (m + n log n) 
m 2 log C 
m 2 n 
Improved shortest path 
mn 
mn 2 
Improved capacity scaling 
m log C 
mn log C 
82 
Lịch sử phát triển 
Dantzig 
Tác giả 
Simplex 
Phương pháp 
Big-Oh 
mn 2 U 
1951 
Năm 
Ford, Fulkerson 
Augmenting path 
mnU 
1955 
Edmonds-Karp 
Shortest path 
m 2 n 
1970 
Dinitz 
Shortest path 
mn 2 
1970 
Edmonds-Karp, Dinitz 
Capacity scaling 
m 2 log U 
1972 
Dinitz-Gabow 
Capacity scaling 
mn log U 
1973 
Karzanov 
Preflow-push 
n 3 
1974 
Sleator-Tarjan 
Dynamic trees 
mn log n 
1983 
Goldberg-Tarjan 
FIFO preflow-push 
mn log (n 2 / m) 
1986 
. . . 
. . . 
. . . 
. . . 
Goldberg-Rao 
Length function 
m 3/2 log (n 2 / m) log Umn 2/3 log (n 2 / m) log U 
1997 
QUESTIONS? 
83