Luồng cực đại trong mạng và một số bài toán ứng dụng
Nguyễn Văn Trường
Bài toán luồng cực đại trong mạng là một trong những bài toá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 toá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à toán học Mỹ là Ford và Fulkerson. Trong nội dung bài viết này chúng tôi
muốn trình bày thuật toán của hai ông và cài đặt nó cũng như đưa ra một số bài toán ứng
dụng của thuật toán.
1. Một số khái niệm
Định nghĩa 1. Mạng là một đồ 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 và có 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) thuộc E được gán với một số không âm c(e) = c(v,w)
gọi là khả năng thông qua của cung e (nếu không có cung (v,w) thì khả năng thông qua
c(v,w) được gán bằng 0).
Định nghĩa 2. Một luồng f trong mạng G = (V,E) là ánh xạ f : E → R+ gán cho mỗi cung
e = (v,w) thuộc E một số thực không âm f(e) = f(v,w), gọi là luồng trên cung e, thoả mãn
các điều kiện sau:
1) Luồng trên mỗi cung e thuộc E không vượt quá khả năng thông qua của nó:
0 ≤ f(e) ≤ c(e).
2) Điều kiện cân bằng luồng trên mỗi đỉnh của mạng là tổng luồng trên mỗi cung đi vào
đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v, nếu v ≠ s và v ≠ t thì:
Divf(v) = Σf(w,v) - Σ f(v,w) = 0
w thuộc G - (v) w thuộc G + (v)
trong đó G - (v) là tập các đỉnh của mạng mà từ đó có cung đến v, và G + (v) là tập các
đỉnh của mạng mà từ v có cung đến nó.
G - (v) = { w thuộc V : (w,v) thuộc E}; G + (v) = { w thuộc V : (v,w) thuộc E};
3) Giá trị của luồng f là số:
val( f ) = Σ f(s,w) = Σ f(w,t)
w thuộc G + (v) w thuộc G - (v)
Bài toán luồng cực đại trong mạng:
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.

trên mạng G theo qu y tắc sau: f′(u,v) nhận một trong các giá trị sau:
1) f(u,v) + d nếu (u,v) thuộc P là cung thuận.
2) f(u,v) - d nếu (u,v) thuộc P là cung nghịch.
3) f(u,v) nếu (u,v) không thuộc P.
Dễ dàng kiểm tra được rằng f′ xây dựng như trên là một luồng trên mạng và val(f′) =
val(f) + d. Thủ tục biến đổi vừa nêu gọi là tăng luồng dọc theo đường P.
Địng nghĩa 4. Đườ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 đề sau là tương đương:
1) f là luồng cực đại trong mạng
2) không tìm được đường tăng luồng f
3) val(f′) = c(X,X*) với một lát cắt (X,X*) nào đó.
2.Thuật toán tìm luồng cực đại trong mạng
Định lý 1 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 với tất cả các cung bằng 0 (luồng đó được gọi là luồng không), và thực
hiện hai thao tác: a) Tìm đường tăng P đối với luồng hiện có; b) Tăng luồng dọc theo
đường P, lặp đi lặp lại cho đến khi thu được luồng mà đối với nó không còn đường tăng
(bước lặp trên được gọi là bước lặp tăng luồng Ford-Fulkerson).
Sơ đồ thuật toán Ford-Fulkerson được mô tả trong thủ tục sau đây:
Procedure Max_Flow;
(*Thuật toán Ford-Fulkerson *)
Begin
(* khởi tạo bắt đầu từ luồng với giá trị 0 *)
for u thuộc V do
for v thuộc V do f(u,v):=0;
Stop:= false;
While not Stop do
If {tìm được đường tăng luông P}then
{tăng luồng dọc theo P}
else stop:=true;
End;

