Thuật toán đích hướng nguồn tìm luồng cực đại trên mạng hỗn hợp mở rộng

Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 
DOI: 10.15625/vap.2015.000207 
THUẬT TOÁN ĐÍCH HƯỚNG NGUỒN 
TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG HỖN HỢP MỞ RỘNG 
Trần Ngọc Việt1, Trần Quốc Chiến2, Lê Mạnh Thạnh3 
1Cao đẳng CNTT Hữu nghị Việt-Hàn 
2Đại học Sư phạm-Đại học Đà Nẵng 
3Đại học Huế 
trviet01@yahoo.com, tqchien@dce.udn.vn, lmthanh1953@yahoo.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 đó, mà 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 hiệu quả hơn. Kết quả chính của bài báo là thuật toán đích hướng nguồn tìm luồng cực đại trên mạng 
hỗn hợp mở rộng, với ý tưởng chính của thuật toán là tìm đường đi tăng luồng từ đỉnh đích đến đỉnh nguồn trên mạng hỗn hợp mở 
rộng; bởi lẽ thông thường thuật toán Ford-Fulkerson tìm đường đi tăng luồng chỉ từ đỉnh nguồn đến đỉnh đích. 
Từ khóa - đồ thị, mạng hỗn hợp mở rộng, luồng, luồng cực đại, thuật toán. 
I. ĐẶ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, trong đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và các nút trên đường đi đó. 
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 đó, mà còn 
phụ thuộc vào tuyến đi đến và tuyến đi khỏi nút đó. Ví dụ thời gian đi qua ngã tư trên mạng giao thông phụ thuộc vào 
hướng di chuyển của phương tiện giao thông: rẽ phải, đi thẳng hay rẽ trái. 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], đồ thị mở rộng [7, 8] và mạng hỗn hợp mở rộng [9, 10, 11], nên bài báo phát triển 
thuật toán đích hướng nguồn tìm luồng cực đại trên mạng hỗn hợp mở rộng khác biệt so với thuật toán Ford-Fulkerson. 
II. MẠNG HỖN HỢP MỞ RỘNG 
Cho mạng là đồ 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. 
Có nhiều loại phương tiện lưu hành trên mạng. Những cạnh vô hướng biểu diễn tuyến hai chiều, trong đó các phương 
tiện trên cùng tuyến nhưng ngược hướng lưu hành chia sẻ khả năng thông hành của tuyến. Trên mạng 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. 
Bộ (V, E, cE, cV) gọi là mạng hỗn hợp mở rộng. 
III. LUỒNG 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). 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 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) 
Biểu thức 
674 THUẬT TOÁN ĐÍCH HƯỚNG NGUỒN TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG HỖN HỢP MỞ RỘNG 
 v(F) = ( )∑
