LUỒNG CỰC ĐẠI
Chúng ta có thể mô hình hóa một bản đồ đường đi bằng một đồ thị có hướng nhằm tìm
ra một đường đi ngắn nhất từ nơi này đến nơi khác, chúng ta cũng có thể biểu diễn một
đồ thị có hướng như một “mạng vận tải” và sử dụng nó để trả lời những câu hỏi về
những luồng vật chất (material flows). Hãy hình dung một lượng vật chất (material
coursing) bắt đầu điểm phát - nơi vật chất được tạo ra - chạy ngang qua một hệ thống
đến điểm thu (SINK) - nơi nó được tiêu thụ. Lượng vật chất tạo ra ở điểm phát bằng
lượng vật chất ở điểm thu. “Luồng” vật chất tại mọi điểm trong hệ thống được xem là
lượng vật chất di chuyển. Những mạng vận tải có thể được sử dụng để mô phỏng các
luồng chất lỏng chảy qua các ống dẫn, các bộ phận được kết nối với nhau qua dây
chuyền lắp ráp, dòng điện chạy qua các mạng điện, thông tin truyền qua các mạng
truyền thông,…
Mỗi một cung trong mạng vận tải tương ứng với một ống dẫn(conduit) vật chất. Mỗi
ống dẫn có khả năng chứa riêng, nó cho biết lượng vật chất tối đa có thể vận chuyển
qua ống dẫn đó. Ví dụ có thể chuyển 200 gallons chất lỏng qua một ống dẫn trong một
giờ hoặc dòng điện 20 amperes qua dây điện. Các đỉnh là chỗ nối của các ống dẫn
(ngoại trừ nguồn và đích), các luồng vật chất qua các đỉnh mà không hợp lại. Hay nói
cách khác, lượng vật chất đi vào một đỉnh phải bằng lượng vật chất đi ra từ đỉnh
đó.Chúng ta gọi thuộc tính này là “sự cân bằng luồng”, và nó tương tự định luật của
Kirchhoff khi vật chất là dòng điện.
Trong bài toán Luồng cực đại, chúng tôi muốn tính toán lượng vật chất lớn nhất có thể
vận chuyển từ điểm phát đến điểm thu mà không vi phạm bất cứ ràng buộc nào. Đó là
một trong những bài toán đơn giản nhất liên quan đến mạng vận tải, và như chúng ta
tìm hiểu trong chương này thì vấn đề trên có thể được giải quyết bằng những thuật
toán hiệu. Hơn nữa, các phương pháp cơ bản sử dụng trong thuật toán luồng cực đại có
thể được ứng dựng để giải quyết các bài toán về mạng vận tải khác.
Chương này trình bày 2 phương pháp để giải quyết bài toán luồng cực đại. Phần 26.1
trình bày khái quát các khái niệm về mạng vận tải và luồng, định nghĩa bài toán luồng
cực đại. Phần 26.2 mô tả phương pháp kinh điển để tìm matching cực đại trong đồ thị
bipartite vô hướng. Trong phần 26.3, 26.4 trình bày phương pháp the push-relabel,
nó là cơ sở để đưa ra các thuật toán nhanh nhất đối với bài toán mạng vận tải. Phần

26.5 bao gồm thuật toán "relabel-to-front", một sự bổ sung cụ thể cho phương the
push-relabel - phương pháp mà có độ phức tạp tính toán O(V
3
). Mặc dù thuật toán này
không phải là thuật toán nhanh nhất nhưng nó mô tả một vài phương pháp sử dụng
trong các thuật toán nhanh nhất xác định đường tiệm cận và nó có hiệu quả trong thực
tiễn.
26.1 Mạng vận tải
Trong phần này, chúng tôi đưa ra một định nghĩa dựa trên một đồ thị được giả định là
đúng về mạng vận tải, thảo luận các thuộc tính của chúng và định nghĩa bài toán luồng
cực đại một cách chính xác. Chúng tôi cũng giới thiệu một vài kí hiệu có ích.
1
Mạng vận tải và luồng
Một mạng vận tải G = (V,E) là một đồ thị có hướng, Trong đó, mỗi cung (u,v)∈E có
một khả năng thông qua c(u,v) ≥ 0. Nếu (u,v)∉E, chúng ta cho c(u,v) = 0. Chúng ta
cần phân biệt 2 đỉnh trong một mạng vận tải: đỉnh phát s và đỉnh thu t. Để thuận tiện
chúng ta giả sử rằng mỗi đỉnh đều nằm trên đường từ đỉnh phát đến đỉnh thu. Nghĩa là,
với mỗi đỉnh v∈V, đều tồn tại đường đi s → v → t. Vì vậy đồ thị là liên thông và |E| ≥
|V| - 1. Hình 26 biểu diễn một ví dụ về mạng vận tải.
Bây giờ chúng ta có định nghĩa về luồng chính thức hơn. Cho G = (V,E) là một mạng
vận tải với khả năng thông qua C. Cho s là đỉnh phát và t là đỉnh thu của mạng. Một
luồng tổng trong G là một hàm có giá trị thực ƒ: V
x
V → R thỏa mãn ba tính chất sau:
Tính ràng buộc về khả năng thông qua của luồng (Capacity constraint):
∀u,v ∈ V: ƒ(u,v) ≤ c(u,v)
Tính đối xứng lệch (Skew symmetry):
∀u,v ∈ V: ƒ(u,v) = - ƒ(v,u)
Tính cân bằng luồng (Flow conservation):
∀u ∈ V\{s,t}:

Khối lượng ƒ(u,v) (có thể nhận giá trị 0 hoặc âm) được gọi là luồng từ đỉnh u đến đỉnh
v. Giá trị của luồng ƒ được xác định như sau
Đó là tổng giá trị luồng ra khỏi đỉnh phát (kí hiệu trị tuyệt đối | | biểu thị giá trị của
luồng chứ không phải là biểu thị của giá trị tuyệt đối hay lực lượng của một tập hợp).
Trong bài toán luồng cực đại, cho một mạng vận tải G với đỉnh phát s và đỉnh thu t.
Hãy tìm một luồng có giá trị cực đại từ đỉnh s đến đỉnh t.
Hình 26.1 Mạng vận tải
Hình 26.1 (a) Mạng vận tải G = (V,E) cho bài toán vận chuyển của công ty Lucky Puck. Nhà máy
Vancouver là đỉnh phát s và kho Winnipeg là đỉnh thu t. Bóng khúc côn cầu (Pucks) được vận chuyển
ngang qua các thành phố trung gian, nhưng chỉ c(u,v) thùng đựng bóng(crates) mỗi ngày có thể đi từ
thành phố u đến thành phố v. Mỗi cung được gán một nhãn gọi là khả năng thông qua của cung đó.
2
Hình 26.1 (b) Một luồng
ƒ
trong G có giá trị |
ƒ
| = 19. Chỉ những luồng có giá trị thực mới được biểu
diễn. Nếu
ƒ
(u,v) > 0 thì cung (u,v) được gán nhãn như sau
ƒ
(u,v) /c(u,v). (Dấu gạch chéo / chỉ
đơn thuần được sử dụng để tách luồng và khả năng thông qua của luồng; nó không phải là biểu
thị của phép chia.) Nếu
ƒ
(u,v)
≤
0 thì cung (u,v) chỉ được gán nhãn bởi khả năng thông qua của
nó.
Trước khi xem một ví dụ về bài toán mạng vận tải, chúng ta hãy khảo sát nhanh 3 tính

chất của luồng:
Tính ràng buộc về khả năng thông qua của luồng nói một cách đơn giản là Luồng tổng
từ đỉnh này đến đỉnh khác không được vượt quá khả năng thông qua đã được cho của
luồng đó.
Tính đối xứng lệch nghĩa là luồng tổng từ đỉnh u đến đỉnh v là đối xứng với luồng
trong hướng ngược lại.
Tính cân bằng luồng tức là tổng giá trị của luồng đi ra từ một đỉnh (ngoại trừ đỉnh phát
và đỉnh thu) là bằng 0. Dựa vào tính đối xứng lệch, chúng ta có thể viết lại tính cân
bằng luồng như sau:
∀ v ∈V\{s,t}. Tức là, tổng giá trị của luồng đi vào một đỉnh bằng 0.
Khi cả (u,v) lẫn (v,u) đều không thuộc E thì có thể không có luồng nào giữa u và v. khi
đó:
ƒ(u,v) = ƒ(v,u) = 0. (Bài tập 26.1-1 yêu cầu chứng minh tính chất này)
Điều cuối cùng liên quan đến tính chất của luồng mà chúng ta cần quan tâm là giá trị.
Tổng giá trị thực của luồng đi vào một đỉnh được xác định bởi
Tổng luồng dương đi ra từ một đỉnh được định nghĩa ngược lại. Chúng ta xác định
tổng giá trị của luồng tại một đỉnh là bằng tổng giá trị thực của luông đi ra từ một đỉnh
trừ đi tổng giá trị thực của luồng đi vào từ một đỉnh. Sự thể hiện tính cân bằng luồng là
ở chỗ tổng giá trị của luồng đi vào một đỉnh (ngoại trừ đỉnh phát và đỉnh thu) phải
bằng với tổng giá trị luồng đi ra từ đỉnh đó. Tính chất này (tổng giá trị của mạng vận
tải tại một đinh phải bằng 0) thường được xem như là “luồng vào bằng luồng ra.”
Một ví dụ về luồng
Một mạng vận tải có thể mô phỏng bài toán vận chuyển như trong hình 26.1(a). Công
ty Lucky Puck có một nhà máy (đỉnh phát s) ở Vancouver sản xuất bóng khúc côn cầu
trên băng và có một kho (đỉnh thu t) ở Winnipeg để cất giữ chúng. Lucky Puck thuê
công ty khác vận chuyển bóng từ nhà máy đến kho. Bởi vì xe tải chạy trên những lộ
trình (cung) xác định giữa các thành phố(đỉnh) và có giới hạn về khả năng chuyên chở.
Lucky Puck có thể vận chuyển tới mức tối đa khả năng thông qua c(u,v) mỗi ngày giữa
mỗi cặp thành phố u và v (hình 26.1(a)). Lucky Puck không có quyền điều khiển trên
3

