Aëãîðèòìû íà ãðàôàõ

20554
çíàêà
0
òàáëèö
0
èçîáðàæåíèé
Ýëåìåíòû òåîðèè ãðàôîâ.

Ãðàô - ñîâîêóïíîñòü òî÷åê è ëèíèé, â êîòîðîé êàæäàÿ ëèíèÿ ñîåäèíÿåò äâå òî÷êè. Òî÷êè íàçûâàþòñÿ âåðøèíàìè, èëè óçëàìè, ãðàôà, ëèíèè - ðåáðàìè ãðàôà. Åñëè ðåáðî ñîåäèíÿò äâå âåðøèíû, òî ãîâîðÿò, ÷òî îíî èì èíöèäåíòíî; âåðøèíû, ñîåäèíåííûå ðåáðîì íàçûâàþòñÿ ñìåæíûìè. Äâå âåðøèíû, ñîåäèíåííûå ðåáðîì, ìîãóò ñîâïàäàòü; òàêîå ðåáðî íàçûâàåòñÿ ïåòëåé. ×èñëî ðåáåð, èíöèäåíòíûõ âåðøèíå, íàçûâàåòñÿ ñòåïåíüþ âåðøèíû. Åñëè äâà ðåáðà èíöèäåíòíû îäíîé è òîé æå ïàðå âåðøèí, îíè íàçûâàþòñÿ êðàòíûìè; ãðàô, ñîäåðæàùèé êðàòíûå ðåáðà, íàçûâàåòñÿ ìóëüòèãðàôîì.

Ðåáðî, ñîåäèíÿþùåå äâå âåðøèíû, ìîæåò èìåòü íàïðàâëåíèå îò îäíîé âåðøèíû ê äðóãîé; â ýòîì ñëó÷àå îíî íàçûâàåòñÿ íàïðàâëåííûì, èëè îðèåíòèðîâàííûì, è èçîáðàæàåòñÿ ñòðåëêîé. Ãðàô, â êîòîðîì âñå ðåáðà îðèåíòèðîâàííûå, íàçûâàåòñÿ îðèåíòèðîâàííûì ãðàôîì (îðãðàôîì); ðåáðà îðãðàôà ÷àñòî íàçûâàþò äóãàìè. Äóãè èìåíóþòñÿ êðàòíûìè, åñëè îíè íå òîëüêî èìåþò îáùèå âåðøèíû, íî è ñîâïàäàþò ïî íàïðàâëåíèþ. Èíîãäà íóæíî ðàññìàòðèâàòü íå âåñü ãðàô, à åãî ÷àñòü (÷àñòü âåðøèí è ÷àñòü ðåáåð). ×àñòü âåðøèí è âñå èíöèäåíòíûå èì ðåáðà íàçûâàþòñÿ ïîäãðàôîì; âñå âåðøèíû è ÷àñòü èíöèäåíòíûõ èì ðåáåð íàçûâàþòñÿ ñóãðàôîì. Öèêëîì íàçûâàåòñÿ çàìêíóòàÿ öåïü âåðøèí. Äåðåâîì íàçûâàåòñÿ ãðàô áåç öèêëîâ. Îñòîâíûì äåðåâîì íàçûâàåòñÿ ñâÿçàííûé ñóãðàô ãðàôà, íå èìåþùèé öèêëîâ.

Ãðàô îäíîçíà÷íî çàäàí, åñëè çàäàíû ìíîæåñòâî åãî âåðøèí, ìíîæåñòâî ðåáåð è óêàçàíû âñå èíöèäåíòíîñòè (ò.å. óêàçàíî, êàêèå âåðøèíû êàêèìè ðåáðàìè ñîåäèíåíû). Íàèáîëåå íàãëÿäíî ãðàô çàäàåòñÿ ðèñóíêîì; îäíàêî íå âñå äåòàëè ðèñóíêà îäèíàêîâî âàæíû; â ÷àñòíîñòè, íåñóùåñòâåííû ãåîìåòðè÷åñêèå ñâîéñòâà ðåáåð (äëèííà, êðèâèçíà è ò.ä.) è âçàèìíîå ðàñïîëîæåíèå âåðøèí íà ïëîñêîñòè.

Äëÿ íåîðèåíòèðîâàííîãî ðåáðà ïîðÿäîê, â êîòîðîì óêàçàííû ñîåäèíÿåìûå èì âåðøèíû, íå âàæåí. Äëÿ îðèåíòèðîâàííîãî ðåáðà âàæíî: ïåðâîé óêàçûâàåòñÿ âåðøèíà, èç êîòîðîé âûõîäèò ðåáðî.

Ìàðøðóò, èëè ïóòü - ýòî ïîñëåäîâàòåëüíîñòü ðåáåð â íåîðèåíòèðîâàííîì ãðàôå, â êîòîðîì êîíåö êàæäîãî ðåáðà ñîâïàäàåò ñ íà÷àëîì ñëåäóþùåãî ðåáðà. ×èñëî ðåáåð ìàðøðóòà íàçûâàåòñÿ åãî äëèííîé.

