158
PHẦN PHỤ LỤC

Phụ lục 2Bài toán luồng cực đạiCho 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*.)

( )
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

While V
T
<> {} do 160
BEGIN
u

V
T
;( * 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] };
V
T
:=V

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 ;

161
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

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:

162L_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
,V
1
,…)
- 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

{
thu tuc gan nhan tim duong tang luong:
L_p[v],L_nhan,L_e[v] la nhan cua dinh v;
L_v la danh sach cac dinh co nhan nhung chua xet;
}
VAR x,y:integer;
ok:boolean;
a1,b1,k1,l1:real;
t,t1,i:integer;
BEGIN
for i:=0 to L_G1.sodinh-1 do
L_p1[i]:=-1;
L_p1[0]:=0;
L_nhan[0]:=true;
L_e[0]:=vocung;
L_v:=[0] ; L_v1:=[0];
L_pathfound:=true;
While L_v<>[] do
Begin
ok:=true;
x:=0;
While (x<=L_G1.sodinh-1) and (ok=true) do
Begin
If x in L_v then ok:=false
Else
x:=x+1;
End;
L_v:=L_v-[x];
For y:=0 to L_G1.sodinh-1 do
If L_p1[y]=-1 then

End;
End;
End;
L_pathfound:=false;
end;
procedure L_Inc_flow(var L_G1:L_typedothi);
{
tang luong theo duong tang
}
var x,y,t,t1:integer;
tang,a,k:real;
s,s1,s2,s3,s4:string;
ok:boolean;
begin
x:=L_G1.sodinh-1;
y:=L_G1.sodinh-1;
tang:=L_e[L_G1.sodinh-1];
ok:=false;
while x<>0 do
begin
y:=L_p1[x];

165
L_giatri(L_G1,x,y,t,a,L_b); {a:=c[x,y],b:=f[x,y]}
L_giatri(L_G1,y,x,t1,k,L_l); {k:=c[y,x],l:=f[y,x]}
if L_nhan[x] then
L_G1.dscanh[t1].trongso.gia:=L_G1.dscanh[t1].trongso.gia+tang
else
begin
L_G1.dscanh[t].trongso.gia:=L_G1.dscanh[t].trongso.gia-tang;

begin
tam:=tam+1;
if tam>1 then

166
L_inc_flow(L_G1)
else
stop:=true;
end;
f:=0;
for y:= 0 to L_G1.sodinh-1 do
begin
L_giatri(L_G1,0,y,t1,a1,b1);
f:=f+b1;
end;
for y:=0 to L_G1.Socanh -1 do
if L_G1.DSCanh[y].DinhCuoi =L_G1.SoDinh -1 then
begin
break;
end;
tam:=0;
t2:=1;
while (t2<=L_G1.sodinh-2) do
begin
if t2 in L_v1 then
L_G1.dsdinh[t2].MucKichHoat :=3
else
L_G1.dsdinh[t2].MucKichHoat :=0;
end;
t2:=t2+1;

Chương trình còn có chức năng giúp cho người sử dụng tạo ra các thí dụ mới
và lưu lại các ví dụ vừa tạo.
Tên của các đỉnh đồ thị được mặt định là V
0
,V
1
,…. Tuy
nhiên chương trình có chức năng đổi tên cho đỉnh, người
sử dụng có thể đổi tên đỉnh bằng cách vào Edit


rename sau đó đánh tên mới vào (xem hình bên).
Việc đổi tên đỉnh và xoá đỉnh có thể thực hiện theo hai
cách, người sử dụng có thể chọn đỉnh rồi chọn Edit như
cách trên, hoặc click phải vào đỉnh cần xét rồi chọn các