Nhóm 4
LUỒNG CỰC ĐẠI
26.1 Mạng vận tải
Dựa vào lý thuyết đồ thị, chúng tôi đưa ra một định nghĩa được giả định là
đúng về mạng vận tải gồm những tính chất của nó và định nghĩa bài toán luồng cực
đại một cách chính xác. Mặt khác, chúng tôi cũng giới thiệu về một vài kí hiệu có
ích.
Định nghĩa về mạng vận tải
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.
Cho đồ thị G = (V, E) với các đỉnh V và các cung 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 (bậc trong bằng 0) và t là đỉnh thu (bậc
ngoài bằng 0) của mạng. Cho f(u, v) là luồng từ đỉnh u đến đỉnh v. Một luồng trong
G là một ánh xạ ƒ: 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):
luồng từ đỉnh này đến đỉnh khác không vượt quá khả năng thông qua đã được cho
của luồng đó.
∀u, v ∈ V: ƒ(u, v) ≤ c(u, v)
Tính đối xứng (Skew symmetry): luồng từ đỉnh u đến đỉnh v phải bằng đối
của luồng từ v đến u.
∀u, v ∈ V: ƒ(u, v) = - ƒ(v, u)
Tính bảo toàn luồng (Flow conservation): tổng giá trị của luồng đi từ một
đỉnh ngoại trừ đỉnh phát và đỉnh thu đến một đỉnh là bằng 0.
∀u ∈ V\{s, t}:
( , ) 0

v V
f u v
∈
=
∑
∀ v ∈V\{s, t}. Tức là, tổng giá trị của luồng đi vào một đỉnh ngoại trừ đỉnh
phát và đỉnh thu là bằng 0.
Khi cả (u, v) lẫn (v, u) đều không thuộc E thì không có luồng nào giữa u và
v. khi đó: ƒ(u, v) = ƒ(v, u) = 0.
Giá trị ƒ(u, v) (có thể nhận giá trị dương, giá trị 0 hoặc giá trị â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:
1
Nhóm 4
| | ( , )
v V
f f s v
∈
=
∑
Đây là tổng giá trị luồng đi từ đỉ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ị giá trị tuyệt đối hay số các yếu tô trong 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.
Sau đây là một ví dụ về mạng vận tải và mạng vận tải với luồng cực đại của
nó
Hình 1 Mạng vận tải
Hình 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 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 đó.
Hình 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 để phân biệt 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ó.
Đ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ị dương của luồng đi vào đỉnh v được xác định bởi
( , ) 0
( , )
u V
f u v
f u v
∈
>
∑
2
| | ( , )
v V

f f s v
∈
=
∑
Nhóm 4
Tổng giá trị dương của luồ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ị thực của luồng tại một đỉnh là bằng tổng giá trị dương của
luồng đi ra từ đỉnh đó trừ đi tổng giá trị dương của luồng đi vào đỉnh đó. Sự thể hiện
tính bảo toàn luồng là ở chỗ tổng giá trị dương của luồng đi vào một đỉnh (ngoại trừ
đỉnh phát và đỉnh thu) phải bằng tổng giá trị dương của luồng đi ra từ đỉnh đó. Tính
chất này (tổng giá trị thực của luồng 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 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 để lưu trữ chúng.
Lucky Puck thuê chổ trên các xe tải của 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) được 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 1(a)). Lucky Puck không có sự kiểm soát trên 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 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 để mô phỏng “luồng” về việc vận
chuyển với mạng vận tải này bởi vì số lượng thùng được vận chuyển mỗi ngày từ
thành phố này đến thành phố khác là khó tránh khỏi sự liên quan đến tính ràng buộc