Ãðàôû øèðîêî èñïîëüçóþòñÿ êàê â ñàìîé ìàòåìàòèêå, òàê è â åå ïðèëîæåíèÿõ. Îíè ïðèìåíÿþòñÿ ïðè ïîñòðîåíèè ðàçëè÷íûõ ìàòåìàòè÷åñêèõ ìîäåëåé: ëèíèé ýëåêòðîïåðåäà÷è, ñåòåé àâòîäîðîã, ëèíèé âîçäóøíûõ ñîîáùåíèé è ïð.

Çàäà÷à ñîñòîèò â òîì, íàéòè ïóòü èç âåðøèíû A â âåðøèíó B. Áóäåì çàäàâàòü ãðàô ìàòðèöåé ñìåæíîñòè, ò.å. êâàäðàòíîé òàáëèöåé NxN, â êîòîðîé íà ïåðåñå÷åíèè i-é ñòðîêè è j-ãî ñòîëáöà çíà÷åíèå TRUE, åñëè i è j ñîåäèíåíû ðåáðîì, è FALSE â ïðîòèâíîì ñëó÷àå.

Ïîèñê â øèðèíó.

Ïîäîáíî òîìó êàê, ñîãëàñíî ïðèíöèïó Ãþéãåíñà, êàæäàÿ òî÷êà âîëíîâîãî ôðîíòà ÿâëÿåòñÿ èñòî÷íèêîì âòîðè÷íîé âîëíû, ìû, îòïðàâëÿÿñü èç çàäàííîé âåðøèíû A, ïîñåùàåì âñå ñìåæíûå ñ íåé âåðøèíû (ò.å. âåðøèíû, â êîòîðûå âåäóò ñòðåëêè èç A). Êàæäàÿ ïîñåùåííàÿ âåðøèíà ñòàíîâèòñÿ èñòî÷íèêîì íîâîé âîëíû è ò.ä. Ïðè ýòîì íåîáõîäèìî ïîçàáîòèòüñÿ î òîì, ÷òîáû íå âåðíóòñÿ â òó âåðøèíó, â êîòîðîé óæå áûëè.

Äëÿ ðåàëèçàöèè àëãîðèòìà ïîíàäîáÿòñÿ:

ìàòðèöà m[1..n, 1..n] - ìàòðèöà ñìåæíîñòè ãðàôà;

âñïîìîãàòåëüíûé ìàññèâ queue[1..n], â êîòîðîì áóäåò ôîðìèðîâàòüñÿ î÷åðåäü, ò.å. òèï äàííûõ ïåðâûé âîøåë – ïåðâûé âûøåë (FIFO). Ðàçìåð åãî äîñòàòî÷åí, òàê êàê ìû íå ïîñåùàåì âåðøèíû äâàæäû. Ñ ìàññèâîì queue ñâÿçàíû äâå ïåðåìåííûå - head è tail.  ïåðåìåííîé head áóäåò íàõîäèòüñÿ íîìåð òåêóùåé âåðøèíû, èç êîòîðîé èäåò âîëíà, à ïðè ïîìîùè ïåðåìåííîé tail íîâûå âåðøèíû ïîìåùàþòñÿ â "õâîñò" î÷åðåäè queue;

âñïîìîãàòåëüíûé ìàññèâ visited[1..n], êîòîðûé íóæåí äëÿ òîãî, ÷òîáû îòìå÷àòü óæå ïðîéäåííûå âåðøèíû (visited[i]=TRUE <=> âåðøèíà i ïðîéäåíà);

âñïîìîãàòåëüíûé ìàññèâ prev[1..n] äëÿ õðàíåíèÿ ïðîéäåííûõ âåðøèí. Â ýòîì ìàññèâå è áóäåò ñôîðìèðîâàí èñêîìûé ïóòü;

ïåðåìåííàÿ f, êîòîðàÿ ïðèìåò çíà÷åíèå TRUE, êîãäà ïóòü áóäåò íàéäåí.

Êðîìå òîãî, ìû ââåäåì íåñêîëüêî âñïîìîãàòåëüíûõ ïåðåìåííûõ, êîòîðûå ïîíàäîáÿòñÿ ïðè îðãàíèçàöèè öèêëîâ.

Program breadth_first_search;

Const n=9;

m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B: integer;

Procedure A_to_B(A, B: integer);

Var

Visited: array[1..n] of boolean;

Prev: array[1..n] of integer;

c: array[1..n] of integer;

head, tail: integer;

f: boolean;

i, v, k: integer;

Begin

head:=1;

tail:=1;

f:=False;

For i:=1 to n do

Begin

Visited[i]:=False;

Prev[i]:=0

End;

C[tail]:=A;

Visited[A]:=True;

While (head<=tail) and not f do

Begin

v:=C[head];

head:=head+1;

For k:=1 to n do

if m[v, k] and not Visited[k] then

Begin

tail:=tail+1;

C[tail]:=k;

Visited[k]:=True;

Prev[k]:=v;

if k=B then

Begin

f:=true;

break

End

End

End;

if f then

Begin

k:=B;

Write(B);

