INFOMAN брой 4
{N; G[1..N,1..N]; Source Dest
12
1 2 4
1 3 8
1 6 7
2 3 4
2 4 5
3 4 1
3 5 7
4 7 5
5 7 7
6 5 2
6 7 4
6 10 2
6 12 5
7 8 9
7 9 6
7 10 12
8 9 2
8 11 7
9 11 8
10 12 8
10 11 3
12 11 1
0 0 0
1 11
МАКСИМАЛЕН ПОТОК В ГРАФ
-----------------------
Схемата на водоснабдителна мрежа представлява насочен граф. Всяко ребро
представлява тръба с пропусклива способност теглото на реброто. Всеки връх
на графа е помпена станция, която помпи водата, която идва от влизащите в
нея ребра, към излизащите от нея ребра. По всяка тръба (u,v) за 1 секунда
протичат най-малко 0 и най-много G[u,v] литра вода.Помпените станции не са
резервоари, което означава, че те не могат да трупат вода в себе си. Това
ще рече, че количеството вода, което влиза по входящите тръби в една помпе-
на станция за единица време е задължително равно на количеството вода, кое-
то излиза по изходящите тръби от станцията за същото време. Посоката, в ко-
ято тече водата по една тръба е предварително зададена и не може да се про-
меня. Да се напише програма, която намира максималният поток от зададен на-
чален връх (източник) до зададен краен връх (консуматор). Максималният по-
ток е максималното количество вода, което може да протече от източника до
консуматора по зададената система от тръби и помпени станции за 1 секунда
ако се приеме, че източникът е неизчерпаем и от него за 1 секунда може да
изтече произволно количество вода.
РЕШЕНИЕ: Нека с някакъв алгоритъм да сме намерили път (последователност
от тръби) от източника до консуматора. Нека най-тясната тръба от този път
да пропуска обем v за 1 секунда. Тогава можем да увеличим потока във всяка
от тръбите с v ( първоначално потокът Flow[u,v] е 0 за всяка тръба (u,v) ).
Нека в тръбите за момента има някакъв поток.Ако намерим такъв път от източ-
ника до консуматора,че всяка тръба от този път да има вместимост по-голяма
от потока, който тече в момента в нея, можем отново да направим подобрение.
Ако G[u,v] е пропускливата способност на тръбата (u,v) или 0 ако няма така-
ва тръба и Flow[u,v] е текущия поток през тръбата (u,v) от станция u към v,
можем към стойността на потока на всяка тръба от намерения път да добавим
най-малката стойност на разликата G[a,b]-Flow[a,b] от всички тръби(a,b) от
намерения път.Така общият поток от източника до консуматора ще стане по-го-
лям и същевременно по всяка от тръбите ще тече най-много толкова вода, кол-
кото може да пренася. Последователното прилагане на последната оптимизация
докато може, не гарантира обаче намирането на максималния поток. Ето защо
можем да прилагаме още една оптимизация, която е същата като горната, но с
тези разлики: Когато от някой връх не можем да продължим търсенето на път,
можем да продължим по тръба с отрицателен поток.Отрицателен поток по тръба-
та (v,u) имаме когато имаме поток по тръбата (u,v). Този отрицателен поток
има стойност равна на стойността на потока (u,v) - Flow[u,v]. Когато наме-
рим път от източника до консуматора, той ще се състои от ребра с положите-
лен поток,за които стойността на потока е по-малка от пропускливата им спо-
собност и от ребра с отрицателен поток, за които потокът не е 0. Ако имаме
намерен такъв път,можем да повишим стойността на максималния за момента по-
ток в графа като: Всички положителни потоци в намерените тръби се увелича-
ват,а всички отрицателни потоци се намаляват с по-малката от следните стой-
ности:
- най-малкият положителен поток от всички положителни потоци в пътя
- най-малкият отрицателен поток от всички отрицателни потоци в пътя
Може да се докаже, че ако в графа няма път като описания по-горе,то намере-
ният за момента поток в тръбите е максимален и стойността му е сбора от по-
тоците в тръбите излизащи от източника, която е равна и на сбора от потоци-
те които се вливат в консуматора. Ето защо ако прилагаме оптимизацията до-
като може, в крайна сметка ще намерим максималният поток. Алгоритъма за на-
миране на път от източника до консуматора, състоящ се от положителни пото-
ци, които могат да се увеличат и от отрицателни потоци, които могат да се
намалят, е с линейна сложност, защото той е същият като алгоритъма за нами-
ране на път в ориентиран граф. Може да се използва търсене в ширина или в
дълбочина, като всеки връх се посещава най-много вежнъж,откъдето произтича
и линейната сложност. Алгоритъмът за намиране на максимален поток,на който
се базира описаният по-горе е известен като алгоритъм на Ford-Fulkerson и
има сложност в най-лошия случай по-голяма от N*N*N.
Да разгледаме още една разновидност на задачата за намиране на максимален
поток в граф. Нека не освен ребрата да имат пропусклива способност,върхове-
те също да имат такава - всеки връх да има съпоставено едно число,което да
е максималния поток, който може да преминава през него за единица време.Та-
зи задача се свежда към предходната по следния начин: Към дадения граф за
всеки връх v се въвежда един допълнителен връх v'. Ребрата, които влизат в
v се пренасочват да влизат в v' и се добавя ребро (v',v) с пропусклива спо-
собност пропускливата способност на върха v.
И още една задача, свързана с максимален поток в граф. Да се напише алго-
ритъм за намиране на всички ребра, такива, че ако пропускливата способност
на някое от тях се увеличи,ще се увеличи и стойността на максималния поток
в дадения граф. Ами решението е такова: Намираме върхове, които са достижи-
ми от Source с помощтта на частичен увеличаващ път.Нека тези върхове бъдат
множеството A. И нека B да е множеството на всички върхове, от които е дос-
тижим крайния връх Dest. Тогава търсените ребра са всички ребра, свързващи
връх от множеството A с връх от множеството B.
}
CONST MaxN = 100;
VAR G,Flow: array[1..MaxN,1..MaxN] of integer;
N, Source, Dest: integer;
Procedure ReadData;
Var F: Text;
v1,v2,Len: integer;
Begin
Assign(F,'POTOK.PAS'); Reset(F); ReadLn(F);
FillChar(G,SizeOf(G),0);
ReadLn(F,N);
repeat
ReadLn(F,v1,v2,Len);
if v1=0 then Break;
G[v1,v2]:=Len;
until false;
ReadLn(F,Source,Dest);
Close(F);
End;
Procedure FindMinimalFlow;
Var Path: array[1..MaxN] of integer;
Sign: array[1..MaxN-1] of boolean;
Poseten: array[1..MaxN] of boolean;
Found: boolean;
Procedure PathFound(Len:integer);
Function Min(a,b:integer): integer;
Begin if a < b then Min:=a else Min:=b end;
Var Value,I: integer;
Begin
Value:=MaxInt;
for I:= 1 to Len-1 do
if Sign[I] then
Value:= Min( Value, G[Path[I],Path[I+1]] - Flow[Path[I],Path[I+1]] )
else Value:= Min( Value, Flow[Path[I+1],Path[I]] );
for I:= 1 to Len-1 do
if Sign[I] then
Inc( Flow[Path[I],Path[I+1]], Value )
else Dec( Flow[Path[I+1],Path[I]], Value );
Found:=true;
End;
Procedure FindPath(v,Br:integer);
Var Next: integer;
Begin
if Found or Poseten[v] then Exit;
Path[Br]:=v; Poseten[v]:=true;
if v = Dest then PathFound(Br);
for Next:= 1 to N do
if G[v,Next] > Flow[v,Next] then
begin Sign[Br]:=true; FindPath(Next,Br+1); end;
for Next:= 1 to N do
if Flow[Next,v] > 0 then
begin Sign[Br]:=false; FindPath(Next,Br+1); end;
End;
Var I,J, MaxFlow: integer;
Begin
FillChar(Flow,SizeOf(Flow),0);
repeat
Found:=false;
FillChar(Poseten,SizeOf(Poseten),false);
FindPath(Source,1);
until not Found;
MaxFlow:=0;
for I:= 1 to N do
Inc(MaxFlow,Flow[Source,I]);
WriteLn('Maximal flow = ',MaxFlow);
for I:= 1 to N do
for J:= 1 to N do
if Flow[I,J] > 0 then
WriteLn('(',I,',',J,') = ',Flow[I,J]);
End;
BEGIN
ReadData;
FindMinimalFlow;
END.