1
Chương 1

MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT
ĐỒ THỊI. MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ
1. Định nghĩa đồ thị

Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này,
các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào
đó của đồ thị.
Giả sử V là tập hữu hạn, không rỗng các phần tử nào đó. Bộ G = (V,E) được
gọi là đồ thị hữu hạn. Mỗi phần tử của V gọi là một đỉnh và mỗi phần tử u = (x,y) của
E được gọi là một cạnh của đồ thị G = (V,E).
Xét một cạnh u của E khi đó tồn tại hai đỉnh x, y của V sao cho u = (x,y), ta
nói rằng x nối với y hoặc x và y phụ thuộc u.
- Nếu cạnh u = (x,y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh
kề nhau.
- Nếu u = (x,x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên.
- Nếu u = (x,y) mà x, y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y
thì u là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh ra, y là đỉnh vào.
- Khi giữa cặp đỉnh (x,y) có nhiều hơn một cạnh thì ta nói rằng những cạnh
cùng cặp đỉnh là những cạnh song song hay là cạnh bội.

a) b) c)


Hình 1.2

Định nghĩa 1. Đơn đồ thị vô hướng G = (V,E) bao gồm V là các tập đỉnh và E
là các tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.

Thí dụ 2.

Hình 2. Sơ đồ máy tính là đơn đồ thị vô hướng

Trong trường hợp giữa hai máy tính nào đó thường xuyên phải tải nhiều thông
tin người ta phải nối hai máy này bởi nhiều kênh thoại. Mạng với đa kênh thoại giữa
các máy được cho trong hình 3.
b
a
c
d
l
k
i
h
g e
b
a
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN

3
Hình 4. Sơ đồ mạng máy tính với đa kênh thông báo

Rõ ràng mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là
đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc có nhiều hơn) cạnh nối một cặp đỉnh
nào đó.
Trong mạng máy tính có thể có những kênh thoại nối một máy nào đó với
chính nó (chẳng hạn với mục đích thông báo). Mạng như vậy được cho trong hình 4.

b
a
g
c
d
k
i
h
e
c
d
l
k
i
h
g e
b
a
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN

4
Nếu trong mạng có thể có đa kênh thoại một chiều, ta sẽ phải sử dụng đến
khái niệm đa đồ thị có hướng:

Định nghĩa 5. Đa đồ thị có hướng G = (V,E) bao gồm V là các tập đỉnh và E là
họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e
1
,
e
2

Thí dụ 1. Xét đồ thị trong hình 1 ta có.
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3,
deg(d) = 1, deg(e) = 3, deg(g) = 0.

Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo. Trong ví dụ trên
đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có các tính chất sau:

Định lý 1. Giả sử G = (V,E) là đồ thị vô hướng với m cạnh. Khi đó
f e
g
d
c b
a
∑
∈
=
Vv
vm )deg(2
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN

5
Chứng minh. Rõ ràng mỗi cạnh e = (u,v) được tính một lần trong deg(u) và
một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số
cạnh.

Hệ quả. Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là đỉnh có bậc là số lẻ)
là một số chẵn.

Chứng minh. Thực vậy gọi V
1

Hình 2. Đồ Thị có hướng G

Thí dụ 3. Xét đồ thị cho trong hình 2. Ta có
deg
-
(a) = 1, deg
-
(b) = 2, deg
-
(c) = 2, deg
-
(d) = 2, deg
-
(e) = 2.
deg
+
(a) = 3, deg
+
(b) = 1, deg
+
(c) = 1, deg
+
(d) = 2, deg
+
(e) = 2.

Do mỗi cung (u,v) sẽ được tính một lần trong bán bậc vào của đỉnh v và một
lần trong bán bậc ra của đỉnh u nên ta có:

Định lý 2. Giả sử G = (V,E) là đồ thị có hướng. Khi đó

nguyờn dng, trờn th vụ hng G = (V,E) l dóy
x
0
, x
1
,, x
n-1
, x
n

Trong ú u = x
0
, v = x
n
, v = (x
i
, x
i+1
)