VT :={s};
PathFound:=true;
While VT ≠ Φ do
Begin
u ← VT ;(*lấy u từ VT*)
for v thuộc VVT do
Begin
if (c[u,v] > 0) and (f[u,v] < c[u,v]) then
Begin
p[v]:=u;
e [v]:=min{ e [u],c[u,v]-f[u,v]};
VT:=VT hợp {v};(*nạp v vào danh sách đỉnh có nhãn*)
If v=t then exit;
End;
If (c[u,v] > 0) and (f[u,v] > 0) then
Begin
p[v]:= - u;(* đánh dấu cung nghịch *)
e [v]:=min{ e [u],f[v,u]};
VT:=VT hợp {v};(*nạp v vào danh sách đỉnh có nhãn*)
If v=t then exit;
End;
End;
PathFound:=false;
End;
Procedure Inc_Flow;
(*tăng luồng theo đường tăng *)
Begin
v:=p[t];u:=t;tang:= e [t];
While u ≠ s do
Begin

Định lý 2. (Định lý về luồng cực đại trong mạng và lát cắt hẹp nhất). Luồng cực đại trong
mạng bằng khả năng thông qua của lát cắt hẹp nhất.
Định lý 3. (Định lý về tính nguyên). Nếu tất cả các khả năng thông qua là các số nguyên
thì luôn tìm được luồng cực đại với luồng trên các cung là các số nguyên.
Tuy nhiên, nếu khả năng thông qua là các số rất lớn thì giá trị của luồng cực đại cũng có
thể rất lớn và thuật toán ở trên đòi hỏi phải thực hiện nhiều bước tăng luồng. Gần đây
người ta đã đưa ra các thuật toán với độ phức tạp tính toán tốt hơn, tuy nhiên thuật toán
Ford-Fulkerson cũng được đánh giá là một trong những thuật toán kinh điển để giải các
bài toán ứng dụng về luồng cực đại trong mạng.
Tiếp theo là phần cài đặt cụ thể của thuật toán bằng ngôn ngữ Pascal. Chương trình dưới
đây có sử dụng dữ liệu vào được cho trong file Luong.inp có dạng như sau:
Dòng đầu tiên gồm ba số nguyên là số đỉnh của mạng n, đỉnh phát s, đỉnh thu t.
Tiếp theo là một ma trận kích thước n x n thể hiện ma trận trọng số của đồ thị có hướng
minh hoạ cho mạng cần tìm luồng cực đại.
Dữ liệu ra được cho trong file Luong.out có dạng như sau:
Phần đầu tiên là một ma trận kích thước n x n thể hiện luồng cực đại tìm được (phần tử
(i,j) của ma trận là luồng trên cung (i,j)).
Dòng tiếp theo là một số nguyên cho biết giá trị luồng cực đại trong mạng.
Chẳng hạn với mạng được cho trong hình vẽ ở trên thì các file tương ứng là:
luong.inp
6 1 6
0 3 4 0 0 0
0 0 0 3 2 0
0 1 0 0 3 0
0 0 0 0 0 4
0 0 0 0 0 3
0 0 0 0 0 0
luong.out
0 3 3 0 0 0
0 0 0 3 0 0