While Prev[k]<>0 do

Begin

Write('<-', Prev[k]);

k:=Prev[k]

end

End

else

Write('Ïóòè èç ', A, ' â ', B, ' íåò')

end;

Begin

Write('A= '); readln(A);

Write('B= '); readln(B);

A_to_B(A, B)

End.

Ïîèñê â ãëóáèíó.

Èäåÿ ïîèñêà â ãëóáèíó ïðîñòà: îòïðàâëÿÿñü îò òåêóùåé âåðøèíû, ìû íàõîäèì íîâóþ (åùå íå ïðîéäåííóþ) ñìåæíóþ ñ íåé âåðøèíó, êîòîðóþ ïîìå÷àåì êàê ïðîéäåííóþ è îáúÿâëÿåì òåêóùåé. Ïîñëå ýòîãî ïðîöåññ âîçîáíîâëÿåòñÿ. Åñëè íîâîé ñìåæíîé âåðøèíû íåò (òóïèê), âîçâðàùàåìñÿ ê òîé âåðøèíå, èç êîòîðîé ïîïàëè â òåêóùóþ, è äåëàåì ñëåäóþùóþ ïîïûòêó. Åñëè ïîïàäåì â âåðøèíó B, ïå÷àòàåì ïóòü. Åñëè âñå âåðøèíû èñ÷åðïàíû - òàêîãî ïóòè íåò.

Çàìåòèì, ÷òî ïîñòðîåííûé òàêèì îáðàçîì àëãîðèòì ñïîñîáåí íàõîäèòü âñå ïóòè èç A â B, íî ïåðâûé íàéäåííûé íåîáÿçàòåëüíî äîëæåí áûòü êðàò÷àéøèì.

Êàê îáû÷íî, àëãîðèòì ñ âîçâðàòàìè ëåã÷å âñåãî îôîðìèòü ñ ïîìîùüþ ðåêóðñèâíîé ïðîöåäóðû. Äëÿ åå ðåàëèçàöèè íàì ïîíàäîáÿòñÿ:

ìàòðèöà m[1..n, 1..n] - ìàòðèöà ñìåæíîñòè ãðàôà;

âñïîìîãàòåëüíûé ìàññèâ visited[1..n], êîòîðûé ìû áóäåì äëÿ òîãî, ÷òîáû îòìå÷àòü óæå ïðîéäåííûå âåðøèíû (visited[i]=TRUE <=> âåðøèíà i ïðîéäåíà);

ïåðåìåííàÿ f, êîòîðàÿ ïðèìåò çíà÷åíèå TRUE, êîãäà ïóòü áóäåò íàéäåí.

Program depth_first_search;

Const n=9;

m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B: integer;

Procedure A_to_b(A, B: integer);

Var

Visited: array[1..n] of boolean;

f: boolean;

i: integer;

Procedure Depth(p: integer);

var k: integer;

Begin

Visited[p]:=True;

For k:=1 to n do

If not f then

If m[p, k] and not Visited[k] then

If k=B then

Begin

f:=True;

Write(B);

Break

End

else Depth(k);

If f then write('<=', p);

End;

Begin

For i:=1 to n do Visited[i]:=False;

f:=false;

Depth(A);

If not f then write('Ïóòè èç ', A, ' â ', B, ' íåò')

End;

Begin

write('A= '); readln(A);

write('B= '); readln(B);

A_to_B(A, B)

End.

Ýéëåðîâû öèêëû.

Òðåáóåòñÿ íàéòè öèêë, ïðîõîäÿùèé ïî êàæäîé äóãå ðîâíî îäèí ðàç. Ýòó çàäà÷ó âïåðâûå ïîñòàâèë è ðåøèë Ëåîíàðä Ýéëåð, ÷åì è çàëîæèë îñíîâû òåîðèè ãðàôîâ, à ñîîòâåòñòâóþùèå öèêëû òåïåðü íàçûâàþòñÿ ýéëåðîâûìè.

Çàäà÷à âîçíèêëà èç ïðåäëîæåííîé Ýéëåðó ãîëîâîëîìêè, ïîëó÷èâøåé íàçâàíèå "ïðîáëåìà êåíèãñáåðãñêèõ ìîñòîâ". Ðåêà Ïðåãåëü, ïðîòåêà þùàÿ ÷åðåç Êàëèíèíãðàä (ïðåæäå ãîðîä íàçûâàëñÿ Êåíèãñáåðãîì), îìûâàåò äâà îñòðîâà. Áåðåãà ðåêè ñâÿçàíû ñ îñòðîâàìè òàê, êàê ýòî ïîêàçàíî íà ðèñóíêå.  ãîëîâîëîìêå òðåáîâàëîñü íàéòè ìàðøðóò, ïðîõîäÿùèé ïî âñåì ó÷àñòêàì ñóøè òàêèì îáðàçîì, ÷òîáû êàæäûé èç ìîñòîâ áûë ïðîéäåí ðîâíî îäèí ðàç, à íà÷àëüíûé è êîíå÷íûé ïóíêòû ìàðøðóòà ñîâïàäàëè.