∈Evs
vsf
),(
, , 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) với đỉnh nguồn a và đỉnh đích z. Nhiệm vụ của bài toán là tìm 
luồng 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ý 1. Với mỗi mạng hỗn hợp mở rộng G = (V, E, cE, cV) với đỉnh nguồn a và đỉnh đích z, luôn luôn tồn 
tại luồng cực đại [1]. 
IV. THUẬT TOÁN ĐÍCH HƯỚNG NGUỒN 
+ Đầu vào. Mạng hỗn hợp mở rộng G = (V, E, cE, cV) với đỉnh nguồn a và đỉnh đích z [4]. 
Các đỉnh trong G được sắp xếp theo thứ tự nào đó. 
+ Đầu ra. Luồng cực đại F = {f(x, y) | (x, y)∈E}, là tập các luồng trên mạng G. 
+ Các bước. 
(1) Khởi tạo 
Luồng xuất phát: f(x, y) := 0, ∀(x, y)∈E. 
Các đỉnh xuất phát sẽ được lần lượt gán nhãn lần thứ nhất L1 gồm 5 thành phần: 
Nhãn lùi có dạng: 
L1(v) = [↓ , prev1(v), c1(v), d1(v), bit1(v)] và có thể được gán nhãn lần hai 
L2(v) = [↓ , prev2(v), c2(v), d2(v), bit2(v)], với prev1(v) là đỉnh liền kề sau đối với nhãn lùi; 
Đặt nhãn lùi )(↓ cho đỉnh đích: 
 ]1,,,,[ ∞∞↓ φz 
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’ là tập đỉnh được gán nhãn 
lùi nhờ các đỉnh của tập T 
 { } φ== :' , : TzT 
 (2) Sinh nhãn lùi 
(2.1) Chọn đỉnh sinh nhãn lùi 
- Trường hợp φ≠T : Chọn đỉnh Tv ∈ nhỏ nhất (theo thứ tự). 
Loại v khỏi { }vTTT \: , = . Giả sử nhãn lùi của v là [↓ , previ(v), ci(t), di(t), biti(t)], i = 1 hoặc 2. B là tập các 
đỉnh chưa có nhãn lùi và kề đỉnh sinh nhãn lùi v. Sang bước 2.2. 
- Trường hợp φ=T và φ≠'T : Gán φ== :' ,': TTT . Quay lại bước 2.1. 
- Trường hợp φ=T và φ='T : Kết thúc, luồng F là cực đại. 
(2.2) Gán nhãn lùi cho đỉnh chưa có nhãn lùi và kề đỉnh sinh nhãn lùi v 
- Trường hợp φ=B : Quay lại bước 2.1. 
- Trường hợp φ≠B : Chọn Bt ∈ nhỏ nhất (theo thứ tự). Loại t khỏi B, { }tBB \:= . Gán nhãn lùi cho t như 
sau: 
Nếu 1)(),,(),(,),( =<∈ vbitvtcvtfEvt iE đặt nhãn lùi đỉnh t là: prevj(t) := v; 
cj(t):=min{ci(v), cE(t,v)−f(t,v)}, nếu di(v)=0, 
cj(t):=min{ci(v), cE(t,v)−f(t,v),di(v)}, nếu di(v) > 0; 
Trần Ngọc Việt, Trần Quốc Chiến, Lê Mạnh Thạnh 675 
dj(t) := cV(t)− ( )∑
∈Eti
tif
),(
, ; 
bitj(t):=1, nếu dj(t) > 0, 
bitj(t):=0, nếu dj(t) = 0. 
 Nếu 0),( ,),( >∈ tvfEtv đặt nhãn lùi đỉnh t là: prevj(t) := v; cj(t):=min{ci(v), f(v,t)}, 
dj(t) := cV(t)− ( )∑
∈Eti
tif
),(
, ; bitj(t):=1. 
Nếu t không được gán nhãn lùi, thì quay lại bước 2.2. 
Nếu t được gán nhãn lùi và t=a , thì sang bước hiệu chỉnh tăng luồng. Sang bước 3. 
Nếu t được gán nhãn lùi và at ≠ , thì bổ sung t vào T’, { }tTT ':' ∪= và quay lại bước 2.2. 
(3) Hiệu chỉnh tăng luồng 
Giả sử t có nhãn lùi [↓ , previ(t), ci(t), di(t), biti(t)]. Ta hiệu chỉnh luồng F như sau: 
(3.1) Hiệu chỉnh từ t đến z theo nhãn lùi 
(3.1.1) Khởi tạo 
 x := s, y := prev1(s), δ := c1(s). 
(3.1.2) Hiệu chỉnh 
 (i) Trường hợp (x, y) là cạnh có hướng từ x đến y: đặt f(x, y) := f(x, y) + δ. 
 (ii) Trường hợp (y, x) là cạnh có hướng từ y đến x: đặt f(y, x) := f(y, x) − δ. 
 (iii) Trường hợp (x, y) là cạnh vô hướng: 
 Nếu f(x, y) ≥ 0 và f(y, x) = 0, thì đặt f(x, y) := f(x, y) + δ. 
 Nếu f(y, x) > 0, thì đặt f(y, x) := f(y, x) − δ. 
(3.1.3) Tịnh tiến 
 (i) Trường hợp x = z, thì sang bước 3.2. 
 (ii) Trường hợp x ≠ z: Đặt x := y và y:=k, với k là thành phần thứ hai của nhãn lùi đỉnh x. Sau đó quay lại 
 bước (3.1.2). 
(3.2) Xóa tất cả nhãn của các đỉnh trên mạng mở rộng, trừ đỉnh đích z. Quay lại bước 2. 
• Định lý 2. Nếu các khả năng thông qua cạnh và khả năng thông qua đỉnh là số nguyên, thì sau hữu hạn bước 
quá trình giải kết thúc. 
Chứng minh 
Theo định lý 1, qua mỗi bước hiệu chỉnh luồng, giá trị luồng tăng lên 1 lượng đơn vị (do cE nguyên, cV nguyên, 
kéo theo δ nguyên dương). Mặt khác, giá trị luồng bị chặn trên bởi tổng các khả năng thông qua của các cung đi khỏi 
đỉnh nguồn. Vì vậy qua một số hữu hạn bước quá trình giải phải kết thúc. 
• Định lý 3. Cho F = {f(x,y) | (x,y)∈E} là luồng trên mạng hỗn hợp mở rộng G với đỉnh nguồn s và đỉnh đích t. 
Khi đó 
( ) ( )∑=∑
∈∈ EtxExs
txfxsf
),(),(
,, 
 Chứng minh 
Gọi V là tập các đỉnh. Với các đỉnh x, y không kề nhau ta gán .0),( =yxf
Ta có ∑ ∑=∑ ∑
∈ ∈∈ ∈ Vy VxVy Vx
xyfyxf ),(),( 
6
lu
đ
l
th
76 
∑⇔
∈y
⇔
∈Vy
∑−
xs,(
• Độ ph
Giả thiế
ồng ta phải d
ường đi tăng 
ần tăng luồng 
 Cho s
ông hành cạn
*) Gán 
 Đỉnh đ
 Đỉnh 5
 Đỉnh 4
 Đỉnh 3
 Đỉnh 2
 Đỉnh 1
Kết quả
(⎜⎜⎝
⎛ ∑
∈V Vx
xf
{ },\∑ ⎜
⎜⎝
⎛ ∑
∈ts Vx
f
( )+
∈E
xsf
()
,
ức tạp của th
t khả năng th
uyệt qua nhi
luồng. Như v
nhiều nhất là 
ơ đồ mạng hỗ
h cE và khả n
nhãn lùi lần th
ích 6: nhãn lù
: nhãn lùi ,[↓
: nhãn lùi ,[↓
: nhãn lùi ,[↓
: nhãn lùi [↓
: nhãn lùi ,[↓
 hiệu chỉnh tă
THUẬT T
(), ∑−
∈Vx
fy
),( ∑−
∈Vx
yx
( )∑
∈Etx
txf
),
,
uật toán. 
ông qua cạnh
ều nhất là |E|
ậy độ phức tạp
v*. Vì vậy độ
n hợp mở rộ
ăng thông hàn
ứ 1: 
i , , ,[ ∞↓ φ
]1 ,9 ,9 ,6 
 ,10 ,10 ,6 
]1 ,9 ,7 ,4 
 ,10 ,7 ,5 ,
1 , ,7 ,3 ∞
ng luồng cho
OÁN ĐÍCH HƯ
0), =⎟⎟⎠
⎞
xy
),( ⎜⎜⎝
⎛
+⎟⎟⎠
⎞
xyf
= 0
 và khả năng 
 cung và để h
 mỗi lần tăng
 phức tạp của
ng ở hình 1. M
h nút cV. Đỉn
Hình 1. S
Xuất phá
Hình 2.
]1 , ∞ 
]1 
]1 
] 
 ở hình 3 và g