while l>0 do
begin
u:=vt[l];l:=l-1;
for v:=1 to n do
if not ( v in vt1)then
begin
if (c[u,v]>0)and(f[u,v]
begin
p[v]:=u;e[v]:=e[u];
if e[v]>c[u,v]-f[u,v] then
e[v]:=c[u,v]-f[u,v];
l:=l+1;vt[l]:=v;vt1:=vt1+[v];
if v=t then exit;
end;
if (c[v,u]>0)and(f[v,u]>0)then
begin
p[v]:=-u;e[v]:=e[u];
if e[u]>f[v,u]then e[v]:=f[v,u];
l:=l+1;vt[l]:=v;vt1:=vt1+[v];
if v=t then exit;
end;
end;
end;
Path_Found:=false;
end;
procedure Inc_Flow;
begin
v:=p[t];u:=t;Tang:=e[t];
while u<>s do
begin

if Path_Found then Inc_Flow
else stop:=true;
end;
end;
begin
init;
Max_Flow;
result;
end.
3. Một số bài toán ứng dụng
Bài 1. (mạng với nhiều điểm phát và nhiều điểm thu)
Cho n kho cần chuyển hàng s1,s2, sn và m kho nhận hàng t1,t2, ,tm. Hãy tìm một
phương án chuyển hàng sao cho lượng hàng được chuyển là lớn nhất, cho biết trước số
lượng hàng cần chuyển cũng như khả năng chứa hàng ở mỗi kho và số hàng có thể
chuyển từ si đến tj là c(i,j).
Bài toán này có thể đưa về bài toán mạng với nhiều điểm phát và điểm thu. Ta coi các
kho si là các điểm phát, các kho nhận tj là các điểm thu. Đồng thời đưa vào một điểm
phát giả s nối với tất cả các điểm phát và một điểm thu giả t được nối với các điểm thu.
Giá trị c(s,si) bằng số hàng cần chuyển ở kho si , và c(tj,t) bằng khả năng chứa hàng trong
kho tj .
Bài 2. (bài toán với khả năng thông qua ở các cung và các đỉnh)
Hãy tìm một phương án vận chuyển dầu từ một bể chứa s tới bể nhận t thông qua hệ
thống đường ống dẫn dầu, sao cho lượng dầu chuyển được là nhiều nhất. Cho biết trước
lượng dầu lớn nhất có thể bơm qua mỗi đường ống và qua mỗi điểm nối giữa các ống.
Phương án giải bài toán như sau: xây dựng đồ thị G = (V,E), với V là tập các đỉnh của đồ
thị gồm s, t và tập các điểm nối, còn E là tập các cung của đồ thị gồm các đường ống dẫn
dầu. Trong G, với mỗi đỉnh v thuộc V thì tổng luồng đi vào đỉnh v không được vượt quá
khả năng thông qua d(v) của nó:
Σf(w,v) ≤ d(v)
w thuộc V

bằng N mà không tồn tại luồng cực đại sao cho giá trị của luồng tại các cung chứa đỉnh
phát đều bằng 2.
Bài 4.
Có n sinh viên cần đi thực tập ở m trường. Mỗi sinh viên i có quyền đăng ký nguyện
vọng thực tập vào các trường với số lượng trường đăng ký là c(i): 0 ≤ c(i) ≤ m. Hãy tìm
một phương án bố trí các sinh viên vào các trường sao cho thoả mãn được nhiều nguyện
vọng nhất và nếu có thể thì số lượng trường có sinh viên được bố trí vào thực tập càng ít
càng tốt. Dữ liệu vào cho trong tệp THUCTAP.INP có cấu trúc như sau: dòng đầu gồm
hai số nguyên n, m; tiếp theo là một ma trận gồm n hàng, m cột: ô (i,j) bằng 1 nếu sinh
viên i có nguyện vọng đăng ký thực tập ở trường j và bằng 0 trong trường hợp ngược lại.
Dữ liệu ra ghi vào tệp THUCTAP.OUT gồm một ma trận gồm n hàng, m cột: ô (i,j) bằng
1 nếu sinh viên i được bố trí thực tập ở trường j và bằng 0 trong trường hợp ngược lại.
Bài toán này khá dễ giải nếu ta phát hiện ra rằng: để thỏa mãn yêu cầu thứ hai của đầu bài
thì chỉ cần bỏ đi một số lượng các trường nhiều nhất trong tập m trường đã cho sao cho
số nguyện vọng được thoả mãn vẫn giữ nguyên như khi chưa bỏ đi trường nào.
Các bài toán có thể giải được thông qua thuật toán đã trình bày rất phong phú và đa dạng.
Nó còn được sử dụng nhiều trong các bài toán tổ hợp như bài toán đám cưới vùng quê,
các bài tối ưu rời rạc (bài toán lập lịch, phân nhóm) Trong các bài toán dạng này, có một
số bài có thể đưa về bài toán tìm cặp ghép đầy đủ tối ưu ( bạn đọc có thể tham khảo thêm
trong bài Cặp ghép của tác giả Lê Văn Chương, trong số báo 11/2001 ).
Tài liệu tham khảo:
[1] Nguyễn Đức Nghĩa, Nguyễn Tô Thành-Toán học rời rạc. Nhà xuất bản giáo dục-
1997.
[2] Robert Sedgewick.' Algorithm ' Princeton University ( USA ) Ađison - Wesley
Publishing Co.
[3] Một số sách báo và tài liệu tham khảo khác.
Nguyễn văn Trường
Một số ứng dụng của bài toán luồng cực đại
Lê Thanh Hà
Ta xét bài toán sau:

assign(f,fi);
reset(f);
readln(f,n);
fillchar(m,sizeof(m),0);
while not eof(f) do
begin
readln(f,i,j);
m[i,j]:=1;
end;
close(f);
end;
procedure tim;
label done;
var i,j,k:byte;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
for i:=1 to n do
if a[i]=0 then
begin
s:=chr(i);
fillchar(c,sizeof(c),0);
repeat
k:=ord(s[length(s)]);
delete(s,length(s),1);
for j:=1 to n do
if (c[j]=0) and (m[k,j]=1) then
begin
c[j]:=1;
dt[j]:=k;

người thợ với mỗi công việc để không những thoả mãn điều kiện như cũ mà tổng số mức
độ tình cảm hay năng xuất phải là lớn nhất. Để giải quyết vấn đề trên ta tiếp tục cải tiến
thuật toán trên: Trước tiên ta xây dựng một đồ thị hai phía mới với các đỉnh vẫn như cũ.
Ta lần lượt thêm vào đồ thị từng cạnh của đồ thị cũ theo thứ tự từ cao xuống thấp của giá
trị trọng số. Sau mỗi lần thêm, ta lại tìm một cặp ghép cực đại trong đồ thị đó cho tới khi
tìm được giá trị cực đại đó bằng m thì dừng. Bạn tham khảo chương trình sau:
uses crt;
const fi = 'input.txt';
fo = 'output.txt';
var m,dx:array[1 150,1 150] of byte;
a,b,c,dtr:array[1 150] of byte;
n:byte;
dem:word;
f:text;
time:longint absolute 0:$46c;
tich:longint;
procedure input;
var i,j:Byte;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do
begin
for j:=1 to n do read(f,m[i,j]);
readln(f);
end;
close(f);
end;
procedure work;

for j:=1 to n do
if (dx[k,j]=1) and (c[j]=0) then
begin
dtr[j]:=k;
c[j]:=1;
if b[j]<>0 then s:=s+chr(b[j])
else
begin
repeat
b[j]:=dtr[j];
k:=a[b[j]];
a[b[j]]:=j;
j:=k;
until j = 0;
goto 1;
end;
end;
until s = '';
1: end;
ok := false;
for i:=1 to n do if a[i]=0 then
begin
ok := true;
writeln(time-tich);
break;
end;
until ok =false;
assign(f,fo);
rewrite(f);
dem:=0;

• 5
( 0 Votes )
Written by Administrator
Thursday, 31 December 2009 04:38
Ứng dụng luồng cực đại trong bài toán tối ưu rời rạc
Đức Trọng
I. Bài toán
Xétbài toán:
Trongđó a
ij
thuộc {0,1}
p
i
nguyên dương
i = 1,2,…,m;
j = 1,2,…,n
Bài toán trên là mô hình toán học của nhiều bàitoán tối ưu tổ hợp trong thực tế. Ví dụ:
II. Vídụ
1. Bài toán phânnhóm sinh hoạt:
Cóm sinh viên và n nhóm sinh hoạt chuyên đề.Với mỗi sinh viên i biết:
- a
ij
=1, nếu sinh viêni có nguyện vọng tham gia vào nhóm j
- a
ij
=0, nếu ngượclại
- p
i
là số lượngnhóm chuyên đề mà sinh viên i phải tham dự
i=1,2,…,m; j=1,2,…,n

ij
= 0, nếu ngược lại
i=1, 2, ,m ; j=1, 2, ,n, khi đó dễ thấy mô hình toán học cho bài toánđặt ra chính là bài
toán (1)-(2), trong đó pi =1, i=1, 2, ,m.
III. Cơ sở thuật toán
Bổ đề 1:
Bài toán (1)-(2) có nghiệm tối ưu khi và chỉ khi:
Chứng minh:
Điều kiện cần là hiển nhiên vì sự tồn tại phương án của bàitoán suy ra bất đẳng thức trong
(3) được thực hiện ít nhất dưới dạng dấu đẳngthức.
Điều kiện đủ: Chỉ cần chỉ ra rằng nếu có (3) thì luôn có phươngán.
Giả sử (3) đúng, gọi:
Do(3) là điều kiện để (1)-(2) có nghiệm nên trong phần tiếp theo ta luôngiả thiết rằng điều
kiệnđược thực hiên.
Bâygiờ ta chỉ ra rằng bài toán (1)-(2) có thể chuyển về giải một số hữuhạn bài toán luồng
cực đại trong mạng. Trước hết với mỗi k nguyêndương ta xây dựng mạng G
(k)
= (V,E) với
e thuộc E:khả năng thông qua c(e)
c(s,u
i
) = p
i

c(u
i
,v
j
) = a
ij

j
) thuộc {0,1}với i=1,2,…,m;j=1,2,…,n
Vậy x* là phương án của bài toán (1)-(2) (đpcm).
Bổđề 3:
Giả sử x*là phương án tối ưu và k* là giá trị tối ưu của bài toán(1)-(2) thì luồng cực đại
trong G
(k*)
có giá trị Δ
Chứng minh: Do giá trị của luồng cực đại trong mạng G
(k*)
không vượt qu Δ, nên để chứng
minh bổ đề ta chỉ cần chỉ ra luồngvới giá trị Δ trong mạng G
(k*)
.
Ta xây dựng luồng Φ như sau:
Dễ dàng chứng minh Φ là luồng trong mạng G
(m)
có giá trị Δ.(đpcm)
Bổđề 4:
Nếu k=m thìluồng cực đại trong mạng G
(m)
có giá trị Δ.
Chứng minh:
Lập luận tương tự bổ đề 3 ta chỉ cần chỉ ra luồng với giátrị Δ trong mạng G
(m)
.
Thậtvậy, giả sử x* là nghiệm bài toán (1)-(2) được xây dựngtheo công thức như bổ đề 1,
xây dựng Φ theo bổ đề 3 ta có luồng giá trị Δ.(đpcm)
IV. Thuậttoán:
Từ nhận xét 2 và 3 suy ra việc giải bài toán (1)-(2) là tìm k*nguyên dương nhỏ nhất sao

