PH N PH L CẦ Ụ Ụ
Ph l c 2ụ ụ
Bài toán lu ng c c đ iồ ự ạ
Cho m ng G=(V,E). Hãy tìm lu ng f* trong m ng v i giá tr lu ng val(f*) làạ ồ ạ ớ ị ồ
l n nh t. Lu ng nh v y ta s g i là lu ng c c đ i trong m ngớ ấ ồ ư ậ ẽ ọ ồ ự ạ ạ .
Bài toán nh v y có th xu t hi n trong r t nhi u ng d ng th c t . Ch ngư ậ ể ấ ệ ấ ề ứ ụ ự ế ẳ
h n khi c n xác đ nh c ng đ l n nh t c a dòng v n t i gi a hai nút c a m t b nạ ầ ị ườ ộ ớ ấ ủ ậ ả ữ ủ ộ ả
đ giao thông. Trong thí d này l i gi i c a bài toán lu ng c c đ i s ch cho ta cácồ ụ ờ ả ủ ồ ự ạ ẽ ỉ
đo n đ ng xe đông nh t và chúng t o thành ch h p t ng ng c a dòng giaoạ ườ ấ ạ ỗ ẹ ươ ứ ủ
thông xét theo hai nút đã ch n. M t thí d khác là n u xét đ th t ng ng v i m tọ ộ ụ ế ồ ị ươ ứ ớ ộ
h th ng đ ng ng d n d u, trong đó các ng t ng ng v i các cung, đi m phátệ ố ườ ố ẫ ầ ố ươ ứ ớ ể
có th coi là tàu ch d u, đi m thu là b ch a, còn các đi m n i gi a các ng là cácể ở ầ ể ể ứ ể ố ữ ố
nút c a đ th , kh năng thông qua c a các cung t ng ng v i ti t di n các ng.ủ ồ ị ả ủ ươ ứ ớ ế ệ ố
C n ph i tìm lu ng d u l n nh t có th b m d u t tàu ch d u vào b ch a.ầ ả ồ ầ ớ ấ ể ơ ầ ừ ở ầ ể ứ
Đ nh lý:ị 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 t lát c t (X,X*) nào đó.ớ ộ ắ
(Ta g i lát c t (X,X*) là m t cách phân ho ch t p đ nh V c a m ng ra thành hai t pọ ắ ộ ạ ậ ỉ ủ ạ ậ
X và X*=V\X, trong đó s
∈
X và t
∈
X*.)
Đ nh lý trên là c s đ xây d ng thu t toán l p sau đây đ tìm lu ng c c đ iị ơ ở ể ự ậ ặ ể ồ ự ạ
trong m ng: B t đ u t lu ng trên t t c các cung b ngạ ắ ầ ừ ồ ấ ả ằ 0 (ta s g iẽ ọ lu ng nh v yồ ư ậ
là lu ng không), và l p l i b c l p sau đây cho đ n khi thu đ c lu ng mà đ i v iồ ặ ạ ướ ặ ế ượ ồ ố ớ
nó không còn đ ng tăng:ườ
B c l p tăng lu ngướ ặ ồ (Ford – Fulkerson): Tìm đ ng tăng P đ i v i lu ng hi n có,ườ ố ớ ồ ệ
tăng lu ng d c theo đ ng P.ồ ọ ườ
Khi đã có lu ng c c đ i, lát c t h p nh t có th tìm theo th t c mô t trongồ ự ạ ắ ẹ ấ ể ủ ụ ả
vi c ch ng minh đ nh lý trên. Thu t toán Ford-Fulkerson đ c mô t trong th t cệ ứ ị ậ ượ ả ủ ụ
sau đây:
Procedure Luongcucdai;
Begin
Stop := false;
While not Stop do
If < Tìm đ ng tăng lu ng P> then ườ ồ
< Tăng lu ng d c theo P>ồ ọ
Else Stop := true;
End;
158
Đ tìm đ ng tăng lu ng trong G(f) có th s d ng thu t toán tìm ki m theoể ườ ồ ể ử ụ ậ ế
chi u r ng (hay tìm ki m theo chi u sâu), b t đ u t đ nh s trong đó không c n xâyề ộ ế ề ắ ầ ừ ỉ ầ
d ng t ng minh đ th G(f). Ford-Fulkerson đ ngh thu t toán gán nhãn chi ti t sauự ườ ồ ị ề ị ậ ế
đây đ gi i bài toán lu ng c c đ i trong m ng. Thu t toán b t đ u t lu ng ch pể ả ồ ự ạ ạ ậ ắ ầ ừ ồ ấ
nh n đ c nào đó trong m ng (có th b t đ u t lu ng không) , sau đó ta s tăngậ ượ ạ ể ắ ầ ừ ồ ẽ
lu ng b ng cách tìm các đ ng tăng lu ng. Đ tìm đ ng tăng lu ng ta s áp d ngồ ằ ườ ồ ể ườ ồ ẽ ụ
ph ng pháp gán nhãn cho các đ nh. M i đ nh trong quá trình th c hi n thu t toán sươ ỉ ỗ ỉ ự ệ ậ ẽ
m t trong ba tr ng thái: ch a có nhãn, có nhãn ch a xét, có nhãn đã xét. Nhãn c aở ộ ạ ư ư ủ
m t đ nh v g m hai ph n và có m t trong hai d ng sau : [ộ ỉ ồ ầ ộ ạ
( )p v+
,
( )v
ε
] ho c [ặ
( ), ( )p v v
ε
−
]. Ph n th nh t +p(v) (-p(v)) ch ra là c n tăng gi m lu ng theo cungầ ứ ấ ỉ ầ ả ồ
(p(v),v)( cung (v,p(v)) còn ph n th hai ầ ứ
( )v
ε
ch ra l ng l n nh t có th tăng ho cỉ ượ ớ ấ ể ặ
gi m lu ng theo cung này. Đ u tiên ch có đ nh s đ c kh i t o nhãn và nhãn c a nóả ồ ầ ỉ ỉ ượ ở ạ ủ
là ch a xét, còn t t c các đ nh còn l i đ u ch a có nhãn. T s ta gán nhãn cho t t cư ấ ả ỉ ạ ề ư ừ ấ ả
các đ nh k v i nó và nhãn c a đ nh s s tr thành đã xét. Ti p theo, t m t đ nh v cóỉ ề ớ ủ ỉ ẽ ở ế ừ ộ ỉ
nhãn ch a xét ta l i gán nhãn cho t t c các đ nh ch a có nhãn k v i nó và nhãn c aư ạ ấ ả ỉ ư ề ớ ủ
đ nh v tr thành đã xét. Quá trình s đ c l p l i cho đ n khi ho c là đ nh t tr thànhỉ ở ẽ ượ ặ ạ ế ặ ỉ ở
có nhãn ho c là nhãn c a t t c các đ nh có nhãn đ u là đã xét nh ng đ nh t v nặ ủ ấ ả ỉ ầ ư ỉ ẫ
không có nhãn. Trong tr ng h p th nh t ta tìm đ c đ ng tăng lu ng, còn trongườ ợ ứ ấ ượ ườ ồ
tr ng h p th hai đ i v i lu ng đang xét không t n t i đ ng tăng lu ng (t c làườ ợ ứ ố ớ ồ ồ ạ ườ ồ ứ
lu ng đã c c đ i). M i khi tìm đ c đ ng tăng lu ng, ta l i tăng lu ng theo đ ngồ ự ạ ỗ ượ ườ ồ ạ ồ ườ
tìm đ c, sau đó xoá t t c các nhãn và đ i v i lu ng m i thu đ c l i s d ng phépượ ấ ả ổ ớ ồ ớ ượ ạ ử ụ
gán nhãn các đ nh đ tìm đ ng tăng lu ng. Thu t toán s k t thúc khi nào đ i v iỉ ể ườ ồ ậ ẽ ế ố ớ
lu ng đang có trong m ng không tìm đ c đ ng tăng lu ng.ồ ạ ượ ườ ồ
Hai th t c tìm đ ng tăng lu ng có th mô t nh sau : ủ ụ ườ ồ ể ả ư
Procedure Find-path;
{
Th t c gán nhãn đ ng tăng lu ngủ ụ ườ ồ
p[v],
∈
ε
[v] là nhãn c a đ nh v;ủ ỉ
VT là danh sách các đ nh có nhãn ch a xét ;ỉ ư
c[u,v] là kh năng thông qua c a cung (u,v),u,v ả ủ
∈
V;
f[u,v] là lu ng trên cung (u,v), (u,v ồ
∈
V);
}
BEGIN
p[s] := s ;
ε
[s] :=
+∞
;
VT := {s};
Pathfound := true;
While VT<> {} do
BEGIN
159
u
⇐
VT ;( * l y u t Vấ ừ T *)
For v
∈
V do
If (v ch a có nhãn) thenư
Begin
If (c[u,v] >0) and (f[u,v] < c[u,v] ) then
Begin
P[v] := u ;
ε
[v] := min {
ε
[u],c[u,v]-f[u,v] };
VT:=VT
∪
{v};(* n p v vào danh sách các đ nh có nhãn *) ạ ỉ
If v = t then exit;
End
Else
If (c[v,u] > 0) and (f[v,u] < 0) then
Begin
P[v] := u ;
ε
[v] := min {
ε
[u] , f[u,v] };
VT:=VT
∪
{v};(* n p v vào danh sách các đ nh có nhãn *) ạ ỉ
If v = t then exit;
End;
End;
End;
160
PathFound :=false;
End;
Procedure Inc_flow ;
{ thu t toán tăng lu ng theo đ ng tăng }ậ ồ ườ
Begin
v := t ;
u := t ;
tang := [t];
while u <> s do
begin
v := p[u];
if v > 0 then f[v,u] := f[v,u] + tang
else
begin
v := -v;
f[u,v] :=f[u,v] –tang;
end;
u := v ;
end;
Procedure FF;
{ th t c th hi n thu t toán Ford_fulkerson }ủ ụ ể ệ ậ
Begin
(* kh i t o b t đ u t lu ng v i giá tr 0 *)ở ạ ắ ầ ừ ồ ớ ị
For u
∈
V do
For v
∈
V do f[u,v] :=0;
Stop := false;
While not Stop do
begin
find_path;
If pathfound then
Inc_flow
Else
Stop:=true;
End;
< Lu ng c c đ i trong m ng là f[u,v], u,v ồ ự ạ ạ
∈
V >
< Lát c t h p nh t là (Vắ ẹ ấ T , V\ VT) >
End;
161
Ch ng trình sau là ch ng trình ph c v cho vi c h c t p và gi ng d y vươ ươ ụ ụ ệ ọ ậ ả ạ ề
bài toán tìm lu ng c c đ i trong m ng. Ch ng trình sau đ c xây d ng b ng côngồ ự ạ ạ ươ ượ ự ằ
c l p trình Delphi.ụ ậ
Các ch c năng c a ch ng trình:ứ ủ ươ Ta xây d ng ch ng trình bao g m nh ng ch cự ươ ồ ữ ứ
năng sau:
* Tóm t t thu t toán Ford – Fulkeson.ắ ậ
* Hi n th các b c th c hi n ng v i t ng ví d c th . ể ị ướ ự ệ ứ ớ ừ ụ ụ ể
Tóm t t thu t toán Ford – Fulkerson : ắ ậ
Ch c năng này có m c đích giúp cho ng i s d ng n m v ng đ c thu tứ ụ ườ ử ụ ắ ữ ượ ậ
toán tr c khi đi vào các thí d c th . ướ ụ ụ ể
Hi n th các b c th c hi n c a bài toán:ể ị ướ ự ệ ủ
Do ch ng trìnhươ nh m m c đích ph c v cho vi c d y và h c môn Toán r iằ ụ ụ ụ ệ ạ ọ ờ
r c nên ch c năng vi c hi n th chi ti t các b c gi i bài toán ng v i t ng thí d cạ ứ ệ ể ị ế ướ ả ứ ớ ư ụ ụ
th giúp cho ng i s d ng hi u rõ h n v thu t toán.ể ườ ử ụ ể ơ ề ậ
C u trúc d li u và cài đ t thu t toán:ấ ữ ệ ặ ậ
C u trúc d li u:ấ ữ ệ
Đ th đ c l u gi d i d ng t p đ nh và t p c nh. M i đ nh đ c l u theoồ ị ượ ư ữ ướ ạ ậ ỉ ậ ạ ỗ ỉ ượ ư
c u trúc c a m t Record nh sau:ấ ủ ộ ư
L_TypeDinh = record
Ten:String;
ToaDo:L_TypeToaDo;
MucKichHoat:Byte;
end;
Trong đó:
- Bi n Ten có ki u String , l u gi tên đ nh (m t đ nh là Vế ể ư ữ ỉ ặ ị 0,V1,…)
- Bi n ToaDo có ki u L_TypeToaDo, l u gi to đ x, y c a m i đ nh cóế ể ư ữ ạ ộ ủ ỗ ỉ
c u trúc c a m t Record nh sau :ấ ủ ộ ư
L_TypeToaDo = record
x,y:integer;
end;
Bi n Muckichhoat có ki u Byte l u gi m c đ kích ho t c a đ nh (m i đ nhế ể ư ữ ứ ộ ạ ủ ỉ ỗ ỉ
có 4 m c kích ho t khác nhau), bi n này dùng đ xác đ nh đ nh đ u, đ nh cu i, đ nhứ ạ ế ể ị ỉ ầ ỉ ố ỉ
h p….ẹ
162