E, i = 0,1,2,, n-1.
ng i núi trờn cũn cú th biu din di dng dóy cỏc cnh:
(x
0
,x
1
), (x
1
,x
2

x
0
, x
1
,, x
n-1
, x
n

trong ú u = x
0
, v = x
n
, (x
i
, x
i+1
)

A, i = 0, 1, 2,, n-1.
ng i núi trờn cũn cú th biu din di dng dóy cỏc cung:
(x
0
, x
1
), (x
1
, x
2
), (x

→
a khơng là đường đi, do (e,c) khơng phải là cạnh
của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đường đi a
→
b
→
e
→
d
→
a
→
b có
độ dài là 5 khơng phải là đường đi đơn, do cạnh (a,b) có mặt trong nó hai lần.
Xét một mạng máy tính. Một câu hỏi đặt ra là hai máy tính bất kỳ trong mạng
này có thể trao đổi thơng tin được với nhau hoặc là trực tiếp qua kênh nối chúng hoặc
thơng qua một hoặc vài máy trung gian trong mạng? Nếu sử dụng đồ thị để biểu diễn
mạng máy tính này (trong đó các đỉnh của đồ thị tương ứng với các máy tính, còn các
cạnh tương ứng của các kênh nối) câu hỏi đó được phát biểu trong ngơn ngữ đồ thị
như sau: Tồn tại hay chăng đường đi giữa mọi cặp đỉnh của đồ thị?

Định nghĩa 3. Đồ thị vơ hướng G = (V,E) được gọi là liên thơng nếu ln tìm
được đường đi giữa hai đỉnh bất kỳ của nó.

Như vậy hai máy tính bất kỳ trong mạng có thể trao đổi thơng tin được với
nhau khi và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thơng.

Thí dụ 3. Trong hình 2: Đồ thị G là liên thơng, còn đồ thị H là khơng liên
thơng.


và lặp lại
q trình đối với u. Ở bước tổng qt, giả sử ta đang xét đỉnh v, Nếu nhử tổng số các
đỉnh kề với v tìm được đỉnh w là chưa được xét thì ta sẽ xét đỉnh này( nó sẽ trở thành
đã xét) và bắt đầu từ nó ta sẽ tiếp tục q trình tìm kiếm. Còn nếu như khơng còn
đỉnh nào kề với v là chưa xét thì ta sẽ nói rằng đỉnh này là đã duyệt xong và quay trở
e
g
d
e
c
b
a
G
H
2
H
3
H
1
H

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

8
lại tiếp tục tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v (nếu v = v
0
, thì kết thúc
tìm kiếm). Có thể nói nơm na là tìm kiếm theo chiều sâu bắt đầu từ đỉnh v được thực
hiện trên cơ sở tìm kiếm theo chiều sâu từ tất cả các đỉnh chưa xét kề với v. Q trình
này có thể mơ tả bởi thủ tục đệ qui sau đây.

tốn lần lượt sẽ tiến hành tìm kiếm từ các đỉnh chưa được thăm, vì vậy, nó sẽ xét qua
tất cả các đỉnh của đồ thị (khơng nhất thiết phải là liên thơng).
Để đánh giá độ phức tạp tính tốn của thủ tục, trước hết nhận thấy rằng số
phép tốn cần thực hiện trong hai chu trình của thuật tốn( hai vòng for của chương
trình chính) là cỡ n. Thủ tục DFS phải thực hiện khơng q n lần. Tổng số phép tốn
cần phải thực hiện trong các thủ tục này là O(n+m), do trong các thủ tục này ta phải
xét qua tất cả các cạnh và các đỉnh của đồ thị. Vậy độ phức tạp tính tốn của thuật
tốn là O(n+m).

Thí dụ 1. Xét đồ thị cho trong Hình 1. Các đỉnh của nó được đánh số lại theo
thứ tự chúng được thăm theo thủ tục tìm kiếm theo chiều sâu mơ tả ở trên. Giả thiết
rằng các đỉnh trong danh sách kề của đỉnh v (Ke(v)) được sắp xếp theo thứ tự tăng
dần của chỉ số.

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

9


QUEUE:<= v; (* Kết nạp v vào QUEUE *)
Chuaxet[v]:= false;
While QUEUE
≠

∅
do
begin
p <= QUEUE; (* Lấy p từ QUEUE *)
Thăm_đỉnh(p);
12(11
)
4(3
)
13(10
)
9(7
)
8(6
)
6(4
)
5(5
)
7(8
)
3(9
)
2(2
)

if Chuaxet[v] then BFS(v);
END.

Lp lun tng t nh trong th tc tỡm kim theo chiu sõu, cú th ch ra
c rng lnh gi BFS(v) s cho phộp n thm tt c cỏc nh thuc cựng thnh
phn liờn thụng vi nh v, v mi nh ca th s c thm ỳng mt ln.
phc tp tớnh toỏn ca thut toỏn l O(n+m).

Thớ d 2. Xột th trong Hỡnh 2. Th t thm nh ca th ny theo thut
toỏn tỡm kim theo chiu rng c ghi trong ngoc.
Hỡnh 2. Ch s mi (trong ngoc) ca cỏc nh c ỏnh li theo th t
chỳng c thm trong thut toỏn tỡm kim theo chiu rng

1.3 Tỡm ng i v kim tra tớnh liờn thụng

12(4
)
4(3

Bi toỏn tỡm ng i gia hai nh
Gi s s v t l hai nh no ú ca th. Hóy tỡm ng i t s n t.

Nh trờn ó phõn tớch, th tc DFS(s) (BFS(s)) s cho phộp thm tt c cỏc
nh thuc cựng mt thnh phn liờn thụng vi s. Vỡ vy, sau khi thc hin xong th
tc, nu Chuaxet[t] = true, thỡ iu ú cú ngha l khụng cú ng i t s n t, cũn
nu Chuaxet[t] = false thỡ t thuc cựng thnh phn liờn thụng vi s, hay núi mt cỏch
khỏc: Tn ti ng i t s n t. Trong trng hp tn ti ng i, ta dựng thờm
bin Truoc[v] ghi nhn nh i trc nh v trong ng i tỡm kim t s n v.
Khi ú, i vi th tc DFS(v) cn sa i cõu lnh if trong nú nh sau:

if Chuaxet[u] then
begin
Truoc[u]:=v;
DFS(u);
end;

Cũn i vi th tc BFS(v) cn sa i cõu lnh cõu lnh if trong nú nh sau:

if Chuaxet[u] then
begin
QUEUE

u; Chuaxet[u]:= false;
Truoc[u]:= p;
end;

ng i cn tỡm s c khụi phc theo quy tc sau:
T


THệ VIEN ẹIEN Tệ TRệẽC TUYEN

12
l mt ng i trờn G, thỡ di ca nú c nh ngha l tng sau

=

p
i
ii
vva
1
1
),(

Tc l, di ca ng i chớnh l tng cỏc trng s trờn cỏc cung ca nú.
(Chỳ ý rng nu chỳng ta gỏn trng s cho tt c cỏc cung u bng 1, thỡ ta thu c
nh ngha di ca ng i nh l s cung ca ng i ging nh trong cỏc
phn trc ó xột).
Bi toỏn tỡm ng i ngn nht trờn th di dng tng quỏt cú th phỏt
biu nh sau: Tỡm ng i cú di nh nht t mt nh xut phỏt s

V n nh
cui (ớch) t

V. ng i nh vy ta s gi l ng i ngn nht t s n t cũn
di ca nú ta s ký hiu l d(s,t) v cũn gi l khong cỏch t s n t (khong cỏch
nh ngha nh vy cú th l s õm). Nu nh khụng tn ti ng i t s n t thỡ ta
s t d(s,t) = . Rừ rng, nu nh mi chu trỡnh trong th u cú di dng,
thỡ trong ng i ngn nht khụng cú nh no b lp li (ng i khụng cú nh

Mng STACK cha dóy nh xỏc nh ng i nhn nht t s n t
*)
begin
STACK:=; STACK t; v:= t;
THệ VIEN ẹIEN Tệ TRệẽC TUYEN

13
While v ≠ s do
begin
u:= đỉnh thoả mãn d[v] = d[u] + a[u,v];
STACK ⇐ u;
v:= u;
end;
end;

Chú ý rằng độ phức tạp tính tốn của thuật tốn là O(n
2
), do để tìm đỉnh u ta
phải xét qua tất cả các đỉnh của đồ thị. Tất nhiên, ta cũng có thể sử dụng kỹ thuật ghi
nhận đường đi trong phần trên: Dùng biến biến mảng Truoc[v], v
∈
V, để ghi nhớ
đỉnh đi trước v trong đường đi tìm kiếm.
Cần lưu ý thêm là trong trường hợp trọng số trên các cạnh là khơng âm, bài
tốn tìm đường đi ngắn nhất trên đồ thị vơ hướng có thể dẫn về bài tốn trên đồ thị có
hướng, bằng cách thay mỗi cạnh của nó bởi hai cung có hướng ngược chiều nhau với
cùng trọng số của các cạnh tương ứng. Tuy nhiên, trong trường hợp có trọng số âm
việc thay như vậy có thể dẫn đến chu trình âm.

2.2 Thuật tốn Ford – Bellman

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

14
s

V l nh xut phỏt,
a[u,v], u, v

V, ma trn trng s;
Gi thit: th khụng cú chu trỡnh õm.
u ra: Khong cỏch t nh s n tt c cỏc nh cũn li d[v], v

V.
Truoc[v], v

V, ghi nhn nh i trc v trong ng i ngn nht t s
n v
*)
begin
(* Khi to *)
for v V do
begin
d[v]:= a[s,v];
Truoc[v]:= s;
end;
d[s]:= 0;
for k:= 1 to n-2 do
for v V \ {s} do
for u V do
if d[v] > d[u] + a[u,v] then

15
Thớ d 1. Xột th cho trong hỡnh 1. Cỏc kt qu tớnh toỏn theo thut toỏn
c mụ t trong bng di õy.

Hỡnh 1. Minh ho cho thut toỏn Ford-Bellman k d[1],
Truoc[1]
d[2],
Truoc[2]
d[3],
Truoc[3]
d[4],
Truoc[4]
d[5],
Truoc[5]
0,1 1,1
,1 ,1
3,1
1 0,1 1,1 4,2 4,2 -1,3


V.Truoc[v],
v

V
ghi nhn nh i trc v trong ng i ngn nht t s n v*)
Begin
A =
(1)

4
(4)

5
(8)

(3)

(-5)

(2)

3
(3)

(3)

(1)

5

T:= T\{u}; (* Cố định nhãn của đỉnh u *)
for v
∈
T do (* Gán lại nhãn cho các đỉnh trong T *)
if d[v] > d[u] + a[u,v] then
begin
d[v]:= d[u] + a[u,v];
Truoc[v]:= u;
end;
end;
end;

Định lý 1. Thoật tốn Dijkstra tìm được đường đi ngắn nhất trên đồ thị sau
thời gian cỡ O(n
2
)

Chứng minh : Trước hết ta chứng minh là thuật tốn tìm được đường đi ngắn
nhấttừ đỉnh s đến các đỉnh còn lại của đồ thị, Giả sử rằng ở một bước lặp nào đó các
nhãn cố định cho ta độ dài đường đi ngắn nhất từ s đến các đỉnh có nhãn cố định, ta
sẽ chứng minh ở lần lặp tiếp theo nếu đỉnh u* thu được nhãn cố định thì d(u
*
) chính
là độ dài đường đi ngắn nhất từ s đến u
*
.
Ký hiệu S
l
là tập các đỉnh có nhãn cố định còn S
2

phải nằm trọn trong S
1
và thế d[u
*
] là
độ dài của nó. Do ở lần lặp đậu tiên S
1
= {s} và sau mỗi lần lặp tạo thêm vào S
1
một
đỉnh u
*
nên giả thiết d(v) cho độ dài đường đi ngắn nhất s đến v với mọi v
∈
S
1
là
đúng với bước lặp đậu tiên. Theo qui nạp suy ra thuật tốn cho ta đường đi ngắn nhất
từ s đến đỉnh của đồ thị .
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

17
Bõy gi s ỏnh gớa s phộp toỏn cn thc hin theo thut toỏn . mi bc
lp li tỡm ra nh u cn phi thc hin O(n) phộp toỏn. V gỏn nhón li cng
cn phi thc hin mt s lng phộp toỏn cng l O(n). Thut toỏn phi thc hin n
-1 bc lp, vp thi gian tớnh toỏn ca phộp toỏn l c O(n
2
).
nh lý c chng minh.
Khi ó tỡm c di ca ng i ngn nht d[v] thỡ ng i ny cú th

Bc lp nh 1 nh 2 nh 3 nh 4 nh 5 nh 6
Khi to 0,1 1,1*
,1 ,1 ,1 ,1
1 - - 6,2 3,2*
,1
8,2
2 - - 4,4* - 7,4 8,2
3 - - - - 7,4 5,3*
4 - - - - 6,6* -
5 - - - - - -
(1)

(7)

(1)

(3)

(4)

(2)

(5)

(2)

(2)

*
.1 .1
2 - - 24.2
*
- 31.4
.1
3 - - - - 31.4
*
41.3
4 - - - - - 41.3
*
5 - - - - - -

Bng kt qu tớnh toỏn theo thut toỏn Dijkstra
Chỳ ý:
1) Nu ch cn tỡm ng i ngn nht t s n mt nh t no ú thỡ cú th
kt thỳc thut toỏn khi cú nh t tr thnh nhón c nh.
2) Tng t nh mc 2, d dng mụ t li thut toỏn cho trng hp th
cho bi danh sỏch k. cú th gim bt khi lng tớnh toỏn trong vic xỏc nh
nh u mi bc lp. Khi ú cú th thu c thut toỏn vi phc tp tớnh toỏn l
O(m logn).

