Chương 2
BÀI TOÁN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA
CÁC CUNG – CÁC ĐỈNH
Bài toán luồng cực đại trong mạng là một trong số những bài toán tối ưu trên đồ
thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị
trong lý thuyết tổ hợp. Bài toán được đề xuất vào đầu những năm 1950, và gắn liền với
tên tuổi của hai nhà bác học Mỹ là Ford và Fulkerson. Bài toán luồng cực đại trong
mạng có nhiều ứng dụng trong thực tế như: Bài toán xác định cường độ dòng lớn nhất
của dòng vận tải giữa hai nút của một bản đồ giao thông, bài toán tìm luồng dầu lớn
nhất có thể bơm từ tàu chở dầu vào bể chứa của một hệ thống đường ống dẫn dầu…
Ngoài ra, ứng dụng của bài toán còn để giải các bài toán như: Bài toán đám cưới vùng
quê, bài toán về hệ thống đại diện chung, bài toán phân nhóm sinh hoạt, bài toán lập
lịch cho hội nghị …Trong phạm vi đề tài này tôi sẽ trình bày “bài toán luồng cực đại
trong mạng với khả năng thông qua các cung các đỉnh” và phải nhờ thuật toán của
Ford và Fulkerson để giải bài toán đặt ra và nêu một số ứng dụng của bài toán.
I. PHÁT BIỂU BÀI TOÁN
1.Bài toán
Giả xử trong đồ thị G = (V,E), ngoài khả năng thông qua của các cung c(u,v), ở
mỗi đỉnh v
∈
V còn có khả năng thông qua của đỉnh là d(v), và đòi hỏi tổng luồng đi
vào đỉnh v không còn vượt quá d(v), tức là
∑
∈
≤
Vw
vdvwf )(),(
Cần phải tìm luồng cực đại giữa s và t trong mạng như vậy.
Xây dựng một mạng G’ sao cho: mỗi đỉnh v của G tương ứng với hai đỉnh v
+
, v

A’ = ( a’
ij

) =
nếu i = j
c[i,j] nếu [i,j] ∈ E’
Thí dụ 1. Hình 1a cho ví dụ mạng G với khả năng thông qua ở cung và đỉnh.
Hình 1b là mạng G’ tương ứng chỉ có khả năng thông qua ở các cung.

Hình 1
Do luồng đi vào đỉnh v
+
phải đi qua cung (v
+
,v
-
) với khả năng thông qua d(v),
nên luồng cực đại trong G’ sẽ bằng luồng cực đại trong G với khả năng thông qua của
các cung và đỉnh.
Hai bước trên ta có thể biểu diễn dưới dạng sơ đồ thuật toán sau:
2
C[v,t]
C[u,t]
C[s,v]
C[s,u]
t
-

v d
v
u d
u
s
d
s
(a)
d
i
,nếu i = j
c[i,j] ,nếu [i,j] ∈ E
0 ,nếu [i,j] ∉ E
A’ = ( a’
ij

) =
nếu i = j
c[i,j] nếu [i,j] ∈ E’
s u v t
7 5 2 0 s
0 6 1 4 u
0 0 8 3 v
0 0 0 6 t
s
+
s
-
u
+


Trong đó: d
i
là khả năng thông qua đỉnh i; C[i,j] khả năng thông qua cung [i,j].
3.2 Biểu diễn mạng G’ tương ứng với mạng G
Mạng tương ứng với G = (V,E), |V | = n là mạng G’ = (V’,E’), |V’| = 2 |V |, |E’|
= 2 |E | - 1. Được biểu diễn thông qua ma trận A’ cấp (2n x 2n) như sau:
3
d
i
,nếu i = j
c[i,j] ,nếu [i,j] ∈ E
0 ,nếu [i,j] ∉ E
A = ( a
ij
) =
A’ = ( a’
ij

) =
nếu i = j
c[i,j] nếu [i,j] ∈ E’
Begin
Mạng G
Mạng G’
Luồng cực đại trên G’
End
s u v t
7 5 2 0 s
0 6 1 4 u

0 0 0 0 0 0 0 6 t
+
0 0 0 0 0 0 0 0 t
-
s
+
s
-
u
+
u
-
v
+
v
-
t
+
t
-
0 6 0 0 0 0 0 0 s
+
0 0 4 0 2 0 0 0 s
-
0 0 0 4 0 0 0 0 u
+
0 0 0 0 0 0 4 0 u
-
0 0 0 0 0 2 0 0 v
+

+
u
-
6
u
-
5
s
-
7
2
s
+
A =
s u v t
7 5 2 0 s
0 6 1 4 u
0 0 8 3 v
0 0 0 6 t
A’ =
s
+
s
-
u
+
u
-
v
+

v
+
v
-
t
+
t
-
0 6 0 0 0 0 0 0 s
+
0 0 4 0 2 0 0 0 s
-
0 0 0 4 0 0 0 0 u
+
0 0 0 0 0 0 4 0 u
-
0 0 0 0 0 2 0 0 v
+
0 0 0 0 0 0 2 0 v
-
0 0 0 0 0 0 0 6 t
+
0 0 0 0 0 0 0 0 t
-
Áp dụng T.T Ford-Fulkerson tìm luồng cực đại cho mạng G’ ta được mạng cực
đại và ma trận biểu diễn nó như sau:
Với Val(f
*
) = 6
4. Bài toán luồng cực đại trong mạng

Sơ đồ của thuật toán Ford – Fulkerson có thể mô tả trong thủ tục sau đây:
Procedure Max_Flow;
(* Thuật toán Ford – Fulkerson *)
begin
(* Khởi tạo: Bắt đầu từ luồng với giá trị 0 *)
for u
∈
V do
5
C =
s
+
s
-
u
+
u
-
v
+
v
-
t
+
t
-
0 6 0 0 0 0 0 0 s
+
0 0 4 0 2 0 0 0 s
-

gán nhãn cho các đỉnh. Mỗi đỉnh trong quá trình thực hiện thuật toán sẽ ở một trong ba
trạng thái: chưa có nhãn, có nhãn chưa xét, có nhãn đã xét. Nhãn của một đỉnh v gồm
2 phần và có một trong hai dạng sau: [+p(v),
ε
(v)] hoặc [-p(v),
ε
(v)]. Phần thứ nhất
+p(v) (-p(v)) chỉ ra là cần tăng (giảm) luồng theo cung (p(v),v) cung (v,p(v)) còn phần
thứ hai
ε
(v) chỉ ra lượng lớn nhất có thể tăng hoặc giảm theo cung này. Đầu tiên chỉ có
đỉnh s được khởi tạo nhãn và nhãn của nó là chưa xét, còn tất cả các đỉnh còn lại đều
chưa có nhãn . Từ s ta gán cho tất cả các đỉnh kề với nó và nhãn của đỉnh s sẽ trở thành
nhãn đã xét. Tiếp theo, từ mỗi đỉnh v có nhãn chưa xét ta lại gán nhãn cho tất cả các
nhãn chưa có nhãn kề với nó và nhãn của đỉnh v trở thành nhãn đã xét. Quá trình sẽ
được lặp lại cho đến khi hoặc là đỉnh t trở thành có nhãn hoặc là nhãn của tất cả các
đỉnh có nhãn đều là đã xét nhưng đỉnh t vẫn chưa có nhãn. Trong trường hợp thứ nhất
ta tìm được đường tăng luồng, còn trong trường hợp thứ hai đối với luồng đang xét
không tồn tại đường tăng luồng ( tức là luồng đã là cực đại ). Mỗi khi tìm được đường
tăng luồng, ta lại tăng luồng theo đường tìm được, sau đó xoá tất cả các nhãn và đối
với luồng mới thu được lại sử dụng phép gán nhãn các đỉnh để tìm đường tăng luồng.
Thuật toán sẽ kết thúc khi nào đối với luồng đang có trong mạng không tìm được
đường tăng luồng.
Thuật toán gán nhãn (The labeling algorithm)
Gọi V
T
là tập mọi đỉnh đã gán nhãn nhưng chưa được thăm. Ta có thuật toán để
tìm đường đi tăng luồng.
Xuất phát với V
T

6