những lộ trình đó và các khả năng thông qua của các lộ trình vì vậy không thể thay đổi
mạng vận tải biểu diễn trong hình 26.1(a). Mục đích của họ là xác định số lượng
Thùng lớn nhất p có thể được vận chuyển mỗi ngày và sau đó đưa ra giá trị này vì
không có nơi nào sản xuất bóng nhiều hơn họ có thể vận chuyển đến kho. Lucky Puck
không quan tâm mất thời gian bao lâu để vận chuyển bóng từ nhà máy đến kho; họ chỉ
quan tâm đến số lượng thùng p rời nhà máy và số lượng thùng p đến kho mỗi ngày.
Nhìn bề ngoài, nó dường như thích hợp để biểu diễn “mạng” vận chuyển với một
luồng trong mạng này bởi vì số lượng thùng vận chuyển mỗi ngày từ thành phố này
đến thành phố khác là vấn đề đối với tính ràng buộc về khả năng thông qua của luồng.
Ngoài ra, sự cân bằng luồng cũng phải được tuân theo, tức là số lượng bóng đưa vào
một thành phố trung gian phải bằng với số lượng bóng đưa ra từ thành phố đó. Mặc
khác, các thùng có thể chất đống tại các thành phố trung gian.
Tuy nhiên có một sự khác biệt khó thấy giữa sự vận chuyển (shipments) và luồng
(flows). Lucky Puck có thể vận chuyển bóng tử Edmonton đến Calgary và họ cũng có
thể vận chuyển bóng từ Calgary đến Edmonton. Giả sử rằng họ vận chuyển 8 thùng
mỗi ngày từ Edmonton (v
1
trong hình 26.1) đến Calgary (v
2
) và 3 thùng mỗi ngày từ
Calgary đến Edmonton. Dường như có thể biểu diễn sự vận chuyển đó một cách trực
tiếp bằng luồng nhưng thực tế chúng ta không thể. Vì sự ràng buộc của tính chất Đối
xứng lệch yêu cầu rằng ƒ(v
1
,v
2
) = - ƒ(v
2
,v
1

), nhưng trong trường hợp này là không
đúng nếu chúng ta coi ƒ(v
1
,v
2
) = 8 và ƒ(v
2
,v
1
) = 3
Lucky Puck có thể nhận thấy rằng thật là vô ích để tìm cách vận chuyển 8 thùng từ
Edmonton đến Calgary và 3 thùng từ Calgary đến Edmonton trong khi họ có thể đạt
được mục đích như vậy bằng cách vận chuyển 5 thùng từ Edmonton đến Calgary và 0
thùng từ Calgary đến Edmonton (và có lẽ sử dụng nhiều tài nguyên hơn trong quá trình
xử lí). Chúng ta biểu diễn bằng một luồng:
Ta có ƒ(v
1
,v
2
) = 5 và ƒ(v
2
,v
1
) = -5. Trong thực tế, 3 trong 8 thùng mỗi ngày từ v
1
đến v
2
bị hủy bỏ bởi 3 thùng mỗi ngày từ v
2
đến v

1
.
Nói chung, việc hủy bỏ cho phép chúng ta biểu diễn sự vận chuyển giữa hai thành phố
bằng một luồng có giá trị dương theo tối đa một trong hai cung giữa các đỉnh tương
ứng. Tức là, trong mọi trường hợp nếu bóng được vận chuyển theo cả hai hướng giữa
hai thành phố thì ta có thể thay đổi bằng cách hủy bỏ thành một trường hợp tương ứng
trong đó bóng được vận chuyển chỉ theo một hướng; hướng có giá trị dương.
Nói một cách khác, cho một luồng ƒ phát sinh do sự vận chuyển vật chất, chúng ta
không thể xây dựng lại một cách chính xác sự vận chuyển đó. Nếu chúng ta biết
ƒ(u,v)=5 thì luồng này có thể tồn tại bởi vì 5 đơn vị (thùng bóng) được vận chuyển từ u
tới v hoặc 8 đơn vị được vận chuyển từ u tới v và 3 đơn vị được vận chuyển ngược trở
lại từ v tới u. Như vậy, đối với bất kỳ cặp đỉnh nào, chúng ta sẽ không quan tâm sự vận
chuyển vật chất thật sự diễn ra như thế nào mà chỉ quan tâm đến số lượng hàng được
chuyển giữa chúng. Còn nếu chú ý đến sự vận chuyển cơ bản (thật sự) thì nên dùng
một cách mô phỏng khác, cách mà lưu lại được thông tin về sự vận chuyển theo cả hai
hướng.
4
Phương pháp hủy bỏ (cancellation) sẽ xuất hiện trong toàn bộ thuật toán của chương
này. Giả sử rằng cung (u,v) tương ứng với một luồng có giá trị ƒ(u,v). Trong quá trình
khai triển thuật toán, chúng ta có thể tăng luồng trên cung (v,u) thêm giá trị d. Trong
toán học, thao tác đó làm giảm ƒ(u,v) một lượng d. Theo khái niệm, chúng ta có thể coi
giá trị d như là giá trị hủy bỏ bớt của luồng trên cạnh (u.v).
Mạng có nhiều đỉnh phát và đỉnh thu
Một bài toán luồng cực đại có thể có nhiều hơn một đỉnh phát và đỉnh thu. Ví dụ, Công
ty Lucky Puck có thể có một tập m nhà máy {s
1
,s
2
,….s
m

} và một tập n kho chứa {t
1
,t
2
,
….t
m
} như trong hình 26.2(a). May mắn là bài toán này không khó hơn bài toán luồng
cực đại thông thường.
Chúng ta có thể quy bài toán xác định một luồng cực đại trong một mạng nhiều đỉnh
phát và đỉnh thu về bài toán luồng cực đại thông thường. Hình 26.2 cho thấy mạng có
nhiều đỉnh phát và đỉnh thu (a) được chuyển thành mạng vận tải thông thường (b) chỉ
có một đỉnh phát và một đỉnh thu như thế nào. Chúng ta thêm một Supersource s và
một cung có hướng (s,s
i
) với khả năng thông qua c(s,s
i
) = ∞, ∀i = 1, 2, ,m. Chúng ta
cũng tạo một Supersink t và thêm vào một cung có hướng (t
i
,t) với khả năng thông
qua c(t
i
,t) = ∞, ∀i = 1, 2, ,n. Bằng trực giác, bất kỳ luồng nào trong mạng như hình (a)
cũng tương ứng với một luồng trong mạng như hình (b). Đỉnh phát đơn s cung cấp
nhiều luồng như yêu cầu cho các đỉnh phát s
i
.Tương tự, đỉnh thu đơn t tiếp nhận nhiều
luồng từ các đỉnh thu t
i

. Bài tập 26.1-3 yêu cầu chứng minh hai vấn đề trên là tương
đương.
Hình 26.2
5
Hình 26.2 Chuyển đổi bài toán luồng cực đại với nhiều đỉnh phát và đỉnh thu về bài toán với một
đỉnh phát và một đỉnh thu.
(a) Một mạng vận tải với 5 đỉnh phát S ={s
1
, s
2
, s
3
, s
4
, s
5
} và ba đỉnh thu T={t
1
, t
2
, t
3
}.
(b) Một mạng vận tải tương ứng với một đỉnh phát và một đỉnh thu. Chúng ta thêm một
Supersource s và một cung với khả năng thông qua vô hạn từ s đến mỗi đỉnh phát s
i
,
∀
i = 1, ,5.
Đồng thời cũng thêm một Supersink t và một cung với khả năng thông qua vô hạn từ mỗi đỉnh thu

t
i
,
∀
i = 1, ,3 đến t.
Làm việc với luồng
Chúng ta sẽ tiếp xúc với một vài hàm (như ƒ), hàm này nhận đối số là 2 đỉnh trong
mạng vận tải. Trong chương này, chúng ta sẽ sử dụng một kí hiệu tổng ẩn trong đó mỗi
đối số hoặc cả hai hoặc có thể là một tập hợp các đỉnh với cách hiểu là giá trị biểu hiện
là tổng của tất cả khoảng cách có thế có khi thay thế các đối số với thành phần tương
ứng. Ví dụ, nếu X và Y là tập tất cả các đỉnh thì:
Vì vậy, sự ràng buộc của tính chất cân bằng luồng có thể được diễn tả như là điều kiện
ƒ(u,V) = 0, ∀ u ∈V\{s,t}. Tương tự, để thuận tiện, chúng ta sẽ bỏ qua các điểm nối cố
định khi chúng có thể được sử dụng trong kí hiệu hàm ẩn. Ví dụ, trong phương trình
ƒ(s,V\s) = ƒ(s,V), thuật ngữ V\s nghĩa là tập V\{s}.
Kí hiệu tập ẩn thường làm đơn giản hóa các phương trình liên quan đến luồng. Bổ đề
sau (phần chứng minh được đặt trong bài tập 26.1-4) đưa ra vài đồng nhất thức
(identities) thường xuất hiện nhất, chúng có liên quan đến luồng và kí hiệu tập ẩn.
Bổ đề 26.1
Cho G = (V,E) là một mạng vận tải và cho ƒ là một luồng trong G. Khi đó đẳng thức
sau khẳng định:
1. ∀ X ⊆ V, ta có: ƒ(X,X) = 0.
2. ∀ X,Y ⊆ V, ta có: ƒ(X,Y) = - ƒ(Y,X).
3. ∀ X,Y,Z ⊆ V với ta có các tổng: ƒ(X∪Y,Z) = ƒ(X,Z) + ƒ(Y,Z)
và ƒ(Z,X∪Y) = ƒ(Z,X) + ƒ(Z,Y).
Xét một ví dụ làm việc với kí hiệu tổng ẩn, chúng ta có thể chứng minh rằng giá trị của
một luồng là tổng luồng đi vào đỉnh phát; tức là:
|ƒ| = ƒ(V,t). (26.3)
Dễ dàng nhận thấy đặc tính này được khẳng định. Do tính chất cân bằng luồng nên tất
cả các đỉnh (ngoại trừ đỉnh phát và đỉnh thu) có giá trị luồng dương đi vào và đi ra

