INFOMAN брой 6
{ Това са входните данни: N; N списъка от наследници
12
7
7 8
8
9
10
11
1
1
6 10
МИНИМАЛНО ДОМИНИРАЩО МНОЖЕСТВО ОТ ВЪРХОВЕ В ГРАФ
(БАЗА НА ГРАФ)
------------------------------------------------
Даден е насочен граф G. Доминиращо множество от върхове в граф наричаме
такова множество D, че за произволен връх p, който не е от това множество
съществува насочен път от някой от върховете на D до p. Минимално домини-
ращо множество в граф наричаме доминиращо множество състоящо се от минима-
лен брой върхове. Да разгледаме следната задача:Дадена е компютърна мрежа
в която всеки компютър предава информация на няколко други компютъра, кои-
то са дадени (но те не задължително му предават на него). Някакъв софтуер
трябва да достигне до всички компютри посредством тази мрежа. Да се наме-
ри минималния брой компютри,на които този софтуер трябва да се предостави,
за да се разпространи той до всеки един компютър от мрежата. Тази задача
е типичен пример за намиране на доминиращо множество от върхове в насочен
граф.
РЕШЕНИЕ: Ще използваме следния алгоритъм за намиране наминимално доми-
ниращо множество от върхове в насочен граф:
D:= [];
Vazmojni:= [1..N];
while има p, p î Vazmojni do
Dostijimi:= [всички достижими от p върхове];
Vazmojni:= Vazmojni - Dostijimi;
D:= D - Dostijimi + [p];
end;
WriteLn(D);
На всяка стъпка от дадения алгоритъм се взема някакъв връх p, който се до-
бавя към доминиращото множество D. Очевидно всички достижими от този връх
върхове не могат да са част от минималното доминиращото множество, защото
са излишни, и затова не се разглеждат повече (изключват се от множеството
Vazmojni). Често се получава,че след прибавянето на върха p в множеството
D, някои негови елементи q се оказват излишни (q са достижими от p). Тога-
ва те се изваждат от множеството (D:= D - Dostijimi).Така по естествен на-
чин накрая в D остават минималния брой доминиращи върхове. Алгоритъма има
сложност по-малка от Ný дори в най-лошия случай.
ДОПЪЛВАНЕ НА ГРАФА ДО СИЛНОСВЪРЗАН
----------------------------------
Приложението на алгоритъма за намиране на минимално доминиращо множество
от върхове в граф не се изчерпва само в разни задачки от сорта на посоче-
ната по-горе, но има тясна връзка със силна свързаност на граф и е много
ефективен при допълване на граф до силносвързан с минимален брой нови ре-
бра. Нека да наричаме графа G1, получен от графа G чрез обръщане на посо-
ката на всичките му ребра, обратен граф на G. Ще дефинираме следния алго-
ритъм за намиране на минималния брой ребра и самите тях, които трябва да
се добавят към графа, за да се допълни до силно свързан:
1. Намираме миним.домин.множ. в G - D и мин.дом.множ. в G1 (обратния
граф на G) - CD. Нека означаваме с p->q наличието на ориентиран път от p
до q. Да предположим, че |D| > |CD|, p1,p2 î D и q1,q2 î CD.
2. Докато |CD|>1 повтаряме: Намираме път p1->q1 и друг път p2->q2.До-
бавяме новото ребро q2-p1.С други търсим два различни пътя от едното мно-
жество до другото и свързваме единия път с другия. Изваждаме p1 от множе-
ството D и q2 от CD.
3. Свързваме всичките останали елементи p на D с останалия един еле-
мент q от множеството CD с новото насочено ребро q-p.
Верността на алгоритъма произтича от следните предпоставки. Ако един
насочен граф е свързан в едната посока, то минималното доминиращо множес-
тво от върхове съдържа точно един елемент. Ако графът е свързан и в дру-
гата посока, то минималното домин.множ. от върхове на обратния граф също
трябва да представлява само един елемент. Това означава, че ако множест-
вата D и CD са едноелементови и се състоят от един и същ единствен връх,
то графът е силно свързан. Понеже при всяко добавяне на ребро и изважда-
не на по един връх и от двете множествата D и CD тези множества продължа-
ват да бъдат миним.доминир.множества на новополучения граф и обратния му
граф, то след точно Max(|D|, |CD|) добавяния на ребро ще се получи силно
свързан граф. Понеже множествата D и CD са минимални, то алгоритъмът ще
добави минимален брой ребра.
}
CONST MaxVr = 100;
TYPE Graf = array[1..MaxVr] of record
BrNasl: byte;
Nasl: array[1..MaxVr] of byte;
end;
VruhSet = array[1..MaxVr] of boolean;
VAR G: Graf;
N: byte;
Procedure ReadData;
Var F: Text;
I: byte;
Begin
FillChar(G,SizeOf(G),0);
Assign(F,'DOMINATE.PAS'); Reset(F); ReadLn(F);
Read(F,N);
for N:= 1 to N do
begin
ReadLn(F);
while not EoLn(F) do
with G[N] do
begin Read(F,I); Inc(BrNasl); Nasl[BrNasl]:=I; end;
end;
Close(F);
End;
Procedure FindDominationSet(var G:Graf; var D:VruhSet); {Намира в D минимал-}
Var Vazmojni,Poseten: VruhSet; {ното доминиращо множество от върхове в графа}
p: byte;
Procedure Obhodi(v:byte); {Спуска се в дълбочина от върха v и прибавя}
Begin {всички достижими от него върхове в D, а ги изважда от Vazmozno}
if Poseten[v] then Exit; Poseten[v]:=true;
Vazmojni[v]:=false; D[v]:=false;
with G[v] do
for v:= 1 to BrNasl do
Obhodi(Nasl[v]);
End;
Begin
FillChar(Vazmojni,SizeOf(Vazmojni),true);
FillChar(D,SizeOf(D),false);
for p:= 1 to N do
if Vazmojni[p] then
begin
FillChar(Poseten,SizeOf(Poseten),false);
Obhodi(p); D[p]:=true;
end;
End;
Procedure MakeStronglyConected;
Type Dostijimost = array[1..MaxVr,1..MaxVr] of boolean;
Var G1: ^Graf;
D,CD: VruhSet;
i,u,v,p1,q1,p2,q2,BrD,BrCD: byte;
ImaPath: ^Dostijimost;
Procedure Obhodi(v:byte);
Begin
if ImaPath^[i,v] then Exit;
ImaPath^[i,v]:=true;
with G[v] do
for v:= 1 to BrNasl do
Obhodi(Nasl[v]);
End;
Procedure FindP1Q1P2Q2(var pp1,qq1,pp2,qq2:byte);
Var p1,q1,p2,q2: byte;
Begin {Намира p1->q1 и p2->q2, p1<>p2, q1<>q2}
for p1:= 1 to N do if D[p1] then
for q1:= 1 to N do
if CD[q1] and ImaPath^[p1,q1] then
for p2:= 1 to N do
if D[p2] and ((p2<>p1)or(BrD=1)) then
for q2:= 1 to N do
if CD[q2] and ((q2<>q1)or(BrCD=1)) and ImaPath^[p2,q2] then
begin pp1:=p1; qq1:=q1; pp2:=p2; qq2:=q2; Exit; end;
End;
Begin
FindDominationSet(G,D); {Намираме D}
New(G1); FillChar(G1^,SizeOf(G1^),0);
for u:= 1 to N do {Образуваме обратния граф G1}
with G[u] do for i:= 1 to BrNasl do
begin
v:=Nasl[i];
with G1^[v] do
begin Inc(BrNasl); Nasl[BrNasl]:=u end;
end;
FindDominationSet(G1^,CD); {Намираме CD}
Dispose(G1);
BrD:=0; for i:= 1 to N do if D[i] then Inc(BrD);
BrCD:=0; for i:= 1 to N do if CD[i] then Inc(BrCD);
New(ImaPath); FillChar(ImaPath^,SizeOf(ImaPath^),false);
for i:= 1 to N do Obhodi(i); {Намираме матрицата ImaPath}
while (BrD>1) or (BrCD>1) do
begin
FindP1Q1P2Q2(p1,q1,p2,q2);
Write(q2,'ÄÄ',p1,' ');
for u:= 1 to N do {добавяме реброто q2-p1 и преизчисляваме ImaPath}
if ImaPath^[u,q2] then
for v:= 1 to N do
if ImaPath^[p1,v] then
ImaPath^[u,v]:=true;
if BrD > 1 then {изваждаме върха p1 от D}
begin Dec(BrD); D[p1]:=false; end;
if BrCD > 1 then {изваждаме върха q2 от CD}
begin Dec(BrCD); CD[q2]:=false; end;
end;
for p1:= 1 to N do if D[p1] then Break;
for q2:= 1 to N do if CD[q2] then Break;
if p1 = q2 then {Множествата D и CD са еднакви и едноелементови}
WriteLn('Графът е силно свързан!')
else WriteLn(q2,'ÄÄ',p1,' ');
End;
VAR D: VruhSet;
I: byte;
BEGIN
ReadData;
FindDominationSet(G,D);
for i:= 1 to N do if D[i] then Write(i,' '); WriteLn;
MakeStronglyConected;
END.