ỚNG NGUỒN T
),(∑ −
∈Vx
txf
(∑⇔
∈Exs
f
),(
thông qua đỉn
iệu chỉnh luồ
 luồng là O(
 thuật toán là 
V. VÍ DỤ
ạng có 6 nú
h nguồn là 1,
ơ đồ mạng hỗn
t từ luồng 0 c
Mạng xuất phá
iá trị luồng v(
ÌM LUỒNG CỰ
),( ⎠
⎞∑
∈Vx
xtf
) ∑=
tx
xs
),(
,
h là số nguyê
ng ta phải du
|E | + 2.|V|). K
O(v*(|E | + 2.|
t, 6 cạnh có h
 đỉnh đích là 6
 hợp mở rộng 
ho ở hình 2 
t từ luồng 0 
F) = 7. 
C ĐẠI TRÊN M
(⎜⎜⎝
⎛ ∑+
∈Vx
xf
( )
∈E
txf , 
n. Ở mỗi bướ
yệt qua nhiều
ý hiệu v* là t
V|)). 
ướng và 3 cạ
. 
ẠNG HỖN HỢP
(), ∑−
∈Vx
sfs
c lặp tìm đườ
 nhất là 2.|V
rị của luồng c
nh vô hướng.
 MỞ RỘNG 
0), =⎟⎟⎠
⎞
x 
ng đi tăng 
| cung trên 
ực đại. Số 
 Khả năng 
Trần Ngọc Việt, T
 *) Gán
 Đỉnh đ
 Đỉnh 5
 Đỉnh 4
 Đỉnh 3
 Đỉnh 2
 Đỉnh 1