bằng nhau. Theo định nghĩa, đỉnh phát có một tổng luồng có giá trị lớn hơn 0; tức là,
có nhiều luồng dương đi ra từ đỉnh phát hơn là đi vào. Ngược lại, đỉnh thu là đỉnh có
thể có một tổng luồng có giá trị bé hơn 0. Tức là có nhiều luồng dương đi vào đỉnh
phát hơn là đi ra. Điều đó được chứng minh như sau:
6
Trong phần sau của chương, chúng ta sẽ vận dụng (generalize) kết quả này (Bổ đề
26.5).
Bài tập
26.1-1. Sử dụng định nghĩa về luồng, chứng minh rằng: nếu (u,v) ∉ E và (v,u) ∉E thì
ƒ(u,v) = ƒ(v,u) = 0
26.1-2. Chứng minh rằng, bất cứ đỉnh v nào (ngoại trừ đỉnh phát và đỉnh thu) thì tổng
số luồng dương (the total positive flow) đi vào v phải bằng tổng số luồng dương đi ra
khỏi v.
26.1-3. Mở rộng các tính chất và định nghĩa về luồng cho bài toán có nhiều đỉnh phát
và đỉnh thu. Hãy chỉ ra rằng bất kỳ luồng nào trong một mạng vận tải nhiều đỉnh phát
và đỉnh thu đều tương ứng với một luồng có cùng giá trị trong mạng có một đỉnh phát
và một đỉnh thu (mạng này thu được bằng cách thêm vào một Supersource và một
supersink).
26.1-4. Chứng minh bổ đề 26.1
26.1-5. Cho mạng vận tải G = (V,E) và luồng ƒ như hình 26.1(b), hãy xác định một cặp
tập con X, Y ⊆ V: ƒ(X,Y) = -ƒ(V\{X,Y}). Sau đó, hãy xác định một cặp tập con X, Y
⊆ V: ƒ(X,Y) ≠ -ƒ(V\{X,Y}).
26.1-6. Cho một mạng vận tải G = (V,E). ƒ
1
, ƒ
2
là các hàm từ V
x
V đến R. Tổng luồng
ƒ

1
+ ƒ
2
là hàm từ V
x
V đến R xác định bởi
(f
1
+ f
2
)(u, v) = f
1
(u, v) + f
2
(u, v) (26.4)
∀u,v∈V. Nếu f
1
và f
2
là các luồng trong G thì tính chất nào trong ba tính chất của luồng
mà luồng tổng f
1
+ f
2
phải thõa mãn? và tính chất nào là trái ngược với nó?
26.1-7. Cho ƒ là một luồng trong mạng và cho α là một số thực. Tích vô hướng αƒ là
một hàm từ V
x
V đến R xác định bởi:
(αƒ)(u,v) =α . ƒ(u,v)

Chứng minh rằng các luồng đó tạo thành một tập lồi (a convex set). Tức là, chỉ ra rằng
nếu ƒ
1
và ƒ
2
là các luồng thì ta có αƒ
1
+ (1- α)ƒ
2
, ∀α ∈[0,1].
26.1-8. Phát biểu bài toán luồng cực đại như là một bài toán lập trình tuyến tính
(linear-programming).
26.1-9. Giáo sư Adam có hai người con nhưng không may là chúng lại ghét nhau. Vấn
đề là chính thái độ quá gay gắt đó không chỉ khiến chúng không chịu đi học cùng nhau
mà còn không chịu đi đến bất cứ chỗ nào mà đứa kia đã đến trong cùng ngày. Chúng
không có vấn đề gì khi vượt qua các con đường tại góc đường. May thay, nhà của giáo
sư và trường học đều nằm ở các góc đường đó. Nhưng Giáo sư không chắc liệu có thể
7
gởi cả hai người con đến học cùng một trường hay không. Giáo sư có một bản đồ về
thành phố. Hãy chỉ ra cách giải quyết bài toán trên nếu cả hai người con có thể đi học
cùng trường như một bài toán về luồng cực đại.
26.2 Phương pháp Ford-Fulkerson
Phần này trình bày phương pháp Ford-Fulkerson để giải quyết bài toán luồng cực đại.
Chúng ta xem nó là một “phương pháp” hơn là một “thuật toán” bởi vì nó chứa thêm
vài sự bổ sung khác với số lần thực hiện khác. Phương pháp Ford-Fulkerson phụ thuộc
vào ba khái niệm quan trọng và liên quan đến các bài toán và thuật toán về luồng:
mạng dư (residual networks), đường tăng (augmenting paths), và lát cắt (cuts). Các
khái niếm này là thiết yếu đối với định lý lát cắt cực tiểu luồng cực đại (định lý 26.7),
định lý này mô tả giá trị của một luồng cực đại trong các thuật ngữ về lát cắt của mạng
vận tải. Chúng ta kết thúc chương này bằng một bổ sung rõ ràng về phương pháp Ford-

Fulkerson và phân tích thời gian chạy của nó.
Phương pháp Ford-Fulkerson là lặp đi lặp lại. Chúng ta bắt đầu với ƒ(u,v) = 0,
∀u,v ∈V. Cho một luồng ban đầu có giá trị 0. Tại mỗi lần lặp lại, chúng ta tăng giá trị
của luồng bằng cách tìm một “đường tăng”. Chúng ta có thể nghĩ một cách đơn giản
“đường tăng” là một đường từ đỉnh phát s đến đỉnh thu t, theo đường đó chúng ta có
thể gởi nhiều luồng hơn và sau đó tăng luồng theo đường này. Chúng ta lặp lại quá
trình này cho đến khi không còn tìm thấy đường tăng nữa. Định lý lát cắt cực tiểu
luồng cực đại chỉ ra rằng khi kết thúc quá trình này sẽ thu được một luồng cực đại.
FORD-FULKERSON-METHOD(G, s, t)
1 luồng ban đầu f nhận giá trị 0
2 while tồn tại một đường tăng p
3 do tăng luồng f theo p
4 return f
Mạng còn dư (residual networks)
Cho một mạng vận tải và một luồng, mạng còn dư gồm các cung còn có thể tăng thêm
tổng luồng. Nói một cách rõ hơn, giả sử rằng chúng ta có một mạng vận tải G = (V,E)
với đỉnh phát s và đỉnh thu t. Cho f là một luồng trong G và xem cặp các đỉnh u,v∈V.
Dung lượng tổng luồng thêm vào mà chúng ta có thể đẩy từ u đến v trước khi vượt quá
khả năng thông qua c(u,v) chính là khả năng thông qua còn dư của (u,v), xác định bởi:
c
f
(u,v) = c(u,v) − f(u,v) (26.5)
Ví dụ, nếu c(u,v) = 16 và f(u,v) = 11 thì chúng ta có thể tăng f(u,v) thêm c
f
(u,v)=5 đơn
vị trước khi vượt quá khả năng thông qua trên cung (u,v). Khi luồng f(u,v) âm thì khả
năng thông qua còn dư c
f
(u,v) là lớn hơn khả năng thông qua c(u,v). Ví dụ, nếu c(u,v)
= 16 và f(u,v) = -4 thì khả năng thông qua còn dư c

f
(u,v) là 20. Chúng ta có thể hiểu
tình huống này như sau. Có một luồng 4 đơn vị từ v tới u mà chúng ta có thể hủy bỏ
bằng cách đẩy vào một luồng 4 đơn vị từ u tới v. Sau đó chúng ta đẩy một luồng 16
đơn vị từ u đến v trước khi vi phạm đến sự ràng buộc về khả thông qua trên cung (u,v).
Vì vậy, chúng ta đã đẩy vào một luồng 20 đơn vị, bắt đầu với luồng f(u,v) = -4.
8
Hình 26.3
(a) Mạng vận tải G và luồng f tường ứng trong hình(b)
(b) Mạng còn dư G
f
với đường tăng p(được tô đậm); khả năng thông qua còn dư của nó là
c
f
(p) = c
f
(v2,v3) = 4.
(c) Luồng trong G là kết quả từ đường tăng theo p bởi khả năng thông qua còn dư của nó.
(d) Mạng còn dư sinh ra bởi luồng trong (c).
Cho một mạng vận tải G = (v,E) và một luồng f, mạng còn dư của G sinh ra bởi f là G
f
= (V, E
f
), trong đó:
E
f
= {(u, v) ∈ V
x
V : c
f

(u, v) > 0}
Tức là, mỗi cung của mạng còn dư hay cung còn dư có thể nhận một luồng có giá trị
lớn hơn 0. Hình 26.1(b) và 26.3(b) cho thấy mạng còn dư tương ứng G
f
Các cung thuộc E
f
cũng là các cung thuộc E hoặc ngược lại. Nếu f(u,v) < c(u,v) với
(u,v) ∈E thì c
f
(u, v) = c(u, v) - f(u, v) > 0 và (u,v) ∈E
f
. Nếu f(u,v) > 0 với (u,v) ∈E thì
f(v,u) < 0. Trong trường hợp này c
f
(v, u) = c(v,u) - f(v,u) > 0 va (v,u) ∈E. (Hay nói
cách khác, cung (u,v) có thể là một cung còn dư trong E
f
thậm chí nếu nó không phải là
cung trong E, đó là trường hợp E
f
∉E. Mạng còn dư trong hình 26.3(b) chứa một vài
cung như vậy, các cung đó không có trong mạng ban đầu, như (v
1
, s) and (v
2
, v
3
). Như
vậy cung (u,v) xuất hiện chỉ trong G
f

nếu (v,u) ∈E và có một luồng dương từ v tới u.
Bởi vì tổng luồng f(u,v) từ u tới v là âm nên c
f
(u, v) = c(u, v) - f(u, v) là dương và (u,v)
∈E
f
). Nếu cả (u,v) và (v,u) không xuất hiện trong mạng ban đầu thì:
c(u,v) = c(v,u) = 0.
Chúng ta kết luận rằng cung (u,v) có thể xuất hiện chỉ trong mạng còn dư nếu có ít
nhất một trong hai cung (u,v) hoặc (v,u) xuất hiện trong mạng ban đầu, vì vậy ta có:
|E
f
| ≤ 2|E|.
9
Quan sát thấy rằng mạng còn dư G
f
cũng chính là một mạng vận tải với các khả năng
thông qua được cho bởi c
f
. Bổ đề sau chỉ ra một luồng trong một mạng còn dư liên
quan với một luồng trong mạng vận tải ban đầu như thế nào.
Bổ đề 26.2
Cho G = (V,E) là một mạng vận tải với điểm phát s và điểm thu t, cho f là một luồng
trong G. Cho G
f
là mạng còn dư của G sinh ra bởi f và f’ là một luồng trong G
f ’
Khi đó
luồng tổng f + f’ xác định bởi phương trình (26.4) là một luồng trong G với giá trị
|f + f'| = |f| + |f'|.