Âûáåðåì â êà÷åñòâå âåðøèí ãðàôà áåðåãà ðåêè, à â êà÷åñòâå ðåáåð - ìîñòû, èõ ñîåäèíÿþùèå. Ïîñëå ýòîãî çàäà÷à ñòàíîâèòñÿ î÷åâèäíîé: òðåáîâàíèå íåîñóùåñòâèìî - ÷òîáû åãî âûïîëíèòü, ÷èñëî äóã, ïðèõîäÿùèõ ê êàæäîé âåðøèíå, äîëæíî áûòü ÷åòíûì.  ñàìîì äåëå, ïîñêîëüêó ïî îäíîìó ìîñòó íåëüçÿ ïðîõîäèòü äâàæäû, êàæäîìó âõîäó íà áåðåã äîëæåí ñîîòâåòñòâîâàòü âûõîä.

×òî íåîáõîäèìî, ÷òîáû â ãðàôå ñóùåñòâîâàë ýéëåðîâ öèêë? Âî-ïåðâûõ, ãðàô äîëæåí áûòü ñâÿçàííûì: äëÿ ëþáûõ äâóõ âåðøèí äîëæåí ñóùåñòâîâàòü ïóòü, èõ ñîåäèíÿþùèé. Âî-âòîðûõ, äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ ÷èñëî ðåáåð â êàæäîé âåðøèíå äîëæíî áûòü ÷åòíûì. Íà ñàìîì äåëå ýòîãî îêàçûâàåòñÿ äîñòàòî÷íî.

Òåîðåìà. ×òîáû â ñâÿçàííîì ãðàôå ñóùåñòâîâàë ýéëåðîâ öèêë, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ÷èñëî ðåáåð â êàæäîé âåðøèíå áûëî ÷åòíûì.

Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü äîêàçàíà âûøå. Äîêàçàòåëüñòâî äîñòàòî÷íîñòè êîíñòðóêòèâíî - â ðåçóëüòàòå áóäåò ïîëó÷åí òðåáóåìûé àëãîðèòì.

Äîêàçàòåëüñòâî âåäåòñÿ èíäóêöèåé ïî ÷èñëó ðåáåð ãðàôà. Ïóñòü óòâåðæäåíèå äîêàçàíî äëÿ âñåõ m<n. Ðàññìîòðèì ãðàô ñ n ðåáðàìè. Âûáåðåì ïðîèçâîëüíóþ âåðøèíó A è íà÷íåì ñòðîèòü òðåáóåìûé ïóòü, âû÷åð÷èâàÿ (ñòèðàÿ) êàæäîå ðåáðî, ïî êîòîðîìó ïðîõîäèì, ÷òîáû íå ïðîéòè åãî äâàæäû.

Çàìåòèì, ÷òî, ïîêà ìû íå âåðíóëèñü â À, ìû âñåãäà ìîæåì ïðîäîëæèòü ïóòü èç òåêóùåãî óçëà X ïî êðàéíåé ìåðå íà îäíî ðåáðî.  ñàìîì äåëå, êàæäûé ïðîõîä ÷åðåç X îñòàâëÿåò ÷åòíûì ÷èñëî ðåáåð â ýòîé âåðøèíå. Ïîýòîìó, åñëè ìû âõîäèì â X, îñòàåòñÿ íå÷åòíîå ÷èñëî íåâû÷åðêíóòûõ ðåáåð, èç íåå âûõîäÿùèõ (ïî êðàéíåé ìåðå îäíî ðåáðî). Ïóñòü ìû âåðíóëèñü â A. Òîãäà, åñëè âñå ðåáðà âû÷åðêíóòû, òåîðåìà äîêàçàíà.  ïðîòèâíîì ñëó÷àå îñòàâøèåñÿ ðåáðà ðàñïàäàþòñÿ íà ñâÿçàííûå ïîäãðàôû, êàæäûé èç êîòîðûõ ñîäåðæèò õîòÿ áû îäíó âåðøèíó èç óæå ïîñòðîåííîãî öèêëà (ïîñêîëüêó ïåðâîíà÷àëüíûé ãðàô ñâÿçàííûé) è ñîäåðæèò ìåíåå n ðåáåð. Ïóñòü, …,– âåðøèíû óêàçàííûõ ïîäãðàôîâ, ÷åðåç êîòîðûå ïðîõîäèò ïîñòðîåííûé ïóòü.

Ïî ïðåäïîëîæåíèþ èíäóêöèè â êàæäîì èç íèõ ñóùåñòâóåò ýéëåðîâ öèêë. Ñòðîèì òåïåðü íîâûé ïóòü èç A ñëåäóþùèì îáðàçîì:

– èäåì ïî ñòàðîìó ïóòè äî;

– âêëþ÷àåì â íåãî íîâûé ïóòü;

– èäåì ïî ñòàðîìó ïóòè îò äî;

– ïîâòîðÿåì ïðîöåññ äëÿ âåðøèíû è ò.ä.