Vari,j:Integer;
Begin
Assign(fi,InputFile);
Reset(fi);
Readln(fi,m,n);
Delta:=0;
For i:=1 to m do begin
read(fi,p[i]);
Delta:=Delta+p[i];
End;
For i:=1 to m do
For j:=1 to n do read(fi,a[i,j]);
Close(fi);
s:=m+1;t:=n+1;
For i:=1 to m do a[s,i]:=p[i];
End;
FunctionFindPath:Boolean;
Var
Queue:Array[1 100]of Integer;
i,j,First,Last,v:Integer;
Begin
Fillchar(TraceX,Sizeof(TraceX),0);
Fillchar(TraceY,Sizeof(TraceY),0);
First:=1;Last:=0;
For i:=1 to m do
If x[s,i]
inc(last);
Queue[last]:=i;
traceX[i]:=-1;
end;

i:=TraceY[j];
IncValue:=Min(IncValue,a[i,j]-x[i,j]);
j:=TraceX[i];
If j>0 then IncValue:=Min(IncValue,x[i,j]);
End;
Start:=i;
IncValue:=Min(IncValue,a[s,start]-x[s,start]);
j:=Finish;
While j>0 do begin
i:=TraceY[j];
x[i,j]:=x[i,j]+IncValue;
j:=TraceX[i];
If j>0 then x[i,j]:=x[i,j]-IncValue;
End;
x[s,start]:=x[s,start]+IncValue;
x[finish,t]:=x[finish,t]+IncValue;
End;
FunctionMaxFlow(k:Integer):Integer;
Vari,mf:Integer;
Begin
Fillchar(x,Sizeof(x),0);
For i:=1 to n do a[i,t]:=k;
Repeat
If not FindPath then break;
IncFlow;
Until False;
mf:=0;
For i:=1 to m do mf:=mf+x[s,i];
MaxFlow:=mf;
End;

Bài toán (1)-(2) giải được nhờ thuật toán đa thức có độ phứctạp tính toán là
O(log
2
m.OFN) trong đó OFN là độ phức tạptính toán tìm luồng cực đại.