*) Gán 
 Đỉnh đ
 Đỉnh 5
 Đỉnh 4
 Đỉnh 3
 Đỉnh 2
 Đỉnh 1
rần Quốc Chiến,
 nhãn lùi lần t
ích 6: nhãn lù
: nhãn lùi ,[↓
: nhãn lùi ,[↓
: nhãn lùi ,[↓
: nhãn lùi [↓
: nhãn lùi ,[↓
nhãn lùi lần th
ích 6: nhãn lù
: nhãn lùi [↓
: nhãn lùi ,[↓
: nhãn lùi ,[↓
: nhãn lùi [↓
: nhãn lùi ,[↓
Đây là luồ
 Lê Mạnh Thạnh 
hứ 2: 
i , , ,[ ∞↓ φ
]1 ,9 ,9 ,6 
]1 ,3 ,5 ,5 
]1 ,2 ,6 ,5 
 ,10 ,7 ,5 ,
1 , ,7 ,2 ∞
Kết quả hiệu 
ứ 3: 
i , , ,[ ∞↓ φ
1 ,2 ,2 ,6 ,
]1 ,3 ,3 ,6 
]1 ,2 ,2 ,5 
1 ,3 ,2 ,3 ,
1 , ,2 ,2 ∞
Kết quả hiệu 
ng cực đại, v
Hình 3. M
]1 , ∞ 
]1 
] 
chỉnh tăng lu
Hình 4. M
]1 , ∞ 
] 
] 
] 
chỉnh tăng lu
Hình 5. M
ì trong lần sin
ạng có giá trị l
ồng cho ở hìn
ạng có giá trị lu
ồng cho ở hìn
ạng có giá trị lu
h nhãn lùi tiế
uồng v(F)= 7 
h 4 và giá trị 
ồng v(F)= 14
h 5 và giá trị 
ồng v(F)= 16
p theo, đỉnh 1
luồng v(F) = 
luồng v(F) = 
 không được 