Äëÿ îêîí÷àíèÿ äîêàçàòåëüñòâà (è ïîñòðîåíèÿ àëãîðèòìà) çàìåòèì, ÷òî áàçà èíäóêöèè î÷åâèäíà: åñëè ðåáðî îäíî, òî îíî – ïåòëÿ.

Õîòÿ äîêàçàòåëüñòâî ïðîâåäåíî äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ, îíî ñðàçó ïåðåíîñèòñÿ íà îðèåíòèðîâàííûå, òîëüêî òðåáîâàíèå ÷åòíîñòè çàìåíÿåòñÿ òåïåðü íà òàêîå: ÷èñëî âõîäÿùèõ â êàæäóþ âåðøèíó ðåáåð äîëæíî áûòü ðàâíî ÷èñëó âûõîäÿùèõ.

Îñòàëîñü çàìåòèòü, ÷òî ïðåäëîæåííûé â äîêàçàòåëüñòâå àëãîðèòì ëèíååí, ò.å. ÷èñëî äåéñòâèé ïðÿìî ïðîïîðöèîíàëüíî ÷èñëó ðåáåð.

Program Euler;

const n=9;

m: array[1..n, 1..n] of boolean=

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Type

list=^node;

node=record

i: integer;

next: list

end;

Var stack1, stack2: list;

v, u, x, i: integer;

Procedure Push(x: integer; var stack: list);

Var temp: list;

Begin

New(temp);

temp^.i:=x;

temp^.next:=stack;

stack:=temp

End;

Procedure Pop(var x: integer; var stack: list);

Begin

x:=stack^.i;

stack:=stack^.next

End;

Function Peek(stack: list): integer;

Begin

Peek:=stack^.i

End;

Procedure PrintList(l: list);

Begin

Writeln;

If l=nil then writeln('NIL');

While l<>nil do

Begin

Write(l^.i:3);

l:=l^.next

End

End;

Begin

stack1:=nil;

stack2:=nil;

Write('Íà÷àëüíàÿ âåðøèíà: ');readln(v);

Push(v, stack1);

While stack1<>NIL do

Begin

v:=peek(stack1);

i:=1;

While (i<=n) and not m[v, i] do inc(i);

If i<=n then

Begin

u:=i;

Push(u, stack1);

m[v, u]:=False;

m[u, v]:=False;

End

else

Begin

pop(x, stack1);

push(x, stack2)

End

End;

PrintList(stack2)

End.

Çàäà÷à Ïðèìà–Êðàñêàëà.

Äàíà ïëîñêàÿ ñòðàíà è â íåé n ãîðîäîâ. Íóæíî ñîåäèíèòü âñå ãîðîäà òåëåôîííîé ñâÿçüþ òàê, ÷òîáû îáùàÿ äëèííà òåëåôîííûõ ëèíèé áûëà ìèíèìàëüíîé.

Èëè â òåðìèíàõ òåîðèè ãðàôîâ:

Äàí ãðàô ñ n âåðøèíàìè; äëèíû ðåáåð çàäàíû ìàòðèöåé. Íàéòè îñòîâíîå äåðåâî ìèíèìàëüíîé äëèíû.

Ïðåäñòàâèì ñåáå, ÷òî çèìîâùèêó îñòàâëåí íåêîòîðûé çàïàñ ïðîäóêòîâ, è åãî çàäà÷åé ÿâëÿåòñÿ ñîñòàâëåíèå âêóñíîãî ìåíþ íà âñþ çèìó. Åñëè çèìîâùèê íà÷íåò ñ òîãî, ÷òî ñïåðâà áóäåò åñòü ñàìóþ âêóñíóþ åäó (íàïðèìåð, øîêîëàä), ïîòîì – âòîðóþ ïî âêóñíîñòè (íàïðèìåð, ìÿñî), òî îí ðèñêóåò îñòàâèòü íà ïîñëåäíèé ìåñÿö òîëüêî ñîëü è ìàðãàðèí. Ïîäîáíûì îáðàçîì, åñëè îïòèìàëüíûé (äëÿ îïðåäåëåííîñòè, ìèíèìàëüíûé) îáúåêò ñòðîèòñÿ êàê-òî ïî øàãàì, òî íåëüçÿ íà ïåðâîì øàãå âûáèðàòü ÷òî-íèáóäü ñàìîå ìàëîå, íà âòîðîì øàãå – îñòàâøååñÿ ñàìîå ìàëîå è ò.ä. Çà òàêóþ ïîëèòèêó îáû÷íî ïðèõîäèòñÿ ðàñïëà÷èâàòüñÿ íà ïîñëåäíèõ øàãàõ. Òàêîé àëãîðèòì íàçûâàåòñÿ æàäíûì.

Óäèâèòåëüíî, íî â çàäà÷å Ïðèìà–Êðàñêàëà, êîòîðàÿ íå êàæåòñÿ îñîáåííî ïðîñòîé, æàäíûé àëãîðèòì äàåò òî÷íîå îïòèìàëüíîå ðåøåíèå.