về khả năng thông qua của luồng. Ngoài ra, sự bảo toàn 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 tinh tế 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 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 đối xứng yêu cầu rằng ƒ(v
1
,v
2
) = - ƒ(v
2
,v
1
), vì vậy trong trường hợp này chúng
ta không thể xem ƒ(v
1
,v
2
) = 8 và ƒ(v
2
,v

1
) = 3 được.
Lucky Puck có thể nhận thấy rằng thật là vô nghĩa để 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
3
Nhóm 4
đượ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 ít tài nguyên hơn trong quá
trình xử lí). Chúng ta biểu diễn vấn đề này 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 là vì 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 để lưu lại được thông tin về
sự vận chuyển theo cả hai hướng.
Phương pháp hủy bỏ (cancellation) sẽ phát sinh trong toàn bộ thuật toán. 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) bằng cách 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à nhiều đỉ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 bao gồm {s
1
,s
2
,…,s
m
} và một
tập n kho bao gồm {t
1
,t
2

,…,t
m
} như trong hình 2(a). 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 với nhiều đỉnh phát và nhiều đỉnh thu
về bài toán luồng cực đại thông thường. Hình 2(b) cho thấy mạng (a) có nhiều đỉnh
phát và đỉnh thu có thể đượ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 đỉnh phát giả
(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 đỉnh thu giả (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) và ngược lại. Đỉnh phát giả s cung cấp nhiều luồng như yêu cầu
4
Nhóm 4
cho các đỉnh phát s
i
.Tương tự, đỉnh thu giả t tiếp nhận nhiều luồng từ các đỉnh thu
t
i
.
Hình 2
Hình 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 đỉnh phát giả (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 đỉnh thu giả (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.
Làm việc với nhiều luồng
Chúng ta sẽ xử lý nhiều hàm (như ƒ), hàm này nhận đối số là 2 đỉnh trong
mạng vận tải. Chúng ta sẽ sử dụng một kí hiệu tổng ẩn (implicit summation
notation) trong đó mỗi đối số hoặc cả hai có thể là một tập hợp các đỉnh với cách
hiểu là giá trị được biểu hiện là tổng 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ì:
( , ) ( , )
x X y Y
f X Y f x y
∈ ∈
=
∑ ∑
Vì vậy, sự ràng buộc của tính bảo tồn 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ỏ dấu ngoặc nhọn
5
Nhóm 4
của tập hợp khi chúng được sử dụng trong kí hiệu tổng ẩ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 các luồng.
Bổ đề
Cho G = (V, E) là một mạng vận tải và cho ƒ là một luồng trong G. Khi đó
có các thuộc tính sau:
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 X ∩ Y = Ø 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 giá trị của luồng đi vào đỉnh thu; tức là:
|ƒ| = ƒ(V, t).

Dễ dàng nhận thấy đặc tính này được khẳng định. Do tính bảo tồn luồng nên
tất cả các đỉnh (ngoại trừ đỉnh phát và đỉnh thu) có giá trị dương của luồng đi vào và
đi ra bằng nhau. Theo định nghĩa, đỉnh phát có tổng giá trị thực của luồng lớn hơn
0; tức là, luồng có giá trị dương đi ra từ đỉnh phát nhiều hơn là đi vào nó. Ngược lại,
đỉnh thu là đỉnh có tổng giá trị thực của luồng bé hơn 0. Tức là luồng có giá trị
dương đi vào đỉnh thu nhiều hơn là đi ra nó. Điều đó được chứng minh như sau:
|ƒ| = ƒ(s, V) (bằng định nghĩa)
= ƒ(V, V) - ƒ(V - s, V) (bằng bổ đề , phần 3)
= - ƒ(V - s, V) (bằng bổ đề , phần 1)
= ƒ(V, V - s) (bằng bổ đề , phần 2)
= ƒ(V, t) + ƒ(V, V - s - t) (bằng bổ đề , phần 3)
= ƒ(V, t) (tính bảo tồn luồng)
Bài tập
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
Bài làm:
Nếu (u, v) ∉ E và (v, u) ∉E thì c(u, v) = 0 (theo định nghĩa)
Mà c(u, v) = 0 thì luồng từ đỉnh u đến đỉnh v cũng bằng 0, tức là f(u, v) = 0.
Theo tính đối xứng f(u,v) = - f(v,u), nên f(v,u) = 0.
Bài tập 26.1-2
6
Nhóm 4
Chứng minh rằng, bất cứ đỉnh v nào (ngoại trừ đỉnh phát và đỉnh thu) thì tổng luồng
dương (the total positive flow) đi vào v phải bằng tổng luồng dương đi ra khỏi v.
Bài tập 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 có nhiều đỉnh
phát và đỉnh thu đều tương ứng với một luồng có giá trị đồng nhất 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) và ngược lại.
Bài tập 26.1-4
Chứng minh bổ đề 26.1.
Bài làm:
* Chứng minh: f(X, X) = 0
( , ) ( , )
1
( , ) ( , ) ( , ) ( , ) 0
2
u v X X u v X X
f X X f u v f u v f v u
∈ × ∈ ×
= = + =
∑ ∑
* Chứng minh: f(X, Y) = - f(Y, X)
( , ) ( , )
( , ) ( , ) ( , )
u v X Y u v X Y
f X Y f u v f v u
∈ × ∈ ×
= = −
∑ ∑
( , ) ( , )
( , ) ( , ) ( , )
u v X Y v u Y X
f v u f v u f Y X
∈ × ∈ ×
= − = − = −
∑ ∑
* Chứng minh:

( , ) ( , ) ( , )X Y f X Y Z f X Z f Y Z
= ∅ ⇒ = +
I U
( , ) ( ) ( , ) ( ) ( )
( , ) ( , ) ( , )
u v X Y Z u v X Z Y Z
f X Y Z f u v f u v
∈ × ∈ × ×
= =
∑ ∑
U U
U

( , ) ( , )
( , ) ( , )
u v X Z u v Y Z
f u v f u v
∈ × ∈ ×
= +
∑ ∑

( , ) ( , )f X Z f Y Z
= +
Bài tập 26.1-5
Cho mạng vận tải G = (V, E) và luồng ƒ như hình 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).
7
Nhóm 4
Hình 1(b)

Bài làm:
* Xác định một cặp tập con X, Y ⊆ V: ƒ(X, Y) = -ƒ(V - X, Y):
X = {s, v1}
Y = {v3}
V – X = {v2, v3, v4, t}
f(X, Y) = f(v1, v3) = 12
f(V – X, Y) = f(v2, v3) + f(v4, v3) + f(t, v3) = (-4) + 7 + (-15) = -12
Vậy, f(X, Y) = - f(V – X, Y)
* Xác định một cặp tập con X, Y ⊆ V: ƒ(X, Y) ≠ -ƒ(V - X, Y):
X = {s, v1}
Y = {v3, t}
V – X = {v2, v3, v4, t}
f(X, Y) = f(v1, v3) = 12
f(V – X, Y) = f(v2, v3) + f(v4, v3) + f(t, v3) + f(v3, t) + f(v4, t)
= (-4) + 7 + (-15) + 15 + 4
= 7
Vậy, ƒ(X, Y) ≠ -ƒ(V - X, Y)
Bài tập 26.1-6
Cho một mạng vận tải G = (V, E), cho ƒ
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) ∀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à
tổng luồng f
1
+ f
2
thõa mãn và tính chất nào là trái ngược với nó?
Bài làm:
*
, ,u v V
∀ ∈