14. 
16. 
gán nhãn lùi. 
677 
678 THUẬT TOÁN ĐÍCH HƯỚNG NGUỒN TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG HỖN HỢP MỞ RỘNG 
VI. KẾT LUẬN 
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à giảm khối lượng tính toán ở nhiều công đoạn này sẽ làm tăng đáng kể hiệu quả của thuật toán so với thuật toán [10] 
do gán nhãn đồng thời cả đỉnh nguồn và đỉnh đích. Ý tưởng của phương pháp trong báo cáo này là gán nhãn các đỉnh 
xuất phát từ đỉnh đích hướng đến đỉnh nguồn. Tiếp theo đó, bài báo xây dựng được thuật toán đích hướng nguồn tìm 
luồng cực đại trên mạng hỗn hợp mở rộng. Cuối cùng, một ví dụ cụ thể được trình bày để minh họa cho thuật toán trên. 
VII. TÀI LIỆU THAM KHẢO 
[1] 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. 
[2] 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, 1(13)/2006, 53-58. 
[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 (2)”, Tạp chí Khoa học & Công nghệ, Đại 
học Đà Nẵng, 3(15)-4(16)/2006, 77-82. 
[4] 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. 
[5] Trần Quốc Chiến, Hồ Xuân Bình,“Thuật toán song song tìm luồng cực đại”, Tạp chí Khoa học & Công nghệ, Đại 
học Đà Nẵng, 5(22)/2007, 37-42. 
[6] Trần Quốc Chiến,“Thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại”, Tạp chí Khoa học & Công 
nghệ, Đại học Đà Nẵng, 3(26)/2008, 99-105. 
[7] Trần Quốc Chiến,“Thuật toán tìm đường đi ngắn nhất trên đồ thị tổng quát”, Tạp chí Khoa học & Công nghệ, Đại 
học Đà Nẵng, 12(61)/2012, 16-21. 
[8] Trần Quốc Chiến, Nguyễn Mậu Tuệ, Trần Ngọc Việt, “Thuật toán tìm đường đi ngắn nhất trên đồ thị mở rộng”. 
Proceeding of the 6th National Conference on Fundamental and Applied Information Technology Research (FAIR), 
Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ VI “Nghiên cứu cơ bản và ứng dụng CNTT”, Huế, 20-21/6/2013. 
NXB Khoa học tự nhiên và Công nghệ. Hà Nội 2013. 522-527. 
[9] Trần Ngọc Việt, Trần Quốc Chiến, Nguyễn Mậu Tuệ, "Bài toán phân luồng giao thông đa phương tiện tuyến tính 
tối ưu trên mạng giao thông", Kỷ yếu Hội nghị Quốc gia lần thứ VII về Nghiên cứu cơ bản và ứng dụng Công nghệ 
thông tin FAIR 2014, DOI 10.15625/FAIR VII.2014-0394, 31-39. 
[10] Trần Ngọc Việt, Trần Quốc Chiến, Lê Mạnh Thạnh, "Thuật toán Ford-Fulkerson cải biên tìm luồng cực đại trên 
mạng hỗn hợp mở rộng", Kỷ yếu Hội nghị Quốc gia lần thứ VII về Nghiên cứu cơ bản và ứng dụng Công nghệ 
thông tin FAIR 2014, DOI 10.15625/FAIR VII.2014-0394, 643-649. 
[11] Trần Quốc Chiến, Trần Ngọc Việt, Nguyễn Đình Lầu,“Thuật toán tìm luồng cực đại trên mạng mở rộng”, Tạp chí 
Khoa học & Công nghệ, Đại học Đà Nẵng, 1(74)/2014, 1-4. 
[12] Taylor, M. A. P., editor: Transportation and Traffic theory in the 21st Century, Pergamon Press Amsterdam, The 
Netherlands, 2002. 
[13] Ellis L. Johnson, Committee Chair, George L.Nemhauser: Shortest paths and multicommodity network flow, 2002. 
SINK TOWARD SOURCE ALGORITHM FINDING MAXIMAL FLOWS ON 
EXTENDED NETWORKS 
Tran Ngoc Viet, Tran Quoc Chien, Le Manh Thanh 
ABSTRACT - Graph is a powerful mathematical tool applied in many fields as transportation, communication, informatics, 
economy, In 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 depend on coming and leaving edges. The paper develops a model of extended network 
that can be applied to modellingmany practical problems more exactly and effectively. The main contribution of this paper is sink 
toward source algorithm finding maximal flows on extended mixed networks. 
Keywords - graph, extended mixed networks, network, flow, maximal Flow, algorithm.