Êàê èçâåñòíî (ýòî ëåãêî äîêàçàòü ïî èíäóêöèè), äåðåâî ñ n âåðøèíàìè èìååò n-1 ðåáåð. Îêàçûâàåòñÿ, êàæäîå ðåáðî íóæíî âûáèðàòü æàäíî (ëèøü áû íå âîçíèêàëè öèêëû). Òî åñòü n-1 ðàç âûáèðàòü ñàìîå êîðîòêîå ðåáðî èç åùå íå âûáðàííîå ðåáðî ïðè óñëîâèè, ÷òî îíî íå îáðàçóåò öèêëà ñ óæå âûáðàííûìè.

À êàê ñëåäèòü, ÷òîáû íîâîå ðåáðî íå îáðàçîâûâàëî öèêëà ñî ñòàðûìè? Ñäåëàòü ýòî ïðîñòî. Äî ïîñòðîåíèÿ äåðåâà îêðàñèì êàæäóþ âåðøèíó i â îòëè÷íûé îò äðóãèõ öâåò i. Ïðè âûáîðå î÷åðåäíîãî ðåáðà, íàïðèìåð (i, j), ãäå i è j èìåþò ðàçíûå öâåòà, âåðøèíà j è âñå, îêðàøåííûå â åå öâåò (ò.å. ðàíåå ñ íåé ñîåäèíåííûå) ïåðåêðàøèâàþòñÿ â öâåò i. Òàêèì îáðàçîì, âûáîð âåðøèí ðàçíîãî öâåòà îáåñïå÷èâàåò îòñóòñòâèå öèêëîâ. Ïîñëå âûáîðà n-1 ðåáåð âñå âåðøèíû ïîëó÷àþò îäèí öâåò.

Äîêàæåì, ÷òî îïèñàííûé àëãîðèòì ïîëó÷àåò â òî÷íîñòè ìèíèìàëüíîå ðåøåíèå. Äëÿ äîêàçàòåëüñòâà íàì ïîíàäîáèòñÿ î÷åíü ïðîñòîå óòâåðæäåíèå:

Åñëè ê äåðåâó äîáàâèòü ðåáðî, òî â äåðåâå ïîÿâèòñÿ öèêë, ñîäåðæàùèé ýòî ðåáðî.

Äåéñòâèòåëüíî, ïóñòü äîáàâëåíî ðåáðî (u, v) – “äîáàâëåíî” îçíà÷àåò, ÷òî ðåáðî – íîâîå, ÷òî ðàíüøå åãî â äåðåâå íå áûëî. Ïîñêîëüêó äåðåâî ÿâëÿåòñÿ ñâÿçàííûì ãðàôîì, òî ñóùåñòâóåò öåïü C(u, …, v) èç íåñêîëüêèõ ðåáåð, ñîåäèíÿþùàÿ âåðøèíû u è v. Äîáàâëåíèå ðåáðà (u, v) çàìûêàåò öåïü, ïðåâðàùàÿ åå â öèêë.

Òåîðåìà. Àëãîðèòì Ïðèìà–Êðàñêàëà ïîëó÷àåò ìèíèìàëüíîå îñòîâíîå äåðåâî.

Äîêàçàòåëüñòâî. Ðåçóëüòàòîì ðàáîòû àëãîðèòìà ÿâëÿåòñÿ íàáîð èç n-1 ðåáåð. Îíè íå îáðàçóþò öèêëà, èáî íà êàæäîì èç n-1 øàãîâ ñîåäèíÿëèñü âåðøèíû ðàçíîãî öâåòà, ò.å. ðàíåå íå ñâÿçàííûå. Ýòîò ãðàô ñâÿçíûé, ïîòîìó ÷òî ïîñëå ïðîâåäåíèÿ 1-ãî ðåáðà îñòàëîñü n-1 ðàçíûõ öâåòîâ, …, ïîñëå ïðîâåäåíèÿ (n-1)-ãî ðåáðà îñòàëñÿ îäèí öâåò, ò.å. îäíà êîìïîíåíòà ñâÿçíîñòè. Èòàê, ïîëó÷åííûé íàáîð ðåáåð îáðàçóåò ñâÿçíûé ãðàô áåç öèêëîâ, ñîäåðæàùèé n-1 ðåáåð è n âåðøèí. Ñëåäîâàòåëüíî, ãðàô åñòü îñòîâíîå äåðåâî.

Äëÿ ðåàëèçàöèè àëãîðèòìà ïîíàäîáÿòñÿ:

Matrix – ìàòðèöà ðàññòîÿíèé, çíà÷åíèå ïåðåñå÷åíèè i-îé ñòðîêè è j-ãî ñòîëáöà ðàâíî ðàññòîÿíèþ ìåæäó i-îé è j-îé âåðøèíàìè. Åñëè òàêîãî ðåáðà íåò òî çíà÷åíèå ðàâíî Infinity – ïðîñòî áîëüøîìó ÷èñëó (ìàøèííàÿ áåñêîíå÷íîñòü);

Color – ìàññèâ öâåòîâ âåðøèí;

Ribs – â ýòîì ìàññèâå çàïîìèíàþòñÿ íàéäåííûå ðåáðà;