( ) ( )
1 2
,f f u v
+

8
Nhóm 4
( ) ( )
( ) ( )
( ) ( )
( )
( ) ( )
1 2
1 2
1 2
1 2
, ,
, ,
, ,
,
f u v f u v
f v u f v u
f v u f v u
f f v u
= +
= − −
= − +
= − +
Vậy, tổng luồng f
1
+ f
2
thõa mãn tính chất đối xứng.
*
, \{ , },u v V s t

∀ ∈
( )( )
1 2
,
v V
f f u v
∈
+
∑
( ) ( )
( )
( ) ( )
1 2
1 2
, ,
, ,
0 0
0
v V
v V v V
f u v f u v
f u v f u v
∈
∈ ∈
= +
= +
= +
=
∑
∑ ∑

Vậy, tổng luồng f
1
+ f
2
thõa mãn tính chất bảo toàn luồng.
*
, ,u v V
∀ ∈
( ) ( )
1 2
,f f u v
+
( ) ( )
( ) ( )
( )
1 2
, ,
, ,
2 ,
f u v f u v
c u v c u v
c u v
= +
≤ +
=
Không lớn hơn hoặc bằng c(u, v). Trừ phi c(u,v) = 0.
Vậy, tổng luồng f
1
+ f
2

không thõa mãn tính chất ràng buộc về khả năng thông qua
của luồng.
Bài tập 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].
Bài làm:
Để chứng minh ta chỉ cần biểu diễn αƒ
1
+ (1- α)ƒ
2
thõa mãn các 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:
Hàm f
1
và f
2
là các luồng nên

