- Trang Chủ
- Toán học
- 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
Xem mẫu
- 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
1
Trường Đại học Sư phạm, Đại học Đà Nẵng, Email: tqchien@dce.udn.vn
2
Trườ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 Abstract - Graph is a powerful mathematical tool applied in many
lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh fields as transportation, communication, informatics, economy, …
tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các In an ordinary graph the weights of edges and vertexes are
cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi là tổng considered independently where the length of a path is the sum of
trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong weights of the edges and the vertexes on this path. However, in
thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi many practical problems, weights at a vertex are not the same for
qua đỉnh đó, nó còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh all paths passing this vertex, but they depend on coming and
đó. Bài viết xây dựng mô hình mạng hỗn hợp mở rộng để có thể leaving edges. This paper develops a model of mixed extended
á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ả network that can be applied to modelling many practical problems
hơn. Kết quả chính của bài viết là thuật toán đường đi tăng luồng more exactly and effectively. The main contribution of this paper is
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 the augmenting-path maxflow algorithm and the Maxflow-Mincut
ứng trên mạng hỗn hợp mở rộng. 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 đề 3. Luồng cạnh trên mạng hỗn hợp mở rộng
Mạng và luồng trên mạng là công cụ toán học hữu ích Cho mạng hỗn hợp mở rộng G = (V, E, ce, cv, be, bv).
ứng dụng trong nhiều lĩnh vực như giao thông, truyền Giả thiết G có đỉnh nguồn s và đỉnh đích t. Tập các giá trị
thông, công nghệ thông tin, kinh tế,… Cho đến nay trong {f(x, y) | (x, y)E}
mạng cổ điển mới chỉ xét đến trọng số của các tuyến và gọi là luồng cạnh trên mạng G nếu thoả mãn.
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 (i) 0 f(x, y) ce(x, y) (x, y)E
đường đi qua nút đó, nó còn phụ thuộc vào tuyến đi đến (ii) Với mọi đỉnh z không phải nguồn hoặc đích
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
f (v, z ) = f (z, v)
( v , z )E ( z ,v )E
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] (iii) Với mọi đỉnh z không phải nguồn hoặc đích
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
f (v, z ) cv(z)
( v , z )E
mở rộng.
• Định lý 1. Cho f = {f(x, y) | (x, y)E} là luồng cạnh
2. Mạng hỗn hợp mở rộng trên mạng G với nguồn s và đích t. Khi đó
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à
f (s, v) − f (v, s )
( s ,v )E ( v ,s )E
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à
= f (v, t ) − f (t, v )
( v ,t )E ( t ,v )E
khả năng thông hành cạnh e E.
Chứng minh. Ta quy ước, với các đỉnh x, y không có
Hàm khả năng thông hành nút cv: V→R*, với cv(u) là cạnh từ x đến y, gán f(x, y)= 0. Ta có
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 f (u, v ) = f (v, u )
uV vV vV uV
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.
f (u, v ) − f (v, u ) = 0
vV uV uV
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’.
f (u, v ) − f (v, u ) +
vV \ s , t uV uV
Bộ (V, E, ce, cv, be, bv) gọi là mạng hỗn hợp mở rộng.
- ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 9(82).2014 33
( f (u, s ) − f (s, u ) ) +
( u ,s )E ( s ,u )E
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ó
( f (u, t ) − f (t, u ) ) = 0 val(f) = f (s, u ) − f (u, s )
( s ,u )E ( u ,s )E
( u ,t )E ( t ,u )E
Theo tính chất (ii) của luồng cạnh, số hạng thứ nhất
bằng 0. Suy ra
= f (s, u ) − f (u, s )
uV uV
( f (u, s ) − f (s, u ) ) +
( u ,s )E ( s ,u )E
= f (v, u ) − f (u, v )
vS uV vS uV
( f (u, t ) − f (t, u ) ) = 0
( u ,t )E ( t ,u )E
(vì vS\{s}, f (v, u ) − f (u, v ) =0)
uV uV
f (s, u ) − f (u, s ) =
( s ,u )E ( u ,s )E
= f (v, u ) + f (v, u )
vS uS vS uT
f (u, t ) −
( u ,t )E
f (t, u )
( t ,u )E
−( f (u, v ) + f (u, v ) )
vS uS vS uT
• Giá trị của luồng = f (v, u ) − f (u, v )
vS uS vS uS
Biểu thức
+ f (v, u ) − f (u, v )
val(f) = f (s, u ) − f (u, s ) vS uT vS uT
f (v, u ) − f (u, v )
( s ,u )E ( u ,s )E
=
gọi là giá trị của luồng f. vS uT vS uT
• Bài toán luồng cực đại: = f(S, T)−f(T, S).
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 lát cắt (S, T). Ký hiệu
Nhiệm vụ của bài toán là tìm luồng cạnh có giá trị S(T) = {uS| vT, (u, v)(S, T)}
lớn nhất.
• Định lý 4. Cho f = {f(x, y) | (x, y)E} là luồng cạnh
Bài toán luồng cực đại là bài toán quy hoạch tuyến tính. trên mạng G và (S, T) là lát cắt của G. Khi đó, với mọi
Giá trị của luồng bị giới hạn bởi tổng khả năng thông hành S’S(T) ta có
của các cung đi ra từ đỉnh nguồn, vì vậy ta có thể khẳng
định định lý sau: f(S, T) c (v ) + ( x, y )(
V cE (x, y )
vS '
• Định lý 2. Cho mạng hỗn hợp mở rộng G = (V, E, ce, S ,T )\( S ',T )
cv, be, bv) với đỉnh nguồn s và đỉnh đích t. Khi đó tồn tại Chứng minh. Ta có
f ( x, y )
luồng cực đại.
f(S, T) =
4. Luồng cực đại lát cắt cực tiểu ( x , y )( S ,T )
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ý
= f (x, y ) +
( x , y )( S ',T )
f (x, y )
( x , y )( S ,T )\( S ',T )
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 = f (x, y ) +
xS ' ( x , y )({ x},T )
f (x, y )
( x , y )( S ,T )\( S ',T )
(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 & c (v ) + ( x, y )(
V cE (x, y )
ST = , và s S, tT, thì tập (S, T) gọi là lát cắt vS ' S ,T )\( S ',T )
(nguồn−đỉnh) của G. • Khả năng thông qua của lát cắt
Cho f = {f(x, y) | (x, y)E} là luồng cạnh trên mạng G. Ký hiệu Cho (S, T) là lát cắt của mạng mở rộng G. Giá trị
f(S, T) = f ( x, y ) cap(S, T) = min{ cv(v ) + ( x, y )( ce(x, y ) |S’S(T)}
( x , y )( S ,T ) vS ' S ,T )\( S ',T )
• Định lý 3. Cho mạng hỗn hợp mở rộng G = (V, E, ce, gọi là khả năng thông qua của lát cắt (S, T).
cv, be, bv) với đỉnh nguồn s và đỉnh đích t. Cho f = {f(x, y) Từ định lý 3 và định lý 4 suy ra
| (x, y)E} là luồng cạnh trên mạng G và (S, T) là lát cắt • Định lý 5. Cho f = {f(x, y) | (x, y)E} là luồng cạnh
của G. Khi đó trên mạng G và (S, T) là lát cắt của G. Khi đó val(f)
val(f) = f(S, T)−f(T, S) 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ư Kết luận: Không tồn tại đường đi tăng luồng. Kết thúc.
Cho luồng cạnh f = {f(x, y) | (x, y)E} trên mạng hỗn (3) Thêm cạnh:
hợp mở rộng G = (V, E, ce, cv, be, bv) với đỉnh nguồn s và Gọi u là đỉnh trước v trong ngăn xếp.
đỉ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 Tìm đỉnh wKe(v) thỏa wM.
khả năng thông qua cạnh cef và hàm khả năng thông qua (3a) Trường hợp tồn tại đỉnh w:
đỉnh cvf như sau: Nếu cvf(v)>0, thì
Với mọi cạnh hoặc cung (u, v) E, nếu f(u, v) > 0 thì {Đẩy w vào ngăn xếp M và đưa w vào S;
(v, u) Ef với khả năng thông qua cef(v, u) = f(u, v). Nếu cvf(w)>0, thì đặt
Với mọi cạnh hoặc cung (u, v) E, nếu ce(u, v) −f(u, (w):=min{cef(v, w), cvf(w),(v)}
v) > 0 thì (u, v) Ef với khả năng thông qua cef(u, v) =
Nếu cvf(w)=0, thì đặt
ce(u, v) − f(u, v).
(w):=min{cef(v, w)), cv(w),(v)}
Với mọi đỉnh vV, khả năng thông qua cvf(v)= cv(v)−
f ( x, v ) .
}
( x , v )E
Nếu cvf(v)=0, thì
• Đường đi tăng luồng {Nếu (w, v)E, thì
Đường đi tăng luồng là đường đi có hướng trong mạng {Đẩy w vào ngăn xếp M và đưa w vào S;
thặng dư thông qua Gf từ đỉnh nguồn s đến đỉnh đích t, sao Đặt (w):=min{cef(v, w),(v)}
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
Nếu (v, w)E& (v, u)E, thì
trên mạng thặng dư.
{Đẩy w vào ngăn xếp M và đưa w vào S;
• Thuật toán tìm kiếm chiều sâu cải biên
Đặt (w):=min{cef(v, w),(v)}
Đầ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:
Quay lại bước (1).
Đường đi tăng luồng p từ s đến t.
(3b) Trường hợp không tồn tại đỉnh w:
(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. Đẩy v ra khỏi ngăn xếp M;
Ký hiệu: M là ngăn xếp các đỉnh duyệt. S là tập hợp các Quay lại bước (1).
đỉnh duyệt, Ke(v) là tập hợp các đỉnh kề sau v,(v) là nhãn (4) Đường đi tăng luồng:
đỉnh v. Các đỉnh trong ngăn xếp M theo thứ tự từ đáy đến đỉnh
Các bước: tạo thành đường đi tăng luồng với luồng tăng là (t)>0.
(0) Khởi tạo: Kết thúc.
Khởi tạo ngăn xếp M:= [s], S:= {s}. • Định lý 6. Cho f = {f(x, y) | (x, y)E} là luồng cạnh
trên mạng G. Khi đó
(1) Xét đỉnh:
(i) Nếu tồn tại đường đi tăng luồng từ s đến t trong mạng
Xét đỉnh đầu vM. thặng dư Gf, thì tồn tại luồng
Nếu v=s, sang bước (2);
g = {g(x, y) | (x, y)E}
Nếu vs và vt, sang bước (3);
có val(g) = val(f) + (t).
Nếu v=t, sang bước (4);
(ii) Nếu không tồn tại đường đi tăng luồng từ s đến t
(2) Thêm cạnh nguồn: trong mạng thặng dư Gf, thì luồng f là luồng cực đại.
Tìm đỉnh (theo thứ tự nào đó)wKe(s) thỏa w M. Chứng minh
(2a) Trường hợp tồn tại đỉnh w: (i) Giả sử p là đường đi tăng luồng từ s đến t, Ta xây
Đẩy w vào ngăn xếp M. dựng luồng g như sau:
Đưa w vào S. Với mọi cạnh (x, y)p
Nếu cvf(w)>0, thì đặt g(x, y) = f(x, y)+(t), nếu (x, y)E có hướng hoặc
(w):=min{cef(s, w), cvf(w)} ((x, y)E vô hướng và f(x, y)0)
(2b) Trường hợp không tồn tại đỉnh w: 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) Chứng minh. Sau mỗi lần hiệu chỉnh tăng luồng, giá trị
Hiển nhiên g là luồng trong G và 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,
val(g) = val(f) + (t). luồng nhận được là luồng cực đại.
(ii) Ký hiệu S là tập đỉnh được duyệt và T là tập đỉnh • Độ phức tạp của thuật toán.
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. 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
Theo thuật toán, ta có f(e)=0, e(T, S), kéo theo luồng ta phải duyệt qua nhiều nhất là 2.E cạnh trong mạng
f(T, S)=0 (1). Đặt thặng dư Gf và để hiệu chỉnh luồng ta phải duyệt qua nhiều
S’:={uS(T)|vT:(u, v)(S, T)&f(u, v)
- 36 Trần Quốc Chiến, Trần Ngọc Việt, Nguyễn Đình Lầu
0 5
0 0 10 5
0 0 0 5 2
2
0 0 0 5
0 7
Hình 2. Luồng giá trị 0 Hình 6. Luồng giá trị 10
Vòng 1: Đường đi tăng luồng là Vòng 5: Đường đi tăng luồng là
1→2→3→4→5→6 1→3→2→5→4→6
với luồng tăng (6) = 5. với luồng tăng (6) = 2.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 3 và giá trị Kết quả hiệu chỉnh tăng luồng cho ở Hình 7 và giá trị
luồng val(f) = 5. luồng val(f) = 12.
0
5 7
5 10 5
5 0 5 3 2 0
0 0 2 7
5 7
Hình 3. Luồng giá trị 5 Hình 7. Luồng giá trị 12
Vòng 2: Đường đi tăng luồng là Vòng 6: Đường đi tăng luồng là
1→2→5→3→4→6 1→3→5→4→6
với luồng tăng (6) = 2. 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ị Kết quả hiệu chỉnh tăng luồng cho ở Hình 8 và giá trị
luồng val(f) = 7. luồng val(f) = 14.
2 7
7 5 10 5
5 2
5 3 0
2
0 2 4
7 9
7
Hình 4. Luồng giá trị 7 Hình 8. Luồng giá trị 14
Vòng 3: Đường đi tăng luồng là
Vòng 7: Đường đi tăng luồng là
1→2→5→4→6
1→3→5→4→6
với luồng tăng (6) = 2.
với luồng tăng (6) = 1.
Kết quả hiệu chỉnh tăng luồng cho ở Hình 5 và giá trị Kết quả hiệu chỉnh tăng luồng cho ở Hình 9 và giá trị
luồng val(f) = 9. luồng val(f) = 15.
4 7
9 5 10 5
5 2
3 3 1
3
0 4 5
7 10
7
Hình 5. Luồng giá trị 9 Hình 9. Luồng giá trị 15
Vòng 4: Đường đi tăng luồng là Vòng 8: Đường đi tăng luồng là
1→2→5→4→6 1→3→5→6
với luồng tăng (6) = 1. 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ị Kết quả hiệu chỉnh tăng luồng cho ở Hình 10 và giá trị
luồng val(f) = 10. luồng val(f) = 16.
- ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 9(82).2014 37
TÀI LIỆU THAM KHẢO
7
10 6 [1] Robert Sedgewick, Algorithms in C, Part 5: Graph Algorithms.
Addison-Wesley 8-2001.
3 2
3 [2] Trần Quốc Chiến, Bài toán tìm luồng cực đại trên mạng, Đề tài
NCKH cấp Bộ, mã số B2005-16-34.
6 10
7 [3] Trần Quốc Chiến,“Thuật toán hoán chuyển nguồn đích tìm luồng
cực đại (1)”, Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng,
Hình 10. Luồng giá trị 16 1(13)/2006, 53-58.
[4] Trần Quốc Chiến,“Thuật toán hoán chuyển nguồn đích tìm luồng
Thực hiện thuật toán tìm kiếm chiều sâu ta nhận được tập cực đại (2)”, Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng,
các đỉnh duyệt S={1,2,3}, tập đỉnh không duyệt T={4,5,6}. 3(15)-4(16)/2006, 77-82.
Như vậy, đến đây không tồn tại đường đi tăng luồng. [5] Trần Quốc Chiến,“Thuật toán đích hướng nguồn tìm luồng cực đại”,
Tạp chí Khoa học & Công nghệ, Đại học Đà nẵng, 4(21)/2007, 1-6.
Tập S(T)={2,3}. Tập S’={3}, vì f(3,5)=2
nguon tai.lieu . vn