a, b – âåðøèíû, ñîåäèíÿåìûå î÷åðåäíûì ìèíèìàëüíûì ðåáðîì

len – äëèíà äåðåâà.

Ìàòðèöó ðàññòîÿíèé áóäåì õðàíèòü â òåêñòîâîì ôàéëå INPUT.MTR, ãäå ÷èñëî íà ïåðâîé ñòðîêå – êîëè÷åñòâî âåðøèí n, à îñòàëüíûå n ñòðîê ïî n ÷èñåë â êàæäîé – ìàòðèöà ðàññòîÿíèé. Åñëè ðàññòîÿíèå ðàâíî 1000 (Infinity), òî òàêîãî ðåáðà íåò.

Program Algorithm_PrimaKrascala;

Uses Crt;

Const MaxSize =100;

Infinity =1000;

Var Matrix: array[1..MaxSize, 1..MaxSize] of integer;

Color: array[1..MaxSize] of integer;

Ribs: array[1..MaxSize] of record

a, b: integer;

end;

n, a, b, k, col, i, len: integer;

Procedure Init;

Var f: text;

i, j: integer;

Begin

Assign(f, 'INPUT.MTR');

Reset(f);

Readln(f, n);

For i:=1 to n do

Begin

For j:=1 to n do read(f, matrix[i, j]);

Readln(f)

End;

For i:=1 to n do color[i]:=i;

len:=0

End;

Procedure Findmin(var a, b: integer);

Var min, i, j: integer;

Begin

min:=infinity;

For i:=1 to n-1 do

For j:=i+1 to n do

If (Matrix[i, j]<min) and (color[i]<>color[j]) then

Begin

min:=Matrix[i, j];

a:=i;

b:=j

End;

len:=len+min

end;

Begin

Clrscr;

Init;

For k:=1 to n-1 do

Begin

Findmin(a, b);

Ribs[k].a:=a;

Ribs[k].b:=b;

col:=Color[b];

For i:=1 to n do

If color[i]=col then color[i]:=color[a];

End;

For i:=1 to n-1 do

Writeln(ribs[i].a, ' –', ribs[i].b);

Writeln('Length= ', len);

Readkey

End.

Äëÿ òàêîãî âõîäíîãî ôàéëà

8

0 23 12 1000 1000 1000 1000 1000

23 0 25 1000 22 1000 1000 35

12 25 0 18 1000 1000 1000 1000

1000 1000 18 0 1000 20 1000 1000

1000 22 1000 1000 0 23 14 1000

1000 1000 1000 20 23 0 24 1000

1000 1000 1000 1000 14 24 0 16

1000 35 1000 1000 1000 1000 16 0

ïðîãðàììà íàïå÷àòàåò:

1–3

5–7

7–8

3–4

4–6

2–5

1–2

Length= 125.

Àëãîðèòì Äåéêñòðû.

Äàíà äîðîæíàÿ ñåòü, ãäå ãîðîäà è ðàçâèëêè áóäóò âåðøèíàìè, à äîðîãè – ðåáðàìè. Òðåáóåòñÿ íàéòè êðàò÷àéøèé ïóòü ìåæäó äâóìÿ âåðøèíàìè.

Ìîæíî ïðåäëîæèòü ìíîãî ïðîöåäóð ðåøåíèÿ ýòîé çàäà÷è, íàïðèìåð, ôèçè÷åñêîå ìîäåëèðîâàíèå òàêîãî ðîäà: íà ïëîñêîé äîñêå ðèñóåòñÿ êàðòà ìåñòíîñòè, â ãîðîäà è â ðàçâèëêè âáèâàþòñÿ ãâîçäè, íà êàæäûé ãâîçäü íàäåâàåòñÿ êîëüöî, äîðîãè óêëàäûâàþòñÿ âåðåâêàìè, êîòîðûå ïðèâÿçûâàþòñÿ ê ñîîòâåòñòâóþùèì êîëüöàì. ×òîáû íàéòè êðàò÷àéøåå ðàññòîÿíèå ìåæäó êîëüöîì i è êîëüöîì k, íóæíî âçÿòü i â îäíó ðóêó, âçÿòü k â äðóãóþ è ðàñòÿíóòü. Òå âåðåâêè, êîòîðûå íàòÿíóòñÿ è íå äàäóò ðàçâîäèòü øèðå, è îáðàçóþò êðàò÷àéøèé ïóòü ìåæäó i è k. Îäíàêî, ìàòåìàòè÷åñêàÿ ïðîöåäóðà, êîòîðàÿ ïðîìîäåëèðóåò ýòó ôèçè÷åñêóþ, âûãëÿäèò î÷åíü ñëîæíî. Èçâåñòíû àëãîðèòìû ïîïðîùå, íàïðèìåð, ïðåäëîæåííûé Äåéêñòðîé åùå â 1959 ã. Ýòîò àëãîðèòì ðåøàåò áîëåå îáùóþ çàäà÷ó:

 îðèåíòèðîâàííîé, íåîðèåíòèðîâàííîé èëè ñìåøàííîé ñåòè íàéòè êðàò÷àéøèé ïóòü èç çàäàííîé âåðøèíû âî âñå îñòàëüíûå âåðøèíû.