( ) ( )
1
, ,f u v c u v
≤
và
( ) ( )
2
, , , ,f u v c u v u v V
≤ ∀ ∈
Ta có:
9
Nhóm 4
( )
( )
( )
( ) ( ) ( )
( )
( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( )
1 2
1 2
1 2
1 ,
, 1 ,
, 1 * ,
* , 1 * ,
1* , ,
f f u v

f u v f u v
f u v f u v
c u v c u v
c u v c u v
α α
α α
α α
α α
+ −
= + −
= ∗ + −
≤ + −
≤ =
* Tính đối xứng:
Hàm f
1
và f
2
là các luồng nên
( ) ( )
1 1
, ,f u v f v u
= −
và
( ) ( )
2 2
, , , ,f u v f u v u v V
= − ∀ ∈
Ta có:
( )

( )
( )
( ) ( ) ( )
( )
( )
( ) ( ) ( )
( )
( )
( ) ( ) ( )
( )
( )
( )
( )
( )
( )
1 2
1 2
1 2
1 2
1 2
1 ,
, 1 ,
, 1 ,
, 1 ,
1 ,
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

α α
α α
α α
α α
α α
+ −
= + −
=− − −
=− + −
=− + −
* Tính bảo toàn luồng:
Hàm f
1
và f
2
là các luồng nên
( )
1
, 0
v V
f u v
∈
=
∑
và
( )
2
, 0, , \{ , }
v V
f u v u v V s t

∈
= ∀ ∈
∑
Ta có:
( )
( )
( )
( ) ( ) ( )
( )
( )
( )
( ) ( ) ( )
( )
( )
( ) ( ) ( )
( ) ( ) ( )
( )
1 2
1 2
1 2
1 2
1 2
1 ,
, 1 ,
, 1 ,
* , 1 * ,
, 1 ,
*0 1 *0
0
v V

v V
v V v V
v V v V
v V v V
f f u v
f u v f u v
f u v f u v
f u v f u v
f u v f u v
α α
α α
α α
α α
α α
α α
∈
∈
∈ ∈
∈ ∈
∈ ∈
+ −
= + −
= + −
= + −
= + −
= + −
=
∑
∑
∑ ∑

∑ ∑
∑ ∑
Bài tập 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).
Bài tập 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 đi qua các con đường tại góc đường. May thay, nhà
10
Nhóm 4
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ể 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 Fork-Fulkerson
Phần này trình bày phương pháp Fork-Fulkerson để làm sáng tỏ vấn đề về
luồng cực đại. Chúng ta gọi nó là 1 “phương pháp” đúng hơn là một “thuật toán” vì
nó bao gồm một số yếu tố với số lần thực hiện khác nhau. Thuật toán Ford-
Fulkerson dựa trên 3 khái niệm quan trọng thể hiện tính vượt trội của phương pháp
và có liên quan đến các vấn đề và các thuật toán về luồng: mạng thặng dư, đường
tăng luồng và lát cắt. 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 bằng
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 cách
biểu diễn một thành phần cụ thể của phương pháp Ford-Fulkerson và phân tích thời
gian của nó.
Phương pháp Ford-Fulkerson là sự 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 luồng” mà chúng ta có thể nghĩ

