32 Trần Quốc Chiến, Trần Ngọc Việt, Nguyễn Đình Lầu
THUẬT TOÁN ĐƯỜNG ĐI TĂNG LUỒNG TÌM LUỒNG CỰC ĐẠI
TRÊN MẠNG HỖN HỢP MỞ RỘNG
AUGMENTING-PATH MAXFLOW ALGORITHM ONEXTENDED MIXED NETWORKS
Trần Quốc Chiến1, Trần Ngọc Việt2, Nguyễn Đình Lầu2
1Trường Đại học Sư phạm, Đại học Đà Nẵng, Email: tqchien@dce.udn.vn
2Trường Cao Đẳng Giao thông Vận tải II, Email: trviet01@yahoo.com, launhi@gmail.com
Tóm tắt - Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều
lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh
tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các
cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi là tổng
trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong
thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi
qua đỉnh đó, nó còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh
đó. Bài viết xây dựng mô hình mạng hỗn hợp mở rộng để có thể
áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả
hơn. Kết quả chính của bài viết là thuật toán đường đi tăng luồng
tìm luồng cực đại và định lý luồng cực đại lát cắt cực tiểu tương
ứng trên mạng hỗn hợp mở rộng.
Abstract - Graph is a powerful mathematical tool applied in many
fields as transportation, communication, informatics, economy, …
In an ordinary graph the weights of edges and vertexes are
considered independently where the length of a path is the sum of
weights of the edges and the vertexes on this path. However, in
many practical problems, weights at a vertex are not the same for
all paths passing this vertex, but they depend on coming and
leaving edges. This paper develops a model of mixed extended
network that can be applied to modelling many practical problems
more exactly and effectively. The main contribution of this paper is
the augmenting-path maxflow algorithm and the Maxflow-Mincut
theorem on extended mixed networks.
Từ khóa - đồ thị; mạng; luồng; luồng cực đại; thuật toán.
Key words - Graph; Network; Flow; Maximal Flow; Algorithm.
1. Đặt vấn đề
Mạng và luồng trên mạng là công cụ toán học hữu ích
ứng dụng trong nhiều lĩnh vực như giao thông, truyền
thông, công nghệ thông tin, kinh tế,… Cho đến nay trong
mạng cổ điển mới chỉ xét đến trọng số của các tuyến và
các nút một cách độc lập. Tuy nhiên, trong nhiều bài toán
thực tế, trọng số tại một nút không giống nhau với mọi
đường đi qua nút đó, nó còn phụ thuộc vào tuyến đi đến
và tuyến đi khỏi nút đó. Vì vậy cần xây dựng một mô hình
mạng mở rộng để có thể áp dụng mô hình hóa các bài
toán thực tế chính xác và hiệu quả hơn. Trên cơ sở các
nghiên cứu về bài toán luồng cực đại [1, 2, 3, 4, 5, 6, 7]
và đồ thị mở rộng [8, 9, 10], bài báo phát triển thuật toán
đường đi tăng luồng tìm luồng cực đại trên mạng hỗn hợp
mở rộng.
2. Mạng hỗn hợp mở rộng
Cho đồ thị hỗn hợp G=(V, E) với tập nút V và tập cạnh
E. Các cạnh có thể có hướng hoặc vô hướng. Ký hiệu R* là
tập số thực dương. Trên đồ thị cho các hàm sau.
Hàm khả năng thông hành cạnh ce: E→R*, với ce(e) là
khả năng thông hành cạnh e E.
Hàm khả năng thông hành nút cv: V→R*, với cv(u) là
khả năng thông hành nút u V.
Hàm chi phí cạnh be: E→R*, với be(e) là chi phí phải
trả để chuyển một đơn vị luồng qua cạnh e.
Với mỗi nút vV, ký hiệu Ev là tập các cạnh liên thuộc
nút v.
Hàm chi phí nút bv: VEvEv→R*, với bv(u, e, e’) là
chi phí phải trả để chuyển một đơn vị luồng từ tuyến e qua
nút u sang tuyến e’.
Bộ (V, E, ce, cv, be, bv) gọi là mạng hỗn hợp mở rộng.
3. Luồng cạnh trên mạng hỗn hợp mở rộng
Cho mạng hỗn hợp mở rộng G = (V, E, ce, cv, be, bv).
Giả thiết G có đỉnh nguồn s và đỉnh đích t. Tập các giá trị
{f(x, y) | (x, y)E}
gọi là luồng cạnh trên mạng G nếu thoả mãn.
(i) 0 f(x, y) ce(x, y) (x, y)E
(ii) Với mọi đỉnh z không phải nguồn hoặc đích
( )
Ezv
zvf
),(
,
=
( )
Evz
vzf
),(
,
(iii) Với mọi đỉnh z không phải nguồn hoặc đích
( )
Ezv
zvf
),(
,
cv(z)
• Định lý 1. Cho f = {f(x, y) | (x, y)E} là luồng cạnh
trên mạng G với nguồn s và đích t. Khi đó
( )
Evs
vsf
),(
,
−
( )
Esv
svf
),(
,
=
( )
Etv
tvf
),(
,
−
( )
Evt
vtf
),(
,
Chứng minh. Ta quy ước, với các đỉnh x, y không có
cạnh từ x đến y, gán f(x, y)= 0. Ta có
( ) ( )
−
Vv Vu Vu
uvfvuf ,,
= 0
( ) ( )
−
tsVv Vu Vu
uvfvuf
,\
,,
+
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 9(82).2014 33
(
( )
Esu
suf
),(
,
−
( )
Eus
usf
),(
,
) +
(
( )
Etu
tuf
),(
,
−
( )
Eut
utf
),(
,
) = 0
Theo tính chất (ii) của luồng cạnh, số hạng thứ nhất
bằng 0. Suy ra
(
( )
Esu
suf
),(
,
−
( )
Eus
usf
),(
,
) +
(
( )
Etu
tuf
),(
,
−
( )
Eut
utf
),(
,
) = 0
( )
Eus
usf
),(
,
−
( )
Esu
suf
),(
,
=
( )
Etu
tuf
),(
,
−
( )
Eut
utf
),(
,
• Giá trị của luồng
Biểu thức
val(f) =
( )
Eus
usf
),(
,
−
( )
Esu
suf
),(
,
gọi là giá trị của luồng f.
• Bài toán luồng cực đại:
Cho mạng hỗn hợp mở rộng G = (V, E, ce, cv, be, bv)
với đỉnh nguồn s và đỉnh đích t.
Nhiệm vụ của bài toán là tìm luồng cạnh có giá trị
lớn nhất.
Bài toán luồng cực đại là bài toán quy hoạch tuyến tính.
Giá trị của luồng bị giới hạn bởi tổng khả năng thông hành
của các cung đi ra từ đỉnh nguồn, vì vậy ta có thể khẳng
định định lý sau:
• Định lý 2. Cho mạng hỗn hợp mở rộng G = (V, E, ce,
cv, be, bv) với đỉnh nguồn s và đỉnh đích t. Khi đó tồn tại
luồng cực đại.
4. Luồng cực đại lát cắt cực tiểu
Cho mạng hỗn hợp mở rộng G = (V, E, ce, cv, be, bv)
với đỉnh nguồn s và đỉnh đích t. Với mọi tập S, T V, ký
hiệu tập các cạnh có hướngvà các cạnh vô hướng đi từ S
vào T là (S, T), tức
(S, T) = {(x, y) E x S &y T}
Nếu S, T V là phân hoạch của V, tức ST = V &
ST = , và s S, tT, thì tập (S, T) gọi là lát cắt
(nguồn
−
đỉnh) của G.
Cho f = {f(x, y) | (x, y)E} là luồng cạnh trên mạng G. Ký hiệu
f(S, T) =
( )
),(),(
,
TSyx
yxf
• Định lý 3. Cho mạng hỗn hợp mở rộng G = (V, E, ce,
cv, be, bv) với đỉnh nguồn s và đỉnh đích t. Cho f = {f(x, y)
| (x, y)E} là luồng cạnh trên mạng G và (S, T) là lát cắt
của G. Khi đó
val(f) = f(S, T)−f(T, S)
Chứng minh. Ta quy ước, với các đỉnh x, y không có
cạnh từ x đến y, gán f(x, y)= 0. Ta có
val(f) =
( )
Eus
usf
),(
,
−
( )
Esu
suf
),(
,
=
( )
Vu
usf ,
−
( )
Vu
suf ,
=
( )
Sv Vu
uvf ,
−
( )
Sv Vu
vuf ,
(vì vS\{s},
( )
Vu
uvf ,
−
( )
Vu
vuf ,
=0)
=
( )
Sv Su
uvf ,
+
( )
Sv Tu
uvf ,
− (
( )
Sv Su
vuf ,
+
( )
Sv Tu
vuf ,
)
=
( )
Sv Su
uvf ,
−
( )
Sv Su
vuf ,
+
( )
Sv Tu
uvf ,
−
( )
Sv Tu
vuf ,
=
( )
Sv Tu
uvf ,
−
( )
Sv Tu
vuf ,
= f(S, T)−f(T, S).
Cho lát cắt (S, T). Ký hiệu
S(T) = {uS| vT, (u, v)(S, T)}
• Định lý 4. Cho f = {f(x, y) | (x, y)E} là luồng cạnh
trên mạng G và (S, T) là lát cắt của G. Khi đó, với mọi
S’S(T) ta có
f(S, T)
( )
'Sv Vvc
+
( )
)',(\),(),(
,
TSTSyx Eyxc
Chứng minh. Ta có
f(S, T) =
( )
),(),(
,
TSyx
yxf
=
( )
)',(),(
,
TSyx
yxf
+
( )
)',(\),(),(
,
TSTSyx
yxf
=
( )
' )},({),(
,
Sx Txyx
yxf
+
( )
)',(\),(),(
,
TSTSyx
yxf
( )
'Sv Vvc
+
( )
)',(\),(),(
,
TSTSyx Eyxc
• Khả năng thông qua của lát cắt
Cho (S, T) là lát cắt của mạng mở rộng G. Giá trị
cap(S, T) = min{
( )
'Sv
vcv
+
( )
)',(\),(),(
,
TSTSyx
yxce
|S’S(T)}
gọi là khả năng thông qua của lát cắt (S, T).
Từ định lý 3 và định lý 4 suy ra
• Định lý 5. Cho f = {f(x, y) | (x, y)E} là luồng cạnh
trên mạng G và (S, T) là lát cắt của G. Khi đó val(f)
cap(S, T).
34 Trần Quốc Chiến, Trần Ngọc Việt, Nguyễn Đình Lầu
5. Mạng thặng dư
Cho luồng cạnh f = {f(x, y) | (x, y)E} trên mạng hỗn
hợp mở rộng G = (V, E, ce, cv, be, bv) với đỉnh nguồn s và
đỉnh đích t. Ta định nghĩa mạng thặng dư thông qua, ký
hiệu Gf, là mạng có tập đỉnh V và tập cung Ef cùng hàm
khả năng thông qua cạnh cef và hàm khả năng thông qua
đỉnh cvf như sau:
Với mọi cạnh hoặc cung (u, v) E, nếu f(u, v) > 0 thì
(v, u) Ef với khả năng thông qua cef(v, u) = f(u, v).
Với mọi cạnh hoặc cung (u, v) E, nếu ce(u, v) −f(u,
v) > 0 thì (u, v) Ef với khả năng thông qua cef(u, v) =
ce(u, v) − f(u, v).
Với mọi đỉnh vV, khả năng thông qua cvf(v)= cv(v)−
( )
Evx
vxf
),(
,
.
• Đường đi tăng luồng
Đường đi tăng luồng là đường đi có hướng trong mạng
thặng dư thông qua Gf từ đỉnh nguồn s đến đỉnh đích t, sao
cho ta có thể gửi luồng dương từ s đến t. Để tìm đường đi
tăng luồng ta sử dụng thuật toán tìm kiếm chiều sâu cải tiến
trên mạng thặng dư.
• Thuật toán tìm kiếm chiều sâu cải biên
Đầu vào: Mạng Gf, đỉnh nguồn s, đỉnh đích t.
Đầu ra:
(i) Trường hợp tồn tại đường đi tăng luồng:
Đường đi tăng luồng p từ s đến t.
(ii) Trường hợp không tồn tại đường đi tăng luồng: Tập hợp
S các đỉnh duyệt, tS.
Ký hiệu: M là ngăn xếp các đỉnh duyệt. S là tập hợp các
đỉnh duyệt, Ke(v) là tập hợp các đỉnh kề sau v,(v) là nhãn
đỉnh v.
Các bước:
(0) Khởi tạo:
Khởi tạo ngăn xếp M:= [s], S:= {s}.
(1) Xét đỉnh:
Xét đỉnh đầu vM.
Nếu v=s, sang bước (2);
Nếu vs và vt, sang bước (3);
Nếu v=t, sang bước (4);
(2) Thêm cạnh nguồn:
Tìm đỉnh (theo thứ tự nào đó)wKe(s) thỏa w M.
(2a) Trường hợp tồn tại đỉnh w:
Đẩy w vào ngăn xếp M.
Đưa w vào S.
Nếu cvf(w)>0, thì đặt
(w):=min{cef(s, w), cvf(w)}
Nếu cvf(w)=0, thì đặt
(w):=min{cef(s, w), cv(w)}
Quay lại bước (1).
(2b) Trường hợp không tồn tại đỉnh w:
Kết luận: Không tồn tại đường đi tăng luồng. Kết thúc.
(3) Thêm cạnh:
Gọi u là đỉnh trước v trong ngăn xếp.
Tìm đỉnh wKe(v) thỏa wM.
(3a) Trường hợp tồn tại đỉnh w:
Nếu cvf(v)>0, thì
{Đẩy w vào ngăn xếp M và đưa w vào S;
Nếu cvf(w)>0, thì đặt
(w):=min{cef(v, w), cvf(w),(v)}
Nếu cvf(w)=0, thì đặt
(w):=min{cef(v, w)), cv(w),(v)}
}
Nếu cvf(v)=0, thì
{Nếu (w, v)E, thì
{Đẩy w vào ngăn xếp M và đưa w vào S;
Đặt (w):=min{cef(v, w),(v)}
}
Nếu (v, w)E& (v, u)E, thì
{Đẩy w vào ngăn xếp M và đưa w vào S;
Đặt (w):=min{cef(v, w),(v)}
}
}
Quay lại bước (1).
(3b) Trường hợp không tồn tại đỉnh w:
Đẩy v ra khỏi ngăn xếp M;
Quay lại bước (1).
(4) Đường đi tăng luồng:
Các đỉnh trong ngăn xếp M theo thứ tự từ đáy đến đỉnh
tạo thành đường đi tăng luồng với luồng tăng là (t)>0.
Kết thúc.
• Định lý 6. Cho f = {f(x, y) | (x, y)E} là luồng cạnh
trên mạng G. Khi đó
(i) Nếu tồn tại đường đi tăng luồng từ s đến t trong mạng
thặng dư Gf, thì tồn tại luồng
g = {g(x, y) | (x, y)E}
có val(g) = val(f) + (t).
(ii) Nếu không tồn tại đường đi tăng luồng từ s đến t
trong mạng thặng dư Gf, thì luồng f là luồng cực đại.
Chứng minh
(i) Giả sử p là đường đi tăng luồng từ s đến t, Ta xây
dựng luồng g như sau:
Với mọi cạnh (x, y)p
g(x, y) = f(x, y)+(t), nếu (x, y)E có hướng hoặc
((x, y)E vô hướng và f(x, y)<ce(x, y))
và
g(y, x) = f(y, x)−(t), nếu (y, x)E có hướng hoặc
((x, y)E vô hướng và f(y, x)>0)
Với mọi cạnh (x, y)p
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 9(82).2014 35
g(x, y) = f(x, y)
Hiển nhiên g là luồng trong G và
val(g) = val(f) + (t).
(ii) Ký hiệu S là tập đỉnh được duyệt và T là tập đỉnh
không được duyệt. Theo bước (1b) của thuật toán: (S, T) là
lát cắt của G.
Theo thuật toán, ta có f(e)=0, e(T, S), kéo theo
f(T, S)=0 (1). Đặt
S’:={uS(T)|vT:(u, v)(S, T)&f(u, v)<ce(u, v)}
Theo định nghĩa S’ ta có
f(u, v)=ce(u, v), (u, v)(S, T)\(S’, T) (2)
Xét đỉnh uS’. Tồn tại vT, f(u, v)<ce(u, v).
Suy ra cv(u)=
( )
Eux
uxf
),(
,
=
( )
Eyu
yuf
),(
,
, vì nếu
ngược lại, đỉnh v được duyệt theo sau đỉnh u.
Mặt khác, (u, y), f(u, y)>0yT, vì nếu yS, thì u
được duyệt theo sauy, và kéo theo v được duyệt theo sauu,
mâu thuẫn với vT. Từ đó ta có
cv(u)=
( )
)},({),(
,
Tuyu
yuf
(3)
Kết hợp (1), (2), (3) ta có
val(f) =
( )
'Sv
vcv
+
( )
)',(\),(),(
,
TSTSyx
yxce
Theo định lý 5, flà luồng cực đại và (S, T) là lát cắt
cực tiểu.
6. Thuật toán đường đi tăng luồng tìm luồng cực đại
trên mạng hỗn hợp mở rộng
Đầu vào: Mạng hỗn hợp mở rộng G = (V, E, ce, cv, be,
bv) với đỉnh nguồn s và đỉnh đích t.
Đầu ra: Luồng cực đại
f = {f(x, y) | (x, y)G}
Các bước:
(0) Khởi tạo luồng xuất phát
Luồng xuất phát:
f = {f(x, y)=0 | (x, y)G}
(1) Tìm đường đi tăng luồng
Áp dụng thuật toán tìm kiếm chiều sâu tìm đường đi
tăng luồng từ s đến t trong đồ thị thặng dư Gf.
(2) Hiệu chỉnh luồng
Nếu tồn tại đường đi tăng luồng, thì hiệu chỉnh luồng
theo định lý 6, quay về bước (1).
Nếu không tồn tại đường đi tăng luồng, thì luồng f là
luồng cực đại. Kết thúc.
• Định lý 7 (tính đúng của thuật toán). Cho mạng mở
rộng G = (V, E, ce, cv, be, bv) với đỉnh nguồn s và đỉnh
đích t. Giả thiết khả năng thông qua cạnh và khả năng thông
qua đỉnh là số nguyên. Khi đó, sau hữu hạn bước quá trình
giải kết thúc và luồng nhận được khi kết thúc thuật toán là
luồng cực đại.
Chứng minh. Sau mỗi lần hiệu chỉnh tăng luồng, giá trị
luồng tăng ít nhất 1 đơn vị. Vì giá trị luồng bị giới hạn, nên
thuật toán phải kết thúc sau hữu hạn bước. Theo định lý 6,
luồng nhận được là luồng cực đại.
• Độ phức tạp của thuật toán.
Giả thiết khả năng thông qua cạnh và khả năng thông
qua đỉnh là số nguyên. Ở mỗi bước lặp tìm đường đi tăng
luồng ta phải duyệt qua nhiều nhất là 2.E cạnh trong mạng
thặng dư Gf và để hiệu chỉnh luồng ta phải duyệt qua nhiều
nhất là 2.V cạnh trên đường đi tăng luồng. Như vậy độ
phức tạp mỗi lần tăng luồng là O(2.E + 2.V). Ký hiệu v*
là trị của luồng cực đại. Số lần tăng luồng nhiều nhất là v*.
Vì vậy độ phức tạp của thuật toán là
O(v*(2.E + 2.V)).
7. Ví dụ
Cho sơ đồ mạng hỗn hợp mở rộng ở Hình 1.
Mạng có 6 nút, 6 cạnh có hướng và 3 cạnh vô hướng.
Khả năng thông hành cạnh ce cho ở Bảng 1, khả năng thông
hành nút cv cho ở Bảng 2, và chi phí qua đỉnh cho ở
Bảng 3. Đỉnh nguồn là 1, đỉnh đích là 6.
Hình 1. Sơ đồ mạng mở rộng
Bảng 1. Khả năng thông hành cạnh
Cạnh
ce
(1,2)
10
(1,3)
9
(2,3)
5
(2,5)
7
(3,4)
7
(3,5)
6
(4,6)
10
(4,5)
5
(5,6)
9
Bảng 2. Khả năng thông hành nút
Đỉnh
1
2
3
4
5
6
cv
10
9
10
9
Trong bài toán tìm luồng cực đại, tạm thời chưa sử dụng
chi phí cạnh và nút.
Thứ tự các đỉnh sử dụng trong thuật toán tìm kiếm chiều
sâu là 1, 2, 3, 4, 5, 6.
Xuất phát từ luồng 0 cho ở Hình 2:
36 Trần Quốc Chiến, Trần Ngọc Việt, Nguyễn Đình Lầu
Hình 2. Luồng giá trị 0
Vòng 1: Đường đi tăng luồng là
1→2→3→4→5→6
với luồng tăng (6) = 5.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 3 và giá trị
luồng val(f) = 5.
Hình 3. Luồng giá trị 5
Vòng 2: Đường đi tăng luồng là
1→2→5→3→4→6
với luồng tăng (6) = 2.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 4 và giá trị
luồng val(f) = 7.
Hình 4. Luồng giá trị 7
Vòng 3: Đường đi tăng luồng là
1→2→5→4→6
với luồng tăng (6) = 2.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 5 và giá trị
luồng val(f) = 9.
Hình 5. Luồng giá trị 9
Vòng 4: Đường đi tăng luồng là
1→2→5→4→6
với luồng tăng (6) = 1.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 6 và giá trị
luồng val(f) = 10.
Hình 6. Luồng giá trị 10
Vòng 5: Đường đi tăng luồng là
1→3→2→5→4→6
với luồng tăng (6) = 2.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 7 và giá trị
luồng val(f) = 12.
Hình 7. Luồng giá trị 12
Vòng 6: Đường đi tăng luồng là
1→3→5→4→6
với luồng tăng (6) = 2.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 8 và giá trị
luồng val(f) = 14.
Hình 8. Luồng giá trị 14
Vòng 7: Đường đi tăng luồng là
1→3→5→4→6
với luồng tăng (6) = 1.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 9 và giá trị
luồng val(f) = 15.
Hình 9. Luồng giá trị 15
Vòng 8: Đường đi tăng luồng là
1→3→5→6
với luồng tăng (6) = 1.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 10 và giá trị
luồng val(f) = 16.
0
0
0
0
0
0
0
0
0
5
0
5
0
5
5
5
0
0
7
0
5
2
7
5
5
2
2
9
0
5
2
7
3
5
4
4
10
0
5
2
7
2
5
5
5
10
2
3
2
7
0
5
7
7
10
4
3
0
7
2
5
9
7
10
5
3
1
7
3
5
10
7