Àëãîðèòì èñïîëüçóåò òðè ìàññèâà èç n ÷èñåë êàæäûé. Ïåðâûé ìàññèâ Visited ñîäåðæèò ìåòêè ñ äâóìÿ çíà÷åíèÿìè: False (âåðøèíà åùå íå ðàññìîòðåíà) è True (âåðøèíà óæå ðàññìîòðåíà); âòîðîé ìàññèâ Len ñîäåðæèò ðàññòîÿíèÿ îò – òåêóùèå êðàò÷àéøèå ðàññòîÿíèÿ îò íà÷àëüíîé äî ñîîòâåòñòâóþùåé âåðøèíû; òðåòèé ìàññèâ C ñîäåðæèò íîìåðà âåðøèí – k-ûé ýëåìåíò C åñòü íîìåð ïðåäïîñëåäíåé âåðøèíû íà òåêóùåì êðàò÷àéøåì ïóòè èç íà÷àëüíîé âåðøèíû â k-þ. Èñïîëüçóåòñÿ òàêæå Matrix – ìàòðèöà ðàññòîÿíèé.

Îïèøåì àëãîðèòì Äåéêñòðû:

1 (èíèöèàëèçàöèÿ).  öèêëå îò 1 äî n çàïîëíèòü çíà÷åíèåì False ìàññèâ Visited; çàïîëíèòü ÷èñëîì i ìàññèâ C (i – íîìåð ñòàðòîâîé âåðøèíû); ïåðåíåñòè i-þ ñòðîêó ìàòðèöû Matrix â ìàññèâ Len;

Visited[i]:=True; C[i]:=0;

2 (îáùèé øàã). Íàéòè ìèíèìóì ñðåäè íåîòìå÷åííûõ (ò.å. òåõ ê, äëÿ êîòîðûõ Visitid[k]=False); ïóñòü ìèíèìóì äîñòèãàåòñÿ íà èíäåêñå j, ò.å. Len[j]£Len[k];

Çàòåì âûïîëíÿòü ñëåäóþùèå îïåðàöèè:

Visited[i]:=True;

åñëè Len[k]>Len[j]+Matrix[j, k], òî (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j)

z:=C[k];

Âûäàòü z

z:=C[z]. Åñëè z =0, òî êîíåö,

èíà÷å ïåðåéòè ê 3.2.

Òåîðåìà. Àëãîðèòì Äåéêñòðû – êîððåêòåí.

Uses Crt;

Const MaxSize=10;

Infinity=1000;

Var Mattr: array [1..MaxSize, 1..MaxSize] of integer;

Visited: array [1..MaxSize] of boolean;

Len,Path: array [1..MaxSize] of integer;

n, Start, Finish, k, i: integer;

Procedure Init;

Var f: text;

i, j: integer;

Begin

Assign(f, INPUT.MTR');

Reset(f);

Readln(f, n);

For i:=1 to n do

Begin

For j:=1 to n do Read(f, mattr[i,j]);

Readln(f)

End;

Write('Íà÷àëüíàÿ âåðøèíà: '); Readln(Start);

For i:=1 to n do

Begin

Visited[i]:=False;

Len[i]:=Mattr[Start, i];

Path[i]:=Start

End;

Path[Start]:=0;

Visited[Start]:=True

End;

Function Possible: Boolean;

Var i: integer;

Begin

Possible:=True;

For i:=1 to n do If not Visited[i] then Exit;

Possible:=False

End;

Function Min: Integer;

Var i, minvalue, currentmin: integer;

Begin

Minvalue:=Infinity;

For i:=1 to n do

If not Visited[i] then

If Len[i]<minvalue then

Begin

currentmin:=i;

minvalue:=Len[i]

End;

min:=currentmin

End;

Begin

ClrScr;

Init;

While Possible do

Begin

k:=min;

Visited[k]:=True;

For i:=1 to n do

If Len[i]>Len[k]+Mattr[i, k] then

Begin

Len[i]:=Len[k]+Mattr[i, k];

Path[i]:=k

End

End;

Write('Êîíå÷íàÿ âåðøèíà: '); Readln(Finish);

Write(Finish);

Finish:=Path[Finish];

While Finish<>0 do

Begin

Write('<-', Finish);

Finish:=Path[Finish];

End;

ReadKey

End.

Íàïðèìåð, äëÿ ñåòè, îïèñàííîé â ïðåäûäóùåé ãëàâå, êðàò÷àéøèé ïóòü èç 3-åé âåðøèíû â 8-þ áóäåò: 8¬


Èíôîðìàöèÿ î ðàáîòå «Aëãîðèòìû íà ãðàôàõ»
Ðàçäåë: Èíôîðìàòèêà, ïðîãðàììèðîâàíèå
Êîëè÷åñòâî çíàêîâ ñ ïðîáåëàìè: 20554
Êîëè÷åñòâî òàáëèö: 0
Êîëè÷åñòâî èçîáðàæåíèé: 0

0 êîììåíòàðèåâ


Íàâåðõ