TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).2008

99
THUẬT TOÁN HOÁN CHUYỂN NGUỒN ĐÍCH
CÓ TRỌNG SỐ TÌM LUỒNG CỰC ĐẠI
WEIGHTED SOURCE-SINK ALTERNATIVE ALGORITHM
TO FIND MAXIMAL FLOW

TRẦN QUỐC CHIẾN
Trường Đại học Sư phạm, Đại học Đà Nẵng

TÓM TẮT
Công trình tiếp tục nghiên cứu thuật toán hoán chuyển nguồn đích giải bài toán
tìm luồng cực đại trên mạng. Kết quả chính của báo cáo là đề xuất Thuật toán
hoán chuyển nguồn đích có trọng số tìm luồng cực đại. Ý tưởng thuật toán là tìm
đường đi tăng luồng đồng thời từ đỉnh nguồn và đỉnh đích với trọng số là lực
lượng các đỉnh gán nhãn tiến và nhãn lùi. Kết quả tính toán qua các ví dụ cho
thấy thuật toán hoán chuyển nguồn đích có trọng số là thuật toán tổng quát có thể
áp dụng hiệu quả cho mạng bất kỳ.
ABSTRACT
This paper deals with the maximal flow problem. The basic results are
systematically presented and proved. The known Ford-Fulkerson is thoroughly
introduced and illustrated. The main result of this work is the weighted source-sink
alternative algorithm. The idea of the algorithm is to find augmented paths
simultaneously from the source and the sink vertex with the weights as the
cardinalities of the forward labeled vertices and the backward labeled vertices (the
Ford-Fulkerson algorithm finds augmented paths only from the source vertex).
Calculus examples show that the proposed algorithm considerably decreases the
computational complexity in comparison with the Ford-Fulkerson algorithm.
Key word: graph, network, flow


S : = { a }
Tạo lập tập T gồm các đỉnh đã có nhãn lùi nhưng chưa được dùng để sinh
nhãn lùi:
T : = { z }
2. Chọn chiều sinh nhãn
Nếu S   T , thì sang bước 3 (sinh nhãn tiến), ngược lại sang bước 4 (sinh
nhãn lùi).
3. Sinh nhãn tiến
3.1. Chọn đỉnh sinh nhãn tiến
 Trường hợp S  : Chọn đỉnh u  S nhỏ nhất (theo thứ tự). Loại u khỏi
S, S := S \ { u }. Ký hiệu nhãn tiến của u là (, p, ) và A là tập các đỉnh
chưa có nhãn tiến và kề đỉnh sinh nhãn tiến u.
Sang bước 3.2.
 Trường hợp S = , thì kết thúc, luồng F là cực đại.
3.2. Gán nhãn tiến cho đỉnh chưa có nhãn tiến và kề đỉnh sinh nhãn tiến u
 Trường hợp A = : Quay lại bước 2.
 Trường hợp A  : Chọn t  A nhỏ nhất (theo thứ tự). Loại t khỏi A, A:=
A \ { t }. Gán nhãn tiến cho t như sau:
Nếu (u,t)  E và f
u,t
< c
u,t
, đặt nhãn tiến đỉnh t là (, u, min{, c
u,t
 f
u,t
}).
Nếu (t, u)  E và f
t,u
> 0, đặt nhãn tiến đỉnh t là (, u, min{, f

}).
Nếu (v, t)E và f
v,t
> 0, đặt nhãn lùi đỉnh t là (, v, min{, f
v,t
}).
Nếu t không được gán nhãn lùi, thì quay lại bước 4.2.
Nếu t được gán nhãn lùi và t có nhãn tiến, thì sang bước hiệu chỉnh tăng
luồng 5.
Nếu t được gán nhãn lùi và t không có nhãn tiến, thì bổ sung t vào T, T:=
T  { t }, và quay lại bước 4.2.
5. Hiệu chỉnh tăng luồng
Ký hiệu t là đỉnh được gán nhãn tiến ở bước 3.2 hoặc nhãn lùi ở bước 4.2
để thuật toán dẫn đến bước 5. Giả sử t có nhãn tiến (, p, ) và nhãn lùi (, q, ).
Đặt  = min{, }.
Ta hiệu chỉnh luồng f như sau:
5.1. Hiệu chỉnh ngược từ t về a theo nhãn tiến
5.1.1. Khởi tạo
j := t, i := p
5.1.2. Hiệu chỉnh
Nếu cung (i, j)  G, thì hiệu chỉnh f
ij
= f
ij
+ .
Nếu cung (j, i)  G, thì hiệu chỉnh f
ji
= f
ji
 .