một cách đơn giản như là một đường từ đỉnh phát s đến đỉnh thu t, dọc theo đó
chúng ta có thể gởi nhiều luồng hơn và sau đó tăng luồng dọc theo đường này.
Chúng ta lặp lại quá trình này cho đến khi đường tăng luồng không được tìm thấy.
Định lý lát cắt cực tiểu luồng cực đại chỉ ra rằng với các điều kiện trên, 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 khởi tạo luồng ban đầu f nhận giá trị 0
2 while tồn tại một đường tăng luồng p
3 do tăng luồng f dọc theo p
4 return f
Mạng thặng dư
Cho mạng vận tải và một luồng, mạng thặng dư bao gồm các cạnh có thể thêm
vào luồng. Chính thức hơn, giả sử chúng ta có một mạng vận tả G = (V, E) với đính
phát s và đỉnh thu t. Cho f là một luồng trên G và xét cặp các đỉnh u,v∈V. Lượng
giá trị của luồng thêm vào 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) giá trị thặng dư của (u,v), xác định bởi:
(26.5) c
f
(u,v) = c (u,v) – f (u,v)
11
Nhóm 4
Ví dụ, nếu c(u,v) = 16 và f (u,v) = 11, khi đó 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ì giá trị thặng dư c
f
(u,v) là lớn hơn giá trị c(u,v). Ví dụ, nếu c(u,v) = 16
và f(u,v) = -4 thì giá trị thặng 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. Chúng ta đẩy một luồng khác 16 đơn vị từ u đến
v trước khi can thiệp đến 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, trước khi tìm thấy khả năng
thông qua của cung đó.
Cho một mạng vận G=(V, E) và một luồng f, mạng thặng dư của G được
sinh ra bởi f là G
f
=(V, E
f
), trong đó:
E
f
= {(u, v) ∈ V
x
V : c
f
(u, v) > 0}
Điều này nghĩa là, với mỗi cung của mạng thặng dư hay cung thặng dư, có thể
thêm vào một luồng có giá trị lớn hơn 0. Hình 26.3(a) lặp lại mạng vận tải và luồng
f của hình 26.1(b), và hình 26.3(b) chỉ ra mạng vận tải G
f
tương ứng.
Hình 26.3: (a) Mạng vận tải G và luồng f của hình 26.1(b). (b) Mạng thặng
dư G
f
với đường tăng luồng p được tô đậm, giá trị thặng dư của nó là c
f
(p) = c(v
2

,
v
3
) = 4. (c) Luồng trong G là kết quả dọc theo đường tăng luồng p bởi giá trị thặng
dư của nó 4. (d) Mạng thặng dư được sinh ta từ luồng trong (c).
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 và
vì vậy (v,u) ∈ E
f
. Nếu không (u, v) cũng không phải (v, u) xuất hiện trong mạng ban
đầu, khi đó c(u, v) = c(v, u) = 0, f(u, v)>= f(v, u)= 0 (bài tập 26.1-1), và c
f
(u, v) =
c
f
(v, u) = 0. Chúng ta kết luận rằng, cung (u, v) có thể xuất hiện trong mạng thặng
12
Nhóm 4
dư chỉ nếu tại ít nhất một trong hai cung (u, v) và (v, u) xuất hiện trong mạng ban
đầu, và khi đó:
| E