Chương 2PHÁT BIỂU BÀI TỐN LUỒNG TRÊN MẠNGNhiều bài tốn quy hoạch tuyến tính có thể quy về bài tốn làm cực tiểu phí
tổn vận chuyển hàng trong một mạng (gồm các nút và các cung đường) sao cho đảm
bảo được các nhu cầu ở một số nút khi đã biết nguồng cung cấp tại một số nút khác.
Các bài tốn như vậy được gọi là các bài tốn luồng trên mạng (network flow
problem) hoặc bài tốn chuyển vận (transshipment problem). Đây là lớp bài tốn
quan trọng nhất và hay gặp nhất trong quy hoạch tuyến tính. Lớp này bao gồm các
bài tốn quen thuộc trong thực tế như: bài tốn vận tải, các bài tốn mạng điện và
mạng giao thơng, các bài tốn quản lý và phân bổ vật tư, bài tốn bổ nhiệm, bài tốn
kế hoạch tài chính, bài tốn đường ngắn nhất, bài tốn luồng cực đại …
Bài tốn luồng cực đại trong mạng là một trong số những bài tố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 tố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. Trong chương này chúng
ta sẽ trình bày thuật tốn của Ford và Fulkerson để giải bài tốn đặt ra và nêu một số
ứng dụng của bài tốn.