là số nguyên, thì sau hữu hạn bước quá
trình giải kết thúc.
Chứng minh (tương tự như thuật toán Ford-Fulkerson).

 Hệ quả. Nếu giá trị thông qua c
ij
là số hữu tỉ với mọi (i,j)  E, thì sau hữu hạn
bước quá trình giải kết thúc.
Chứng minh (tương tự như thuật toán Ford-Fulkerson).

 Định lý 2
Cho mạng G=(V,E,c) với nguồn a và đích z, f = {f
ij
 (i,j)G} là luồng
nhận được khi kết thúc thuật toán hoán chuyển nguồn đích có trọng số tìm luồng
cực đại. Khi đó, f là luồng cực đại.
Chứng minh
Ta xét hai trường hợp kết thúc thuật toán.
(i) Thuật toán kết thúc ở bước 3.1: Ký hiệu S là tập các đỉnh mang nhãn tiến.
Khi đó lát cắt (S, V \ S) là lát cắt cực tiểu (xem chứng minh thuật toán Ford-
Fulkerson), kéo theo f là luồng cực đại.
(ii) Thuật toán kết thúc ở bước 4.1: Ký hiệu T là tập các đỉnh mang nhãn lùi.
Khi đó lát cắt (V \ T, T) là lát cắt cực tiểu (tương tự chứng minh thuật toán Ford-
Fulkerson), kéo theo f là luồng cực đại.

+ Ví dụ 1. Xét mạng G

trong đó số đỉnh là (2.n +1)
2
+1 và các cung cho như hình vẽ với trọng số đều là 1.

),(
)1,(
ji
ji


,  2k  i  2k và (3k  j  k1 hoặc k  j  3k1)

),(
)1,(
ji
ji


,  2k  i  2k và k  j  k1
(b) Cung ngang [(i,j), (i+1,j)], 2k  i  2k1, 3k  j  3k
(i,j)(i+1,j)  (0  i  2k1, 0  j  3k)
hoặc (2k  i  1, 3k  j  1)
(i,j)(i+1,j)  0  i  2k1, 3k  j  1
hoặc 2k  i  1, 0  j  3k

(iii) Khả năng thông qua của tất cả các cung là 1.
Áp dụng thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại
của G ta thấy: lực lượng của S và T tương đương nhau, vì vậy số lần gán nhãn tiến
và nhãn lùi xấp xỉ như nhau. Ở mỗi vòng lặp tìm đường đi tăng luồng, số đỉnh xét
xấp xỉ (2k)
2
= 4.k
2
, và nhãn tiến và nhãn lùi sẽ gặp nhau ở các đỉnh (i,j) có tọa độ

[4] Oystein Ore: Theory of Graphs. American Mathematical Society. 1967.
[5] Christofides Nicos : Graph Theory. Academic Press. New York London San
Francisco, 1975.
[6] R.G. Busacker & T.L. Saaty: Finite Graph and Networks. Mc Graw-Hill
Book Company. New York - St. Louis - San Francisco - Toronto - London -
Sydney, 1974.
z
a
0
1
2
k
-
1
-
2k
1
3
k
-3k
-
1
k
-
k
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).2008

105
[7] Kenneth H. Rosen: Discrete Mathematics and Its Applications. McGraw Hill
Book Company. New York 1994.