f
| ≤ 2| E |
Nhận xét: Mạng thặng 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 thặng 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, và f là một
luồng trong G. G
f
là mạng thặng dư của G sinh ra bởi f và f ’ là một luồng trong G
f ’
Khi đó tổng luồng f + f ’ được 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, sức chứa tối đa và tính bảo tồn
luồng được tuân theo. Đối với tính đối xứng lệch, 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 khả năng thông qua của luồng, 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 bao tồn luồng, chú ý rằng: ∀ u ∈V\{s,t}, ta có:
∑ (f+f’)(u, v) = ∑ ( f(u, v) + f’ (u, v))
v∈V v∈V
= ∑ f(u, v) + ∑ f’ (u, v))
v∈V v∈V
= 0 + 0
= 0
Cuối cùng, ta có
| f | + | f’ | = ∑( f + f’)(s, v)
= ∑( f(s, v) + f’(s, v))
= ∑f(s, v) + ∑f’(s, v)
= | f | + | f’ |
Đường tăng luồng
13
Nhóm 4
Cho một mạng vận tải G = (V,E) và luồng f, một đường tăng luồng p là một
đường đơn giản từ s đến t trong một mạng thặng dư G
f
. Theo định nghĩa về mạng
thặng dư, mỗi cung (u,v) trên một đường tăng luồng thêm vào một 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 luồng. Xem mạng thặng
dư G
f
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 thông qua còn dư nhỏ nhất trên đường là c
f
(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 trong đường tăng
luồng p là giá trị thặng dư của p, cho bởi:
c
f
(p) = min{c
f
(u, v): (u, v) thuộc đường tăng 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 mạng vận tải G = (V, E), f là một luồng trong G và p là đường tăng luồng
trong G
f
. Định nghĩa một hàm f
p
: V
x
V → R bởi:
C
f
(p)

nếu (u, v) ∈ p
f
p
(u, v) = - C
f

(p)

nếu (u, v) ∈ p
0, trường hợp khác
Khi đó, f
p
là một luồng trong G
f
với giá trị |f
p
| = c
f
(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 mạng vận tải G = (V.E), f là một luồng trong G và p là một đường tăng
luồng trong G
f
. 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
. Khi đó 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
luồ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 mà 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 thặng dư của nó không chứa đường tăng luồng nào. Để chứng
14
Nhóm 4
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.
Một lát cắt (S, T) của một mạng vận tải G = (V, E) là một phân hoạch của V
thành S và 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 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, khi đó luồng thông 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 chỉ ra 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 thông 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.
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.
Luồng thô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.
Quan sát thấy rằng luồng thông 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, luồng thông 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.
15
Nhóm 4
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, (S,T)
là một lát cắt của G. Khi đó luồng thông 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)
= ∑f (u, v) ≤ ∑c(u, v) = c(S, T)
u∈S u∈S
v∈T v∈T
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)
nhj
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 thặng dư G
f
không chứa đường tăng luồ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ử f là một luồng cực đại trong G nhưng G
f
có một đường tăng
luồng p. Khi đó, theo hệ quả 26.4, luồng tổng f + f

p
, trong đó f
p
được cho bởi
16
Nhóm 4
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 luồ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 Fork-Fulkerson cơ bản
Phương
=

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 luồng p và tăng luồng f trên mỗi cung của p theo giá trị thặng
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, E) 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 gán 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. Giá trị thặng 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ữ giá trị thặng dư của đường p.
FORD-FULKERSON(G, s, t)
1 for mỗi cung (u, v) ∈ E [G]
2 do f [u, v] ← 0
3 f [v, u] ← 0
4 while tồn tại a đường p từ s đến t trong mạng thặng dư G
f
5 do c
f
(p) ← min {c
f
(u, v) : (u, v) ∈ p}
6 for mỗi cung (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 đơ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ụ.
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.
17
Nhóm 4
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 luồng p trong G
f
và tăng luồng f theo p dựa trên giá trị thặng
dư c
f
(p). Khi không tồn tại đường tăng luồng thì luồng f là luồng cực đại.
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 thặng dư G
f
từ dòng
4 với đường tăng luồ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 thặng dư trong (a) là
mạng vào (ban đầu) G. (e) Mạng thặng dư sau cùng của vòng lặp while. Nếu không
còn đường tăng luồng nào thì luồng f biểu diễn trong hình (d) là một luồng cực đại.
Phân tích thuật tóan Fork- Fulkerson

Thời gian thực hiện thuật toán Ford-Fulkerson phụ thuộc vào đường tăng
luồng p trong dòng 4 được xác định như thế nào. Nếu nó được lựa chọn xấu thì
18
Nhóm 4
thuật toán có thể không giới hạn: 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. 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 luồ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 xuất hiện 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í tính hiệu quả cấu trúc dữ liệu được sử dụng để biểu diễn mạng G = (V, E).
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 cách đơn giản để 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 thặng dư G
f
chứa tất cả các cung (u,v) của G’ thõa: c(u,v) - f[u,v]
≠ 0. Thời gian để tìm một đường trong một mạng thặng 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. Mỗi lần
lặp của vòng while mất thời gian O(E), khiến cho tổng thời gian thực hiện của Ford-
Fulkerson là O(E |f*|).
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 thặng
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 thặng dư. Chúng ta có thể tiếp tục chọn đường tăng luồng s → u → v → t
trong những lần lặp thuộc số lẻ và đường tăng luồng s → v → u → t trong những
lần lặp thuộc số chẵn. Chúng ta có thể thực hiện 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ị.
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ỷ.
19
Nhóm 4
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 luồng với giá trị thặng dư 1. (b) Mạng thặng dư. Biểu diễn một đường
tăng luồng khác với giá trị thặng dư 1. (c) Mạng thặng dư.
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 luồng p trong dòng 4 (của thuật toán Ford-
Fulkerson) với một phương pháp tìm kiếm rộng, tức là nếu đường tăng luồng là một
đường ngắn nhất từ s đến t trong mạng thặng dư, trong đó mỗi cung có đơn vị
khoảng cách (trọng lượng). Chúng ta gọi phương pháp Ford-Fulkerson vì thuật toán

Edmonds-Karp được bổ sung. 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 thặng dư
G
f
. Bổ đề sau sử dụng kí hiệu δ
f
(u,v) cho khoảng cách đường ngắn nhất 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 đặn 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
laf nguyên nhân làm cho đường ngắn nhất từ s đến v giảm xuống, và sau đó chúng
ta sẽ tìm thấy sự mâu thuẫn. f là luồng trước lần 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à f ’ là luồng tiếp sau đó. v là đỉnh ∈ δ
f’
(u,v) với
khoảng cách δ
f’
(s,v) là nhỏ nhất 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à
(26.7) δ
f ’
(s,u) = δ
f ’
(s,v) – 1.
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à:
(26.8) δ
f ’
(s,u) ≥ δ
f
(s,u)
20
Hình 26.6
Nhóm 4
Chúng ta khẳng định (u,v) ∉E
f
. Vì sao? Nếu chúng ta có (u,v) ∈E
f

, 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 được 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 thặng dư G
f
là tới hạn (critical)
trên một đường tăng luồng p nếu giá trị thặng dư của p là giá trị thặng 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

luồ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 thặng dư. Hơn nữa, trên bất cứ đường tăng nào cũng phải 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, khi đó (u,v) tới hạn trong lần đầu tiên, ta có:
δ
f
(s,v) = δ
f
(s,u) + 1
Mỗi lần tăng luồng, cung (u,v) không xuất hiện trong mạng thặng 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 bị
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ó:
21
Nhóm 4
δ
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.
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ị thặng 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 luồ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 luồ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), với lát cắt ({s, v2, v4},{v1, v3, t}) hãy tính giá trị của luồng và
khả năng thông qua của lát cắt này?
Đặt (S,T) là lát cắt tương ứng với lát cắt ({s, v2, v4},{v1, v3, t}). Ta có:
22
Nhóm 4
- Luồng thông qua lát cắt (S, T):
f(S, T) = f(s,v
1
) + f(v
2
,v
1
) + f(v
2
,v
3
) + f(v
4
,v
3
) + f(v
4
,t)
= 11 – 11 – 4 +7 +4 = 7.
- Khả năng thông qua lát cắt (S, T):
c(S, T) = c(s,v
1
) + c(v
2

,v
1
) + c(v
4
,v
3
) + c(v
4
,t)
= 16 + 4 +7 +4 = 31.
Bài tập 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).
- Thực hiện việc tính toán đường tăng luồng p trong dòng 4 (của thuật toán
Ford-Fulkerson) với một phương pháp tìm kiếm rộng, tức là nếu đường
tăng luồng là một đường ngắn nhất từ s đến t trong mạng thặng dư, trong
đó mỗi cung có đơn vị khoảng cách (trọng lượng).
- Giải thuật được mô tả trong file chương trình.
Bài tập 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ử luồng?
- Lát cắt cực tiểu tương ứng với luồng cực đại đã chỉ ra là: ({s,v1,v2,v4},
{v3,t})
- Trong số các đường tăng xuất hiện, hai đường tăng khử luồng:
Bài tập 26.2-4
Chứng minh rằng, với bất kỳ cặp đỉnh u 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).
23
Nhóm 4
Bài tập 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.
Bài tập 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.
Bài tập 26.2-7
Chứng minh bổ đề 26.3
Cho mạng vận tải G = (V, E), f là một luồng trong G và p là đường tăng luồng
trong G
f
. Định nghĩa một hàm f
p
: V
x
V → R bởi:
c
f
(p)