I. PHÁT BIỂU BÀI TỐN

1.Mạng. Luồng trong mạng

Định nghĩa 1. Ta gọi mạng là đồ thị có hướng G = (V,E), trong đó có duy
nhất một đỉnh s khơng có cung đi vào gọi là điểm phát, duy nhất một đỉnh t khơng có
cung đi ra gọi là điểm thu và mỗi cung e = (v,w)
∈

Γ∈
−
Γ∈ vwvw
f
wvfvfvDiv

Trong đó
)(v
−
Γ
- tập các đỉnh của mạng mà từ đó có cung đến v,
)(v
+
Γ
- tập các đỉnh
của mạng mà từ v có cung đến nó:
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

20
{ } { }
.),(:)(,),(:)( EwvVwvEvwVwv ==
+

3.Giỏ tr ca lung f l s
.),(),()(
)()(



+

mng ra thnh hai tp X v X
*
=V \ X , trong ú s

X v t

X
*
. Kh nng thụng
qua ca lỏt ct (X,X
*
) l s



=
*
).,(),(
*
Xw
Xv
wvcXXc

Lỏt ct vi kh nng thụng qua nh nht c gi l lỏt ct hp nht.

B 1. giỏ tr ca mi lung f trong mng luụn nh hn bng kh nng
thụng qua lỏt ct (X,X
*
) bt k trong nú : val(f)


ta thu c
,)(),(),(
*
*





=+
Xw
Xv
Xw
Xv
fvalwvfwvf

THệ VIEN ẹIEN Tệ TRệẽC TUYEN

21
hay là
∑ ∑
∈
∈
∈
∈
−=
*
*
).,(),()(
Xw


suy ra val(f)
≤
c(X,X
*
). Bổ đề được chứng minh.
Từ bổ đề 1 suy ra

Hệ quả 1. Giá trị luồng cực đại trong mạng không vượt quá khả năng thông
qua của lát cắt hẹp nhất trong mạng.

Ford và Fulkerson đã chứng minh rằng giá trị luồng cực đại trong mạng đúng
bằng khả năng thông qua của lát cắt hẹp nhất. Để có thể phát biểu và chứng minh kết
quả này chúng ta sẽ cần thêm một số khái niệm.
Giả sử f là một luồng trong mạng G = (V,E). Từ mạng G = (V,E) ta xây dựng
đồ thị có trọng số trên cung G
f
=(V,E
f
) , với tập cung E
f
và trọng số trên các cung
được xác định theo quy tắc sau:

1
0
Nếu e = (v,w)
∈
E với f(v,w) = 0, thì (v,w)
∈

đồng thời cũng là cung của G được gọi là cung thuận, các
cung còn lại gọi là cung nghịch. Đồ thị G
f
được gọi là đồ thị tăng luồng.

Thí dụ: Các số viết cạnh các cung của G ở hình 1 theo thứ tự là khả năng
thông qua và luồng trên cung.
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN

22
∈
P là cung nghịch
f(u,v), nếu (u,v)
∉
P

Dễ dàng kiểm tra được rằng f‘ được xây dựng như trên là luồng trong mạng và
val(f ‘)= val(f) +
δ
. Ta sẽ gọi thủ tục biến đổi luồng vừa nêu là tăng luồng dọc theo
đường P.

Định nghĩa 4. Ta gọi đường tăng luồng f là mọi đường đi từ s đến t trên đồ thị
tăng luồng G(f).

Định lý 1. Các mệnh đề dưới đây là tương đương:
(i) f là luồng cực đại trong mạng:
(ii) Không tìm được đường tăng luồng f:
(iii) val(f) = c(X,X
*
) với mọi lát cắt (X,X
*
) nào đó.

Chứng minh.
(i) => (ii). Giả sử ngược lại, tìm được đường tăng luồng P. Khi đó ta có thể
tăng giá trị luồng bằng cách tăng luồng dọc theo đường P. Điều đó mâu thuẫn với
tính luồng cực đại của luồng f.
(ii) => (iii). Giả sử không tìm được đường tăng luồng. Ký hiệu X là tập tất cả
các đỉnh s trong đó đồ thị G

Xv
wvfwvfwvffval

c

s

s

1

1

2

t

3

3

b

1

d

2

2


4,1

2,2

THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN

23

Với v
∈
X, w
∈
X
*
. do (v, w)
∉
G
f
, nên f(v, w) = c(v, w). Vậy
∑ ∑
∈
∈
∈
∈
===
* *
*
).,(),(),()(
Xw

0
Tìm một đường đi tăng luồng P. Nếu khơng có thì thuật tốn kết thúc. Nếu
có, tiếp bước 3 dưới đây.
3
0
Nếu
δ
(P) = +
∞
thuật tốn kết thúc.

Trong đó δ(P) - Lượng luồng tăng thêm, hay nói khác là làm sự tăng luồng (flow
augmentation) dọc theo đường đi tăng luồng P một lượng thích hợp mà các ràng buộc
của bài tốn vẫn thoả.

Cách tìm đường đi tăng luồng. Ta sử dụng thuật tốn gán nhãn có nội dung
như sau. Một đường đi P thoả mãn về đường đi tăng luồng, nhưng chỉ đi từ s đến k
nào đó (chưa tới t, nói chung) sẽ được gọi là đường đi chưa bão hồ (unsaturated
path).

Ta nói đỉnh u là đã đánh dấu (u is labeled) nếu ta biết là có một đường đi chưa
bão hồ từ s tới u. Bây giờ ta sẽ xét tất cả các đỉnh v có nối trực tiếp đến đỉnh u (sẽ
gọi là ở cạnh đỉnh u) xem chúng có thể được gán nhãn hay khơng khi u đã gán nhãn.
Việc này được gọi là thăm (scanning) đỉnh u.
Nếu (u,v) có luồng trên cung F(u,v) < C(u,v) thì ta có thể nối thêm cung (u,v)
và đường đi chưa bão hồ P từ s đến u để được đường đi chưa bão hồ tới v. Vậy v có
thể gán nhãn.

Bước lặp tăng luồng ( Ford - Fulkerson): Tìm dường tăng P đối với luồng
hiện có. Tăng luồng dọc theo đường P.

mt trong ba trng thỏi: cha cú nhón, cú nhón cha xột, cú nhón ó xột. Nhón ca
mt nh v gm 2 phn v cú mt trong hai dng sau: [+p(v),

(v)] hoc [-p(v),

(v)
]. Phn th nht +p(v) (-p(v)) ch ra l cn tng (gim) lung theo cung (p(v),v) cung
(v,p(v)) cũn phn th hai

(v) ch ra lng ln nht cú th tng hoc gim theo cung
ny. u tiờn ch cú nh s c khi to nhón v nhón ca nú l cha xột, cũn tt c
cỏc nh cũn li u cha cú nhón . T s ta gỏn cho tt c cỏc nh k vi nú v nhón
ca nh s s tr thnh nhón ó xột. Tip theo, t mi nh v cú nhón cha xột ta li
gỏn nhón cho tt c cỏc nhón cha cú nhón k vi nú v nhón ca nh v tr thnh
nhón ó xột. Quỏ trỡnh s c lp li cho n khi hoc l nh t tr thnh cú nhón
hoc l nhón ca tt c cỏc nh cú nhón u l ó xột nhng nh t vn cha cú nhón.
Trong trng hp th nht ta tỡm c ng tng lung, cũn trong trng hp th
hai i vi lung ang xột khụng tn ti ng tng lung ( tc l lung ó l cc i
). Mi khi tỡm c ng tng lung, ta li tng lung theo ng tỡm c, sau ú
xoỏ tt c cỏc nhón v i vi lung mi thu c li s dng phộp gỏn nhón cỏc
nh tỡm ng tng lung. Thut toỏn s kt thỳc khi no i vi lung ang cú
trong mng khụng tỡm c ng tng lung.

Thut toỏn gỏn nhón (The labeling algorithm)

Gi V
T
l tp mi nh ó gỏn nhón nhng cha c thm. Ta cú thut toỏn
tỡm ng i tng lung.
Xut phỏt vi V


E, F(u,v) < C(u,v) v v cha gỏn nhón thỡ gỏn nhón nú v a
v vo tp V
T
.
3
0
Nu (v,u)

E, F(v,u) > 0 v v cha gỏn nhón thỡ gỏn nhón nú v a vo
tp V
T
.

Bõy gi ta xột kt qu ca thut toỏn gỏn nhón. Nú cú kt thỳc hu hn hay
khụng? Nhn xột rng mt nh c vo tp V
T
ch khi chuyn t cha gỏn nhón.
Do ú mt nh ch c vo V
T
nhiu nht l mt ln. M mi bc lp b mt nh
ra khi V
T
. Do ú, vỡ s nh ca mng l hu hn, thut toỏn phi kt thỳc hu hn.

Thớ d 1. p dng thut toỏn Ford-Fullkerson tỡm lung cc i bng cỏch
gỏn nhón cho nh ca mng G vi lung f c cho nh Hỡnh 1, hai s vit bờn cnh
mi cung l kh nng thụng qua v lung ca cỏc cung. Kt qu cỏc bc ca thut
toỏn mụ t bi cỏc th v bng di õy. Mng vi lung cc i thu c Hỡnh
2. Lỏt ct bộ nht l X = {s,c}, X


3,0

3,1

c
e
t
d
b
5,2

1,1

6,1

6,5

6,4

5,4

s
3,0

3,1

c(s+,3)
e(b+,1)
t(d+,1)


6,1

6,6

6,5

5,5

s
THệ VIEN ẹIEN Tệ TRệẽC TUYEN