INFOMAN брой 15
{ This is the input data: N; edge_count; edge list
10 17
1 8 1 9 1 10 2 4 2 5 2 9 3 6 3 6 3 7
4 5 4 7 4 9 4 10 5 2 5 6 7 8 8 10
N-свързаност на граф
--------------------
Даден е неориентиран свързан граф. Пита се колко най-малко ребра трябва
да премахнем от него, за да се разкъса той на две компоненти.
РЕШЕНИЕ: Ще използваме факта, че ако един граф не може да се разкъса от
премахването на K ребра, той е K-свързан, т.е. между всеки два негови върха
има най-малко K на брой различни пътя. (Това не означава, че не може да се
разкъса ако премахнем K или по-малко върха. Има разлика! Ние имаме предвид
ребрена K-свързаност). Можем да намерим колко различни пътя (несъдържащи ед-
накви ребра) има между два върха. Това става с намиране на максимален поток
в графа, като се съпостави пропусклива способност 1 на всяко ребро. Понеже
максималният поток е равен на минималния разрез и по всяко ребро може да те-
че поток 0 или 1, потокът всъщност изразява броя пътища в графа. За да наме-
рим свързаността на графа, трябва от някой върх (да кажем от връх 1) да на-
мерим максималния поток до всички останали върхове. И нека f(v) е максимал-
ният поток от връх 1 до връх v. Тогава минималният брой ребра K, които тряб-
ва да премахнем от графа, за да го разкъсаме е минималното f(v) за v=[2..N].
Нека P е множеството на всички върхове v, за които f(v)=K. Получава се така,
че K съдържа всички компоненти на K-ребрена-съврзаност в графа. Ето защо мо-
жем да построим нов граф G' от множеството върхове P. Компонентите на свър-
заност на G' са компонентите на K-свързаност на първоначалния граф. Нека Q
е една такава компонента. Всички ребра от Q към някой връх, който не е от Q,
трябва да се премахнат, за да се разкъса оригиналният граф на две компонен-
ти. Броят им е точно K - минималния брой. С това задачата е решена. Ще отбе-
лежим само, че максималния поток се търси по алгоритъма на Ford-Fulkerson и
има сложност O(N*N*N), така че общата сложност на алгоритъма е O(N*N*N*N).
Star Gruhtar
май, 1999
}
CONST MaxN = 100;
EndLess = MaxInt;
VAR N: integer;
G,Flow: array[1..MaxN,1..MaxN] of integer;
Procedure ReadData;
Var F: Text;
Count,v1,v2: integer;
Begin
Assign(F,'N-CONECT.PAS'); Reset(F); ReadLn(F);
FillChar(G,SizeOf(G),0);
ReadLn(F,N,Count);
for Count:= 1 to Count do
begin
Read(F,v1,v2);
Inc(G[v1,v2]); Inc(G[v2,v1]);
end;
Close(F);
End;
Function FindMaximalFlow(Source,Dest:integer): integer;
{ Find the maximum flow Flow[] in G[] }
Var Path: array[1..MaxN] of integer;
Poseten: array[1..MaxN] of boolean;
FoundPath: boolean;
MaxFlow: integer;
Procedure AugumentFlow(len:integer); { Augument the flow by Path[1..len] }
Var i, v1, v2, F: integer;
Begin
{find the maximum augumenting value - F}
F:=EndLess;
for i:= 1 to Len-1 do
begin
v1:=Path[i]; v2:=Path[i+1];
if G[v1,v2]-Flow[v1,v2] + Flow[v2,v1] < F then
F:= G[v1,v2]-Flow[v1,v2] + Flow[v2,v1];
end;
MaxFlow:=MaxFlow+F;
{augument the network flow by F}
for i:= 1 to Len-1 do
begin
v1:=Path[i]; v2:=Path[i+1];
if Flow[v2,v1] > 0 then
Dec(Flow[v2,v1],F)
else Inc(Flow[v1,v2],F);
end;
End;
Procedure FindAugumentingPath(v,len:integer);
Var next: integer; { Find an augumenting path in the network if any }
Begin
if Poseten[v] or FoundPath then Exit;
Poseten[v]:=true; Path[len]:=v;
if v = Dest then
begin FoundPath:=true; AugumentFlow(len); end;
for next:= 1 to N do
if (G[v,next] > Flow[v,next]) or (Flow[next,v] > 0) then
FindAugumentingPath(next,len+1);
End;
Begin
FillChar(Flow,SizeOf(Flow),0);
MaxFlow:=0;
repeat
FillChar(Poseten,SizeOf(Poseten),false);
FoundPath:=false;
FindAugumentingPath(Source,1);
until not FoundPath;
FindMaximalFlow:=MaxFlow;
End;
Procedure FindMinimalEdgesToDisconnect;
{ Disconnect the graph removing minimal in number edges }
Var u,v,MinCut: integer;
F: array[1..MaxN] of integer;
InComponent:array[1..MaxN] of boolean;
Procedure DFS(v:integer);
Var next: integer;
Begin
if InComponent[v] or (F[v]<>MinCut) then Exit;
InComponent[v]:=true;
for next:= 1 to N do
if G[v,next] > 0 then
DFS(next);
End;
Function Min(a,b:integer): integer;
Begin if a < b then Min:=a else Min:=b End;
Begin
{find the minimal cut in the graph}
MinCut:=EndLess;
for v:= 2 to N do
begin
F[v]:= FindMaximalFlow(1,v);
MinCut:= Min( MinCut, F[v] );
end;
WriteLn('Minimum edges to disconnect the graph: ',MinCut);
{find the edges of the minumum cut}
FillChar(InComponent,SizeOf(InComponent),false);
for v:= 1 to N do
if F[v] = MinCut then
begin DFS(v); Break; end;
WriteLn('The edges are:');
for u:= 1 to N do
for v:= u+1 to N do
if G[u,v] > 0 then
if InComponent[u]<>InComponent[v] then
WriteLn(' (',u,',',v,')');
End;
BEGIN
ReadData;
FindMinimalEdgesToDisconnect;
END.