Chứng minh Chúng ta phải kiểm tra tính đối xứng, tính ràng buộc về khả năng thông
qua và tính cân bằng luồng có được tuân theo hay không. Đối với tính đối xứng, chú ý
rằng ∀ u,v ∈ V, ta có:
(f + f')(u, v) = f(u, v) + f'(u, v)
= -f(v, u) - f'(v, u)
= -(f(v, u) + f'(v, u))
= -(f + f')(v, u).
Đối với tính ràng buộc về khả năng thông qua, chú ý rằng: f'(u, v) ≤ c
f
(u, v), ∀ u, v ∈V.
Theo phương trình (26.5), nên:
(f + f')(u, v) = f(u, v) + f'(u, v)
≤ f(u, v) + (c(u, v) - f(u, v))
= c(u, v) .
Đối với tính cân bằng luồng, chú ý rằng: ∀ u ∈V\{s,t}, ta có:
Cuối cùng, ta có:
Đường tăng
Cho một mạng vận tải G = (V,E) và luồng. Một đường tăng là một đường đơn giản từ s
đến t trong một mạng còn dư Gf. Theo định nghĩa về mạng còn dư, mỗi cung (u,v) trên
một đường tăng nhận thêm vài luồng dương từ u đến v mà không vi phạm tính ràng
buộc về khả năng thông qua trên cung đó.
Đường tô đậm trong hình 26.3(b) là một đường tăng. Xem mạng còn dư Gf trong hình
đó như là một mạng vận tải, chúng ta có thể tăng luồng qua mỗi cung theo đường tô
đậm lên 4 đơn vị mà không vi phạm tính ràng buộc về khả năng thông qua vì khả năng
10
thông qua còn dư nhỏ nhất trên đường là cf(v
2
,v
3
)=4. Dung lượng tối đa mà chúng ta có

thể tăng cho luồng trên mỗi cung theo đường tăng p, cho bởi:
c
f
(p) = min{c
f
(u, v): (u, v) is on p}.
Bổ đề sau xây dựng đối số trên chính xác hơn
(Phần chứng minh của bổ đề được xem như bài tập (26.2-7))
Bổ đề 26.3
Cho G = (V,E) là một mạng vận tải, f là một luồng trong G và cho p là đường tăng
trong Gf. Định nghĩa một hàm f
p
: V
x
V → R bởi:
Vì vậy, f
p
là một luồng trong Gf với giá trị |f
p
| = cf(p) > 0
Hệ quả sau chỉ ra rằng nếu chúng ta cộng thêm f
p
vào f thì sẽ nhận được luồng khác
trong G mà giá trị của nó là gần hơn với giá trị cực đại. Hình 26.3(c) cho thấy kết quả
khi cộng thêm f
p
vào đường tăng trong hình 26.3(b) đối với luồng f từ hình 26.3(a).
Hệ quả 26.4
Cho G = (V.E) là một mạng vận tải, f là một luồng trong G và cho p là một đường tăng
trong Gf. Cho f

p
được xác định như phương trình (26.6).
Định nghĩa một hàm f’: V
x
V → R như sau: f’ = f + f
p

Vì f’ là một luồng trong G với giá trị | f' | = | f | + |f
p
| > | f |.
Chứng minh trực tiếp từ các bổ đề 26.2 và 26.3
Lát cắt của mạng vận tải
Phương pháp Ford-Fulkerson lặp lại việc tăng luồng theo các đường tăng cho đến khi
một luồng cực đại được tìm thấy. Định lý lát cắt cực tiểu luồng cực đại (chúng ta sẽ
chứng minh ngắn gọn) phát biểu rằng một luồng là cực đại nếu và chỉ nếu mạng còn
dư của nó không chứa đựng đường tăng nào. Tuy nhiên, để chứng minh định lý này
trước tiên chúng ta phải tìm hiểu khái niệm về lát cắt của một mạng vận tải.
Hình 26.4
Hình 26.4. Một lát cắt (S,T) trong một mạng vận tải của hình 26.1(b), với S ={s,v
1
,v
2
} và T ={v
3
,v
4
,t}.
Các đỉnh trong S là đen và các đỉnh trong T là trắng. Tổng luồng qua (S,T) là f(S,T) = 19 và khả
năng thông qua của lát cắt là c(S,T) = 26
Một lát cắt (S,T) của một mạng vận tải G = (V,E) là một sự phân chia của V thành S và

T (T=V\S), trong đó s ∈ S và t ∈ T (Định nghĩa này tương tự với định nghĩa về lát cắt
11
mà chúng ta sử dụng cho các cây khung nhỏ nhất trong chương 23, chỉ khác là ở đây
chúng ta đang cắt một đồ thị có hướng. Và chúng ta khẳng định rằng s ∈ S và t ∈ T)
Nếu f là một luồng thì luồng tổng đi qua lát cắt (S,T) được định nghĩa là f(S,T). Khả
năng thông qua của lát cắt (S,T) là c(S,T). Một lát cắt cực tiểu của một mạng là một lát
cắt mà khả năng thông qua là nhỏ nhất trong tất cả các lát cắt của mạng.
Hình 26.4 cho thấy lát cắt ({s,v
1
,v
2
},{v
3
,v
4
,t}) trong mạng vận tải của hình 26.1(b).
Luồng tổng đi qua lát cắt này là:
f(v
1
, v
3
) + f(v
2
, v
3
) + f(v
2
, v
4
) = 12 + (-4) + 11 = 19, và khả năng thông qua của nó là:

c(v
l
, v
3
) + c(v
2
, v
4
) = 12 + 14 = 26.
Quan sát thấy rằng tổng luồng đi qua một lát cắt có thể bao gồm các luồng âm giữa các
đỉnh, nhưng khả năng thông qua của một lát cắt thì bao gồm các giá trị không âm. Nói
cách khác, tổng luồng đi qua một lát cắt (S,T) gồm có các luồng dương theo cả hai
hướng; luồng dương từ S đến T được cộng thêm vào trong khi luồng dương từ T đến S
bị trừ đi. Mặt khác, khả năng thông qua của một lát cắt (S,T) được tính chỉ gồm các
cung đi từ S đến T. Các cung đi từ T đến S không được tính đến trong sự tính toán của
c(S,T).
Bổ đề sau chỉ ra rằng tổng luồng đi qua bất cứ lát cắt nào cũng đều như nhau và nó
bằng giá trị của luồng.
Bổ đề 26.5
Cho f là một luồng trong mạng vận tải G với đỉnh phát s và đỉnh thu t, cho (S,T) là một
lát cắt của G. Khi đó tổng luồng đi qua (S,T) là f(S,T) = | f |
Chứng minh: chú ý rằng f(S\{s};V) = 0 bởi tính chất cân bằng luồng, ta có:
f(S, T) = f(S, V) - f(S, S) (theo bổ đề 26.1, phần (3))
= f(S, V) (theo bổ đề 26.1, phần (1))
= f(s, V) +f(S - s, V) (theo bổ đề 26.1, phần (3))
= f(s, V) (vì f(S – s,V) = 0)
= | f | .
Một hệ quả trực tiếp từ bổ đề 26.5 là kết quả chúng ta đã chứng minh trước đây –
phương trình (26.3) – giá trị của luồng đó là tổng luồng đi vào điểm thu.
Một hệ quả khác từ bổ đề 26.5 cho thấy các khả năng thông qua của lát cắt có thể được

sử dụng để giới hạn (chặn) giá trị của một luồng như thế nào.
Hệ quả 26.6
Giá trị của bất kỳ luồng f nào trong mạng vận tải G đều bị chặn trên bởi khả năng
thông qua của bất kỳ lát cắt nào của G.
Chứng minh: Cho (S,T) là lát cắt bất kỳ của G và cho f là luồng bất kỳ. Theo bổ đề
26.5 và tính ràng buộc về khả năng thông qua:
| f | = f(S, T)
12
Một kết quả trực tiếp từ hệ quả 26.6 là luồng cực đại trong một mạng bị chặn trên bởi
khả năng thông qua của một lát cắt cực tiểu của mạng đó. Định lý lát cắt cực tiểu luồng
cực đại phát biểu rằng giá trị của một luồng cực đại là bằng với khả năng thông qua
của một lát cắt cực tiểu.
Định lý 26.7 (định lý lát cắt cực tiểu luồng cực đại)
Nếu f là một luồng trong mạng vận tải G = (V,E) với đỉnh phát s và đỉnh thu t thì các
điều kiện sau là tương đương:
1. f là một luồng cực đại trong G
2. Mạng còn dư G
f
không chứa đường tăng nào
3. | f | = c(S,T) đối với lát cắt (S,T) của G
Chứng minh
(1) ⇒ (2): giả sử trái ngược (mâu thuẩn) rằng f là một luồng cực đại trong G nhưng G
f
lại có một đường tăng p. Khi đó, theo hệ quả 26.4, luồng tổng f + f
p
, trong đó f
p
được
cho bởi phương trình (26.6), là một luồng trong G với giá trị hoàn toàn lớn hơn | f |,
mâu thuẩn với giả thiết rằng f là một luồng cực đại.

(2) ⇒ (3): Giả sử rằng G
f
không chứa đường tăng nào, tức là G
f
không chứa đường
nào tử s đến t. Định nghĩa:
S = {v ∈V: xác định một đường từ s đến v trong G
f
} và T = V\{S}. Sự phân chia (S,T)
là một lát cắt: thông thường ta có s∈S và t∉S vì không có đường nào từ s đến t trong
G
f
. Với mỗi cặp đỉnh u và v (u ∈S và v ∈T) ta có f(u, v) = c(u, v), mặt khác vì (u,v)
∈E
f
(có thể đặt v trong tập S). Vì vậy, theo bổ đề 26.5 | f | = f(S,T) = c(S,T).
(3) ⇒ (1): theo hệ quả 26.6, | f | ≤ c(S,T) đối với tất cả các lát cắt (S,T). Vì vậy điều
kiện | f | = c(S,T) hàm ý rằng f là một luồng cực đại.
Thuật toán Ford-Fulkerson cơ bản
Trong mỗi lần lặp đi lặp lại của phương pháp Ford-Fulkerson, chứng ta tìm được vài
đường tăng p và tăng luồng f trên mỗi cung của p theo khả năng thông qua còn dư
c
f
(p). Sự trình bày sau về phương pháp tính toán luồng cực đại trong một đồ thị
G = (V,S) bằng cách cập nhật luồng f[u,v] giữa mỗi cặp đỉnh u,v (2 đỉnh này nối với
nhau tạo thành một cung).
1
Nếu u và v không được nối với nhau bởi một cung trong cả
hai hướng thì ta cho f[u,v] = 0. Các khả năng thông qua c(u,v) được cho sẵn theo đồ
thị, và c(u,v) = 0 nếu (u,v) ∉ E. Khả năng còn dư c

f
(u,v) được tính theo đúng như công
thức (26.5). Biểu thức c
f
(p) trong đoạn mã sau chỉ là một biến tạm thời để lưu trữ khả
năng thông qua còn dư của đường p.
FORD-FULKERSON(G, s, t)
1 for each edge (u, v) ∈ E[G]
2 do f[u, v] ← 0
3 f[v, u] ← 0
1
Chúng ta sử dụng dấu ngoặc vuông khi xem xét một đại lượng (identifier) như là một trường có thể biến đổi (ví dụ như
f) và sử dụng dấu đơn khi xem xét nó như là một hàm.
13
4 while tồn tại a đường p từ s đến t trong mạng còn dư G
f
5 do c
f
(p) ← min {c
f
(u, v) : (u, v) ∈ p}
6 for each edge (u, v) trong p
7 do f[u, v] ← f[u, v]+c
f
(p)
8 f[v, u] ← - f[u, v]
Thuật toán Ford-Fulkerson mở rộng một cách đơn giản dựa trên phương pháp Ford-
Fulkerson đã trình bày trước đó. Hình 26.5 cho thấy kết quả của mỗi lần lặp trong khi
thực hiện ví dụ. Dòng 1-3 khởi tạo luồng f bằng 0. Vòng lặp While từ dòng 4-8 thực
hiện việc lặp để tìm một đường tăng p trong Gf và tăng luồng f theo p dựa trên khả

năng thông qua còn dư c
f
(p). Khi không còn đường tăng nào thì luồng f là luồng cực
đại.
Phân tích thuật toán Ford-Fulkerson
Thời gian thực hiện thuật toán Ford-Fulkerson phụ thuộc vào đường tăng p trong dòng
4 được xác định như thế nào. Nếu nó được chọn tồi thì thuật toán có thể không xác
định: giá trị của luồng sẽ tăng một cách liên tục, nhưng nó không hội tụ (hướng đến)
giá trị luồng cực đại.
2
Tuy nhiên, nếu đường tăng được chọn bằng cách sử dụng
phương pháp tìm kiếm theo chiều rộng trước(a breadth-first search) (phương pháp này
được trình bày trong phần 22.2) thì thuật toán thực hiện trong thời gian đa thức. Tuy
nhiên, trước khi chứng minh kết quả này, chúng ta thu được một giới hạn trong trường
hợp đường tăng được chọn tùy ý và tất cả các khả năng thông qua là các số nguyên.
Trong thực tiễn, bài toán luồng cực đại thường cho với các khả năng thông qua
nguyên. Nếu các khả năng thông qua là các số hữu tỉ thì một phép biến đổi theo tỉ lệ
thích hợp có thể được sử dụng để biến chúng thành các số nguyên. Giả thiết dưới đây
trình bày việc thực hiện thuật toán Ford-Fulkerson trong thời gian O(E |f*|), trong đó f*
là luồng cực đại được tìm thấy bởi thuật toán. Việc phân tích như sau: các dòng 1-3
mất thời gian O(E). Vòng lặp While từ dòng 4-8 được thực hiện tối đa |f*| lần vì giá trị
luồng tăng ít nhất một đơn vị trong mỗi lần lặp.
Công việc thực hiện bên trong vòng lặp có thể tạo được hiệu quả nếu chúng ta quản lí
cấu trúc dữ liệu sử dụng để biểu diễn mạng G = (V,E) một cách có hiệu quả. Giả sử
rằng chúng ta lưu giữ một cấu trúc dữ liệu tướng ứng với một đồ thị có hướng
G’= (V,E’), trong đó E’ = {(u,v): (u,v) ∈E hoặc (v,u) ∈E}. Các cung trong mạng G
cũng là các cung trong G’ và vì vậy nó là một khoảng (không gian) ước lượng để duy
trì các khả năng thông qua và các luồng trong cấu trúc dữ liệu này. Cho luồng f trên G,
các cung trong mạng còn dư Gf chứa tất cả các cung (u,v) của G’ thõa:
c(u,v) - f[u,v] ≠ 0.

Vì vậy, thời gian để tìm một đường trong một mạng còn dư là O(V + E’) = O(E) nếu
chúng ta sử dụng cả tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu. Vì vậy, mỗi
lần lặp của vòng while mất thời gian O(E) khiến cho thời gian thực hiện tổng cộng của
Ford-Fulkerson là O(E |f*|).
2
Phương pháp Ford-Fulkerson có thể không kết thúc nếu các khả năng thông qua của cung là những số vô tỷ.
14
Hình 26.5
Hình 26.5 Thực hiện thuật toán Ford-Fulkerson cơ bản. (a) – (d) Việc lặp liên tiếp của vòng lặp
while. Phía bên trái của mỗi phần biểu diễn mạng còn dư Gf với đường tăng p được tô đậm. Phía
bên phải của mỗi phần biểu diễn tổng luồng f (đó là kết quả của việc cộng thêm f
p
vào f). Mạng còn
dư trong (a) là mạng vào (ban đầu) G. (e) Mạng còn dư sau cùng khi thực hiện vòng lặp. Nếu không
còn đường tăng nào thì luồng f biểu diễn trong hình (d) là một luồng cực đại.
15
Hình 26.6
Hình 26.6 (a) Một mạng vận tải đối với thuật toán Ford-Fulkerson có thể mất thời gian O(E |f|*),
trong đó f* là một luồng cực đại với |f*| = 2.000.000 . Biểu diễn một đường tăng với khả năng thông
qua còn dư 1. (b) Kết quả mạng còn dư. Biểu diễn một đường tăng khác với khả năng thông qua 1.
(c) Kết quả mạng còn dư.
Khi các khả năng thông qua là nguyên và giá trị luồng tối ưu |f*| là nhỏ, thì thời gian
thực hiện thuật toán Ford-Fulkerson là tốt. Hình 26.6(a) biểu diễn một ví dụ về những
gì có thể xảy ra trên một mạng vận tải đơn giản với |f*| là lớn. Một luồng cực đại trong
mạng này có giá trị 2.000.000: 1.000.000 đơn vị của luồng đi theo đường s → u → t,
và luồng khác 1.000.000 đơn vị đi theo đường s → v → t. Nếu đường tăng đầu tiên
được tìm thấy bởi thuật toán Ford-Fulkerson là s → u → v → t (hình 26.6(a)) thì
luồng có giá trị 1 sau lần lặp đầu tiên. Kết quả mạng còn dư được biểu diễn trong hình
26.6(b). Nếu lần lặp thứ hai tìm thấy đường tăng s → v → u → t (hình 26.6(b)) thì
luồng sau có giá trị 2. Hình 26.6(c) biểu diễn kết quả mạng còn dư. Chúng ta có thể

tiếp tục chọn đường tăng s → u → v → t trong những lần lặp thuộc số lẻ và đường
tăng s → u → v → t trong những lần lặp thuộc số lẻ. Chúng ta có thể tính tổng của
2.000.000 tăng, mỗi lần chỉ tăng giá trị luồng lên một đơn vị.
Thuật toán Edmonds-Karp
Giới hạn trên của thuật toán Ford-Fulkerson có thể được cải thiện nếu chúng ta thực
hiện việc tính toán đường tăng p trong dòng 4 với một phương pháp tìm kiếm rộng, tức
là nếu đường tăng là một đường ngắn nhất từ s đến t trong mạng còn dư, trong đó mỗi
cung có đơn vị khoảng cách (trọng lượng – weight). Chúng ta gọi phương pháp Ford-
Fulkerson vì thuật toán Edmonds-Karp được thực hiện. Bây giờ chúng ta chứng minh
rằng thuật toán Edmonds-Karp thực hiện với thời gian O(V E
2
).
Việc phân tích phụ thuộc vào khoảng cách đến các đỉnh trong mạng còn dư G
f
. Bổ đề
sau sử dụng kí hiệu δ
f
(u,v) cho khoảng cách đường ngắn nhất (shortest-path distance)
từ u đến v trong G
f
, trong đó mỗi cung có đơn vị khoảng cách.
Bổ đề 26.8
Nếu thuật toán Edmonds-Karp áp dụng trên một mạng vận tải G = (V,E) với đỉnh phát
s và đỉnh thu t, thì ∀v ∈V\{s,t} : khoảng cách đường ngắn nhất δ
f
(u,v) trong mạng còn
dư G
f
tăng một cách đều đều với mỗi sự tăng luồng.
Chứng minh Chúng ta giả sử rằng, cho vài đỉnh v∈V\{s,t}, có một sự tăng luồng tạo

ra khoảng cách đường ngắn nhất từ s đến và sau đó chúng ra sẽ xuất phát từ một sự
mâu thuẩn. Cho f là luồng trước sự tăng đầu tiên (luồng f làm giảm một vài khoảng
cách đường ngắn nhất) và cho f’ là luồng kế sau đó. Cho v là đỉnh ∈δ
f’
(u,v), khoảng
cách của δ
f’
(u,v) bị giảm bởi việc tăng luồng, vì vậy δ
f’
(s,v) < δ
f
(s,v). Cho
p = s →u→v là một đường ngắn nhất từ s đến v trong G
f ’
nên (u,v) ∈E
f ’
và
δ
f ’
(s,u) = δ
f ’
(s,v) – 1. (26.7)
Vì vậy làm thế nào chúng ta chọn v, biết rằng nhãn khoảng cách của đỉnh u không
giảm, nghĩa là
16
δ
f ’
(s,u) ≥ δ
f
(s,u)

Chúng ta khẳng định (u,v) ∉E
f
. Vì sao? Nếu chúng ta có (u,v) ∈E thì chúng ta cũng có
thể có:
δ
f
(s,v) ≤ δ
f
(s,u) + 1 (theo bổ đề 24.10, bất đẳng thức tam giác)
≤ δ
f ‘
(s,u) + 1 (theo bất đẳng thức (26.8))
= δ
f ’
(s,u) (theo phương trình (26.7)),
điều này trái với giả thiết δ
f ’
(s,v) < δ
f
(s,v).
Chúng ta có thể có (u,v) ∉ E
f
và (u,v) ∈ E
f ’
như thế nào? Việc tăng phải thực hiện tăng
luồng từ v đến u. Thuật toán Edmonds-Karp luôn tăng luồng theo các đường ngắn
nhất, và vì vậy đường ngắn nhất từ s đến u trong G
f
có (v,u) như là cung cuối cùng của
nó. Vì vậy,

δ
f
(s,v) = δ
f
(s,u) - 1
≤ δ
f ‘
(s,u) - 1 (theo bất đẳng thức (26.8))
= δ
f ’
(s,v) -2 (theo phương trình (26.7)),
điều này trái với giả thiết δ
f ’
(s,v) < δ
f
(s,v). Chúng ta kết luận giả thiết một đỉnh v tồn
tại là không đúng.
Định lý tiếp theo giới hạn số lần lặp của thuật toán Edmonds-Karp.
Định lý 26.9
Nếu thuật toán Edmonds-Karp được áp dụng trên một mạng vận tải G = (V,E) với đỉnh
phát s và đỉnh thu t thì tổng số lần tăng luồng thực hiện bởi thuật toán là O(V E).
Chứng minh
Ta nói rằng một cung (u,v) trong một mạng còn dư G
f
là tới hạn (critical) trên một
đường tăng p nếu khả năng thông qua còn dư của p là khả năng thông qua còn dư của
(u,v), tức là nếu c
f
(p) = c
f

(u,v). Sau khi chúng ta đã tăng luồng theo một đường tăng thì
bất cứ cung tới hạn nào trên đường đó cũng sẽ không xuất hiện trong mạng còn dư.
Hơn nữa, trên bất cứ đường tăng nào cũng có ít nhất một cung phải là tới hạn. Chúng
ta sẽ chỉ ra rằng mỗi tập cung |E| có thể trở thành tới hạn tối đa |V|/2 – 1 lần.
Cho u và v là các đỉnh trong V được nối với nhau bởi một cung trong E. Vì các đường
tăng là các đường ngắn nhất nên khi (u,v) tới hạn trong lần đầu tiên, ta có:
δ
f
(s,v) = δ
f
(s,u) + 1
Luồng được tăng một lần, cung (u,v) không xuất hiện trong mạng còn dư. Nó không
thể xuất hiện lại sau này trên đường tăng khác cho đến khi sau khi luồng từ u đến v
được giảm (luồng này chỉ xuất hiện nếu (v,u) xuất hiện trên một đường tăng). Nếu f ’
là luồng trong G khi trường hợp này xảy ra thì ta có:
δ
f ’
(s,u) = δ
f ’
(s,v) + 1
vì δ
f
(s,v) ≤ δ
f ’
(s,v) theo bổ đề 26.8, ta có:
δ
f ’
(s,u) = δ
f ’
(s,v) + 1

≥ δ
f
(s,v) + 1
= δ
f
(s,u) + 2.
17
Vì vậy, từ khi (u,v) trở nên tới hạn cho đến khi nó trở nên tới hạn lần kế tiếp, khoảng
cách từ đỉnh phát đến u tăng ít nhất 2 lần (ban đầu khoảng cách từ đỉnh phát đến u ít
nhất bằng 0). Các đỉnh trung gian trên một đường ngắn nhất từ s đến u không thể chứa
s, u hoặc t (vì (u,v) trên đường tới hạn ngụ ý là u ≠ t). Vì vậy, cho đến khi u trở nên
không thể đạt đến từ đỉnh phát thì khoảng cách của nó tối đa là |V| - 2. Như vậy, (u,v)
có thể trở thành tới hạn tối đa (|V|-2)/2 = |V|/2 – 1 lần. Vì có O(E) cặp đỉnh có thể có
một cung giữa chúng trong một đồ thị còn dư, tổng số các cung tới hạn trong suốt toàn
bộ quá trình thực hiện thuật toán Edmonds-Karp là O(V E). Và do đó mỗi đường tăng
có ít nhất một cung tới hạn.
Vì mỗi lần lặp của thuật toán Ford-Fulkerson có thể được thực hiện với thời gian O(E)
khi đường tăng được tìm thấy bởi phương pháp tìm kiếm theo chiều rộng, tổng thời
gian thực hiện chương trình theo thuật toán Edmonds-Karp là O(V E
2
). Chúng ta sẽ
thấy rằng thuật toán Push-relabel có thể mang lại các giới hạn tốt hơn. Thuật toán ở
phần 26.4 đưa ra một phương pháp để đạt được thời gian thực hiện là O(V
2
E), phương
pháp này làm nền tảng cho thuật toán với thời gian O(V
3
) ở phần 26.5.
Bài tập
26.2-1

Trong hình 26.1(b), luồng ngang qua lát cắt ({s,v2,v4},{v1,v3,t}) là gì? Khả năng
thông qua của lát cắt này là bao nhiêu?
26.2-2
Chỉ ra sự thực hiện thuật toán Edmonds-Karp trên mạng vận tải ở hình 26.1(a).
26.2-3
Trong ví dụ ở hình 26.5, lát cắt cực tiểu tương ứng với luồng cực đại đã chỉ ra là gì?
Trong số các đường tăng xuất hiện trong ví dụ, hai đường tăng nào khử (cancel)
luồng?
26.2-4
Chứng minh rằng, với bất kỳ cặp đỉnh u và v và với bất kỳ khả năng thông qua c và
luồng f , ta có: c
f
(u, v)
+
c
f
(v, u) = c(u, v) + c(v, u).
26.2-5
Nhớ lại cách vẽ hình biểu diễn sự chuyển đổi một mạng vận tải với đa đỉnh phát
(multisource), đa đỉnh thu (multisink) thành một mạng với đỉnh phát và đỉnh thu đơn
(ở phần 26.1) bằng cách thêm vào các cung có khả năng thông qua vô hạn. Chứng
minh rằng bất kỳ luồng nào trong mạng kết quả cũng có một giá trị hữu hạn nếu các
cung của mạng đa đỉnh phát, đa đỉnh thu ban đầu có khả năng thông qua hữu hạn.
26.2-6 Giả sử rằng mỗi đỉnh phát s
i
trong bài toán đa đỉnh phát, đa đỉnh thu tạo ra
chính xác p
i
đơn vị luồng sao cho f(s
i

,V)=p
i
. Cũng giả sử rằng, mỗi đỉnh thu t
j
tiêu thụ
chính xác q
j
đơn vị, sao cho f(V,t
j
,)=q
j

,
trong đó ∑
i
p
i
= ∑
j
q
j
Hãy chỉ ra cách để chuyển
đổi bài toán tìm một luồng f tuân theo các sự ràng buộc thêm vào đó thành bài toán tìm
một luồng cực đại trong một mạng vận tải với đỉnh phát và đỉnh thu đơn.
26.2-7
Chứng minh bổ đề 26.3
18
26.2-8
Chỉ ra một luồng cực đại trong một mạng vận tải G = (V,E) luôn luôn có thể được tìm
thấy bởi một dãy tối đa |E| các đường tăng. (Gợi ý: xác định các đường tăng sau khi

tìm thấy luồng cực đại.)
26.2-9
Cung liên kết của một đồ thị vô hướng là số nhỏ nhất k các cung phải bị xóa bỏ khỏi
đồ thi phân tách. Ví dụ, cung liên kết của một cây là 1 và cung liên kết của một vòng
tuần hoàn các đỉnh là 2. Chỉ ra cách làm thế nào để cung liên kết của một đồ thị vô
hướng G = (V,E) có thể được xác định bằng cách thực hiện thuật toán luồng cực đại
trên tối đa |V| mạng vận tải, mỗi mạng có O(V) đỉnh và O(E) cung.
26.2-10
Giả sử rằng một mạng vận tải G = (V,E) có các cung đối xứng, tức là (u,v) ∈ E nếu và
chỉ nếu (v,u) ∈ E. Hãy chỉ ra rằng thuật toán Edmonds-Karp giới hạn tối đa |V| |E|/4
lần lặp. (Gợi ý: Với bất kỳ cung (u,v)xét cả δ(s,u) và δ(v,t) thay đổi như thế nào giữa
các lần (u,v) tới hạn.)
26.3. Đối sánh cực đại (maximum bipartite matching)
Ngày nay, người ta đã có thể giải được một số bài toán tổ hợp tương tự bài toán
luồng cực đại như bài toán đa tài nguyên (multiple source), bài toán luồng cực đại
multiple-sink Ngoài ra chúng ta còn những bài toán tổ hợp liên quan đến luồng trong
mạng, một trong số đó bài toán tìm một đối sánh cực đại (maximum matching) trong
một đồ thị kép (bipartite graph) là một bài toán điển hình.
Để giải bài toán này, chúng ta áp dụng tính bảo toàn của phương pháp Ford-
Fulkerson với đồ thị G=(V,E) trong thời gian O(VE).
Phát biểu bài toán:
Định nghĩa: (maximum matching)
Cho một đồ thị vô hướng G=(V,E), một đối sánh là tập các cung M là tập con
của tập E mà mỗi một cung thuộc M thì đều được tạo từ đỉnh v
∈
V . Một đỉnh v
∈
v là
được đối sánh (matched) bởi đối sánh M (matching M) nếu trong M có cung chứa điểm
đó, ngược lại thì v không được đối sánh bởi đối sánh M.

Một đối sánh cực đại (maximum matching) khi và chỉ khi độ lớn của nó là cực
đại, tức là nếu M là một đối sánh cực đại thì với đối sánh M’ bất kỳ thì:
|M|≥ |M’|.
Bài toán: (bipartite graph)
Xem như tập đỉnh của đồ thị phân thành hai tập con L và R thỏa V = L

R và
giả thiết rằng mọi đỉnh trong V đều thuộc một cung nào đó thuộc E (xem hình 26.7)
19
L R L R
(a) (b)
Hình 26.7: Đồ thị kép G=(V,E) với tập phân vùng đỉnh (vertex partition) V = L

R. (a) đối sánh với số phần tử (cardinality) 2, (b) đối sánh với số phần tử 3.
Tìm một đối sánh cực đại trong một đồ thị kép là một bài toán có nhiều ứng
dụng thực tiễn. Ví dụ: một đối sánh giữa 1 tập L là các máy trong một quy trình sản
xuất với tập R là những công việc chính là tổ chức sao cho công việc được thực hiện
theo một quy trình liên tục đồng nhất về thời gian. Ta xem một cung (u,v) trong E biểu
diễn một máy trong đó u
∈
L là khả năng thực hiện của máy và v
∈
R là công việc mà
máy cần phải làm. Đối sánh cực đại ở đây chính là khả năng làm việc lớn nhất có thể
cho phép của máy.
Phương pháp tìm đối sánh cực đại:
Áp dụng phương pháp Ford-Fulkerson để tìm một đối sánh cực đại trong một đồ
thị vô hướng kép G=(V,E) trong một hàm thời gian (time polymonial) của
V
và

E
.
Hình 26.8 mô hình hóa ý tưởng giải bài toán đó là tạo ra một mạng vận tải (flow
network) trong đó các luồng chính là các đối sánh.
20
L R L R
(a) (b)
Hình 26.86: Mạng vận tải (flow network) chuyển thành đồ thị kép. (a) Đồ thị
kép G=(V,E) với tập đỉnh được cho ở 26.7 với đối sánh cực đại là các cung được tô
đậm. (b) một mạng vận tải tương tự G’ với một luồng cực đại. Mỗi cung đều có khả
năng thông. Những cung tô đậm là các luồng của 1 và tất cả các cung còn lại không
chứa luồng. Những đường tô đậm có chiều đi từ tập L đến tập R tương ứng với đối
sánh cực đại trong đồ thị kép.
Chúng ta xác định một mạng vận tải tương ứng (corresponding flow network)
G’=(V’,E’) cho một đồ thị kép sau. Giả thiết rằng điểm phát s và điểm thu t không
thuộc V , V’ =V

{s,t}. Nếu tập phân vùng đỉnh (vertex partition) của đồ thị G là V =
L

R thì tương ứng các cung của G’ cũng chính là những cung thuộc tập E mà có
hướng từ tập L đến tập R, độ lớn của tập E’ gồm các cạnh dựa trên các đỉnh của V
được tính như sau:
E’ = {(s,u): u
∈
L}

∪
{(s,u): u
∈

L, v
∈
R, (u,v)
∈
E}

∪
{(v,t): v
∈
R}
Gán đơn vị khả năng thông mạng cho mỗi cung của E’, do mỗi đỉnh thuộc V
thuộc ít nhất một cung nên
E
≥
V
/2.
Suy ra
E
≤

'E
=
E
+
V
≤
3
E
. Vậy
'E

= O(E)
21
Bổ đề (lemma) dưới đây sẽ chứng tỏ rằng một đối sánh trong G tương ứng hoàn
toàn một luồng trong mạng vận tải tương đương G’. Chúng ta nói rằng một luồng f
trên một mạng vận tải G=(V,E) là có giá trị nguyên (integer – valued) nếu f(u,v) là một
biến nguyên với mọi (u,v)
∈
V
×
V.
Bổ đề 26.10:
Cho đồ thị kép G=(V,E) với tập phân vùng đỉnh (vertex partition) V = L

R và
G’=(V’,E’) tương ứng là mạng vận tải của nó. Nếu M là một đối sánh trong G thì có
một luồng giá trị nguyên (integer- valued) f trong G’ thỏa:
f
=
M
Ngược lại, nếu f là một luồng giá trị nguyên thuộc G’ thì sẽ tồn tại một đối sánh
M trong G mà độ lớn thỏa:
M
=
f
Chứng minh:
Trước tiên chúng ta phải chỉ ra được một đối sánh M trong G sẽ tương ứng một
luồng giá trị nguyên f trong G’. Ta định nghĩa f như sau: nếu (u,v)
∈
M thì
f(s,u)=f(u,v)=f(v,t)=1 và f(u,s)=f(v,u)=f(t,v)=-1. Các cung (u,v)

∈
E’ còn lại thì ta cho
f(u,v)=0. Khi đó dễ dàng nhận thấy f là bảo toàn tính đối xứng, các ràng buộc về khả
năng thông qua (capacity contrains) và cân bằng luồng.
Dễ dàng thấy mỗi cung (u,v)
∈
M tương ứng với một đơn vị của luồng trong G’
theo đường đi s u v t. Ngoài ra, các đường đi được tạo ra bởi các cung trong M
là những đỉnh không kề (vertex-disjoint), ngoại trừ hai đỉnh s và t. Tổng luồng trên
từng lát cắt (L
∪
{s}. R
∪
{t}} bằng độ lớn của M (
M
); do đó, bổ đề 26.5 giá trị của
luồng là
f
=
M
.
Để chứng minh điều ngược lại, giả sử f là một luồng giá trị nguyên trong G’ và
M ={(u,v): u
∈
L, v
∈
R, f(u,v) >0}. Mỗi đỉnh u
∈
L chỉ có duy nhất một cung đi vào, ta
ký hiệu là (s,u) và khả năng thông qua của cung đó là 1.

Do đó mỗi đỉnh u
∈
L có nhiều nhất là một đơn vị luồng dương đi vào, trong
trường hợp nếu một đơn vị luồng dương không đi vào, thì do sự cân bằng luồng, một
đơn vị luồng dương sẽ đi ra. Hơn nữa, do f là có giá trị nguyên, với mỗi đỉnh u
∈
L một
đơn vị luồng dương có thể đi vào tại 1 cung và ra nhiều nhất là một cung. Vậy một đơn
vị của luồng dương đi vào u nếu và chỉ nếu có một đỉnh v
∈
R thỏa f(u,v) = 1 và có tối
đa là một cung ra tại mỗi đỉnh u
∈
L chứa luồng dương. Một tham số cân bằng
(symmetric argument) sẽ được gán cho mỗi đỉnh v
∈
R. Khi đó tập M là một đối sánh.
Dễ dàng thấy rằng mọi đỉnh được đối sánh u
∈
L có f(s,u) = 1 và mọi cung (u,v)
∈
E - M sẽ tồn tại f(u,v) = 0. Suy ra:
M
= f(L,R)
=f(L,V’) - f(L,L) - f(L,s) - f(L,t) (Bổ đề 26.1)
Biểu thức trên có thể được rút gọn như sau:
Do là luồng cân bằng nên f(L,V’) = 0;
Theo Bổ đề 26.1 thì f(L.L)=0
Do tính đối xứng nên - f(L,s) = f(s,L)
Do không có cung nào từ L vào t nên f(L,t) = 0

22
Từ đó suy ra:
M
= f(s,L)
=f(s,V’) (do tất cả các cung ra từ s đều đi vào L)
=
f
(theo định nghĩa của
f
)
Theo Bổ đề 26.10, chúng ta có thể kết luận được một đối sánh cực đại trong một
đồ thị kép G tương ứng với một luồng cực đại trong mạng vận tải tương tự
(corresponding flow network) G’ của G, nhờ đó chúng ta có thể tính một đối sánh cực
đại trong G bằng tìm luồng cực đại trên G’. Sự ràng buộc duy nhất là thuật toán tìm
luồng cực đại trả về một luồng trong G’ mà trong đó có một số hàm f(u,v) cho giá trị
không nguyên, mặc dầu giá trị luồng
f
là một giá trị nguyên. Định lý sau đây sẽ chỉ ra
ràng nếu chúng ta dùng phương pháp Ford-Fulkerson thì sẽ giải quyết được vấn đề
trên.
Định lý 26.11 (Định lý bảo toàn)
Nếu hàm khả năng c có giá trị bảo toàn thì luồng cực đại f mà được tìm bằng
phương pháp Ford-Fulkerson sẽ có thuộc tính giá trị luồng
f
là giá trị nguyên. Ngoài
ra, với mọi đỉnh u và v thì giá trị của f(u,v) là một giá trị nguyên.
Chứng minh: Sử dụng tính lặp tại bài tập 26.3-2 để chứng minh Hệ quả sau
Hệ quả 26.12:
Độ lớn của một đối sánh cực đại M trong đồ thị kép G bằng giá trị của luồng cực
đại f trong mạng vận tại tương ứng G’.

Chứng minh:
Giả sử rằng M là một đối sánh cực đại trong G và luồng tương ứng f trong G’ là
không cực đại và có một luồng cực đại f’ trong G’ thoả
'f
>
f
.
Vì khả năng thông của G’ là giá trị nguyên (theo định lý 26.11) nên có thể suy
ra f’ là giá trị nguyên. Do đó, f’ tương ứng một đối sánh M’ trong G với độ lớn
'M
=
'f
>
f
=
M
, điều này ngược với giả thiết M là một đối sánh cực đại. Tương tự ta có
thể chỉ ra rằng nếu f là một luồng cực đại trong G’, đối sánh tương ứng của nó là một
đối sánh cực đại trên G.
Vậy, cho một đồ thị kép vô hướng G, ta có thể tìm một đối sánh cực đại bằng
cách tạo ra mạng vận tải G’, sau đó dùng phương pháp Ford-Fulkerson tìm một đối
sánh cực đại M từ luồng cực đại giá trị nguyên đã tìm được. Do các đối sánh trong một
đồ thị kép có độ lớn tối thiểu min(L,R) = O(V), giá trị của luồng cực đại tỏng G’ là
O(V). Ta có thể tìm một đối sánh cực đại trong một đồ thị kép trong thời gian O(VE’)
= O(VE), do đó
'E
=
Θ
(E).
Bài tập:

1. Cài đặt thuật toán Ford-Fulkerson trong mạng vận tải ở hình 26.8(b) và chỉ ra
mạng còn dư (residual network) sau khi thực hiện nâng luồng (flow augmentation). L
bao gồm các đỉnh từ 1 đến 5 và R gồm các đỉnh từ 6 đến 9. Với mỗi vòng lặp
(iteration), xác định đường tăng (augmenting path) nhỏ nhất (lexicographycally
smallest).
2. Chứng minh Định lý 26.11
23
3. Cho đồ thị kép G=(V,E) có tập phân vùng đỉnh (Vertex partition) V = L

R
và G’=(V’,E’) tương ứng là mạng vận tải của nó. Xác định đường đi tốt (good upper
bound) dựa trên trọng số (length) của đường tăng được tìm thấy trong G’ bằng phương
pháp Ford-Fulkerson.
4. Một đối sánh đầy đủ (perfect matching) là một đối sánh có tất cả các đỉnh đều
được đối sánh.
Cho đồ thị kép vô hướng G=(V,E) có tập phân vùng đỉnh (Vertex partition) V =
L

R thỏa
L
=
R
. Với mọi X
⊆
V, ta xác định lân cận (neighborhood) là tập các đỉnh
liền kề với các phần tử (đỉnh) của X như sau:
N(X)={y
∈
V: (x,y)
∈

E,
∀
x
∈
X}
Chứng minh Định lý Hall được phát biểu như sau:
Với mọi tập con A
⊆
L thì G có đối sánh đầy đủ (perfect matching) nếu và chỉ
nếu
A
≤
)(AN
.
5. Một đồ thị kép G=(V,E) với tập đỉnh V = L

R là đầy đủ bậc d (d-regular)
nếu mọi đỉnh v
∈
V có bậc là d. Trong các đồ thị kép đầy đủ bậc d thì
L
=
R
.
Chứng minh rằng mọi đồ thị kép đầy đủ bậc d có một đối sánh của phần tử
L

bằng cách chỉ ra một lát cắt cực tiểu của mạng vận tải tương là có khả năng thông qua
(capacity)
L

.
26.4 Thuật toán Push-relabel
Trong phần này, chúng ta biểu diễn “generic-push-relabel” để tính toán luồng cực đại.
Tới nay, rất nhiều thuật toán luồng cực đại được xem nhanh nhất đều là thuật toán
push-label và sự thực thi nhanh nhất của thuật toán luồng cực đại dựa trên phương
pháp push-relabel. Những vấn đề về luồng khác như cực tiểu chi phí của luồng, có thể
được giải quyết một cách hiệu quả bằng phương pháp “push-relabel”. Phần này giới
thiệu thuật toán luồng cực đại “chung” của Goldberg, có độ phức tạp ở mức O(V
2
E)
do đó hiệu quả hơn thuật toán của Edmond-Karp có độ phức tạp O(VE
2
). Phần 26.5 cải
tiến thuật toán chung để chứa đựng một thuật toán push-relabel có độ phức tạp là
O(V
3
).
Thuật toán push-relabel được thực hiện ở một mức độ địa phương nào đó hơn là
phương pháp Fold-Fulkerson. Thay vì kiểm tra phần còn lại của của mạng để tìm kiếm
một đường đi tiếp theo, thuật toán push-relabel làm việc trên một đỉnh tại một thời
điểm, tìm kiếm chỉ các đỉnh liền kề trong phần mạng còn lại. Hơn nữa, không giống
phương pháp Ford-Furkerson, thuật toán push-relabel không duy trì thuộc tính chuyển
đổi luồng trong suốt quá trình thực hiện. Tuy nhiên, chúng thực hiện và duy trì một
preflow, là một hàm f: VxV→ R thỏa mãn tính đối xứng, ràng buộc dung lượng và sự
chuyển luồng: f(V,u) ≥ 0 cho tất cả các đỉnh u ∈ V –{s}. Chúng ta gọi lượng này là sự
vượt quá luồng vào đỉnh u, được xác định bởi
e(u) = f(V,u).
Chúng ta nói rằng đỉnh u ∈ V –{s,t} là quá tải nếu e(u) > 0.
24
Chúng ta nên bắt đầu phần này bằng cách mô tả trực quan bên dưới thuật toán push-

relabel. Sau đó ta nên tìm hiểu hai hành động là “push” một luồng trước (preflow) và
“gán lại nhãn” (relabel) một đỉnh. Cuối cùng ta biểu diễn thuật toán và phân tích tính
đúng đắn và thời gian thực hiện của nó.
Mô tả:
Để mô tả phương pháp push-relabel ta giả sử đang thực hiện với dòng chất lỏng: chúng
ta giả sử một mạng luồng G=(V,E) biểu diễn một hệ thống các đường ống thông nhau
với một sức chứa (trọng số). Thực hiện tương tự đối với phương thức Ford-Fulkerson,
chúng ta có thể nói rằng mỗi đường đi thêm vào trong mạng giống như thêm vào dòng
chất lỏng, với không có điểm nhánh, với luồng từ nguồn tới đích. Phương pháp Ford-
Fulkerson thêm nhiều dòng của luồng cho đến khi không thể thêm được nữa.
Thuật toán generic-push-relabel có một chút khác biệt. Các cạnh có hướng thể
hiện cho đường ống. Các đỉnh, là nơi giao nhau của các cạnh, có hai tính chất thú vị.
Một là, để điều tiết luồng vượt quá giới hạn, mỗi đỉnh có một ống thoát ra dẫn tới một
bể chứa độ lớn tùy ý để có thể điều tiết chất lỏng. Hai là, mỗi đỉnh, sức chứa của nó, và
tất cả các kết nối đường ống nằm trên một nền mà chiều cao tăng như là quá trình giải
thuật.
Chiều cao đỉnh xác định cách luồng được đẩy vào (push): chúng ta chỉ đẩy
luồng xuống, do đó, từ một đỉnh cao đến đỉnh thấp hơn. Luồng từ một đỉnh thấp hơn
đến một đỉnh cao hơn có thể được, nhưng thao tác đẩy luồng chỉ đẩy nó xuống. Chiều
cao của đỉnh nguồn là |V|, và chiều cao của đích là 0. Tất cả các chiều cao đỉnh khác
bắt đầu từ 0 và tăng với thời gian. Thuật toán đầu tiên gửi càng nhiều luồng càng tốt
xuống từ đỉnh nguồn tới đích. Số lượng gửi chính xác vừa đủ để lấp đầy sức chứa các
ống đi ra từ nguồn; do đó, nó gửi các trọng số của (s,V-s). Khi luồng đầu tiên tham gia
một đỉnh trung gian (intermediate) nó chọn trong các đỉnh nguồn. Từ đây, cuối cùng
nó đẩy xuống.
Cuối cùng nó có thể xảy ra là chỉ những ống leave một đỉnh u và chưa bão hòa
với luồng kết nối đến đỉnh không cùng mức như đỉnh u hoặc xuất phát trên từ u.
Trong trường hợp này, để giải thoát đỉnh u bị tràn luồng khỏi luồng giới hạn của nó,
chúng ta phải tăng chiều cao của nó- gọi là “gán lại nhãn” cho đỉnh u. Chiều cao của
nó được tăng hơn một đơn vị so với chiều cao thấp nhất của các đỉnh kế cận là các ống

ở trạng thái chưa bão hòa. Sau khi một định được gán lại nhãn, do đó, phải có tối thiểu
một ống đi ra đi qua mà các luồng có thể đẩy vào.
Cuối cùng, tất cả các luồng có thể chuyển qua đến cái bồn. Không nhiều hơn có
thể đến, bởi vì các ống tuân theo ràng buộc trọng số;; số lượng luồng băng qua bất kì
đoạn cắt nào vẫn còn được giới hạn bởi khả năng của đoạn cắt. Để làm một luồng
trước là một luồng “hợp pháp”, thuật toán gửi các giới hạn được chọn trong các nguồn
của đỉnh tràn luồng trở lại nguồn bằng cách tiếp tục gán lại nhãn các đỉnh để above
chiều cao |V| của nguồn. Khi chúng ta thấy, một lần tất cả các bể chứa đều rỗng, thì
luồng trước không chỉ là một luồng “hợp lệ”, mà còn là luồng cực đại.
Các thao tác cơ bản
25