nếu (u, v) ∈ p
f

p
(u, v) = - c
f
(p) nếu (u, v) ∈ p
0, trường hợp khác
Khi đó, f
p
là một luồng trong G
f
với giá trị |f
p
| = c
f
(p) > 0
Chứng minh:
- Dựa vào định nghĩa f
p
(u, v) nên ta có f
p
(u, v) < c
f
(u, v) và f
p
(u, v) = - f
p
(u, v). Nghĩa là f
p
thỏa mãn 2 tính chất của luồng: Sức chứa tối đa và tính
đối xứng lệch.
- Tính bảo toàn luồng:

∑ f
p
(u, v) = c
f
(p) + (-c
f
(p)) + 0 = 0
v∈V
Vậy ta chứng minh xong bổ đề 26.3.
Bài tập 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.)
24
Nhóm 4
- Vì rằng sau khi ta thực hiện quá trình tăng luồng dựa vào các đường tăng
luồng trong mạng thặng dư, tức rằng sau quá trình tăng luồng ta có được
một đồ thị tồn tại các cung bão hòa. Và tập cạnh của đồ thị này cũng
chính tập cạnh E của đồ thì G ban đầu, tức |E
sau
| = |E
đầu
| = |E|.
Vì vậy 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.
Bài tập 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.
Bài tập 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 Bộ ghép cực đại trên đồ thị hai phía
Đối với một số bài toán tổ hợp ta có thể áp dụng phương pháp Luồng cực đại
(maximum - flow) để giải.Có một số bài toán với nhiều nguồn phát và nhiều nguồn
thu như ở mục giới thiệu Phần 26.1 cho chúng ta một ví dụ Có một số bài toán tổ
hợp khác dường như rất ít liên quan đến vấn đề luồng trong mạng, nhưng thực tế ta
có thể giải nó bằng cách dùng phương pháp luồng cực đại. Một trong số đó ta có thể
kể đến bài toán: tìm kiếm một bộ ghép cực đại trong đồ thị hai phía. Mục này tập
trung giải quyết vấn đề đó. Để giải quyết vấn đề này, ta sẽ tận dụng lợi thế của các
đặc tính của phương pháp For Fulkerson.nhà.Chúng ta thấy rằng phương pháp
Ford-Fulkerson có thể được dùng để giải quyết vấn đề tìm bộ ghép cực đại trên đồ
thị hai phía.Ở đây ta xét đối với đồ thị G = (V, E) với thời gian tính là O(VE).
Bài toán về bộ ghép cực đại trên đồ thị hai phía
Phần này ta sẽ tìm hiểu bài toán tìm bộ ghép cực đại trên đồ thị hai phía. Do
đó trước khi tìm hiểu bài toán ta cần tìm hiểu một số khái niệm: đồ thị hai phía, bộ
ghép (matching), bộ ghép cực đại (maximum bipartite matching).
 Đồ thị hai phía (đồ thị phân đôi):
25