Элементы теории графов. Домнин Л.Н. - 81 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

F r
1
F r
2
v∈V l(v):=∞
l(s) := 0 F r
1
:= adj s
v∈F r
1
l(v) := 1
l(t)=∞ t
F r
2
:= ∅;
v∈F r
1
w∈ adj v
l(w)=∞
½
l(w) := l(v)+1;
F r
2
:= F r
2
+{w};
F r
1
:= F r
2
r
G.
{v
i
, v
j
}
c
i,j
/r
G
0
G. G
0
G
0
.
G
1
r
P
{v
i
,v
j
}∈E
c
i,j
−m.
   Ïóñòü F r1  ìíîæåñòâî êëåòîê (âåðøèí ãðàôà), îáðàçóþ-
ùèõ ôðîíò âîëíû íà òåêóùåé èòåðàöèè; F r2  ôðîíò âîëíû
íà ñëåäóþùåé èòåðàöèè. Òîãäà ôîðìàëèçîâàííîå îïèñàíèå àë-
ãîðèòìà èìååò âèä:
begin   {ÂÎËÍÎÂÎÉ ÀËÃÎÐÈÒÌ}
  for v∈V do l(v):=∞ ; {Ïîìåòèòü âñå âåðøèíû êàê ñâîáîäíûå}
   l(s) := 0 ; F r1 := adj s ; {Ñôîðìèðîâàòü íà÷àëüíûé ôðîíò è}
  for v∈F r1 do l(v) := 1 ; {ïîìåòèòü åãî âåðøèíû åäèíèöàìè.}
  while
     
           l(t)=∞ do {Ïîêà ôðîíò âîëíû íå äîñòèã âåðøèíû t }
        F r2 := ∅;
        for
            v∈F r1 do
     
                           {äëÿ êàæäîé âåðøèíû òåêóùåãî ôðîíòà}
     
     
              for w∈ adj v do {ïðîâåðèòü âñå ñîñåäíèå âåðøèíû}
      
               
             if l(w)=∞
                                        {è åñëè íàéäåòñÿ ñâîáîäíàÿ}
                  then
     
                     ½
     
          
                       l(w) := l(v)+1;       {âêëþ÷èòü åå âî âíîâü}
     
          
               
     
                       F r2 := F r2 +{w};    {ôîðìèðóåìûé ôðîíò.}
     
         F r1 := F r2
end.       {ÂÎËÍÎÂÎÉ ÀËÃÎÐÈÒÌ}


   4.4.2. Ãðàôû ñî âçâåøåííûìè äóãàìè (ðåáðàìè)
      Êðàò÷àéøèå ïóòè è â ýòîì ñëó÷àå ìîæíî íàõîäèòü ñ ïî-
ìîùüþ âîëíîâîãî àëãîðèòìà. Ïóñòü r  íàèáîëüøèé îáùèé
äåëèòåëü âåñîâ ðåáåð (äóã) ãðàôà G. Ïðåîáðàçóåì ãðàô, çà-
ìåíèâ êàæäîå èç ðåáåð {vi , vj } ïðîñòîé öåïüþ, ñîñòîÿùåé èç
ci,j /r ðåáåð åäèíè÷íîé äëèíû. ßñíî, ÷òî â ïîëó÷åííîì ïðè
ýòîì ãðàôå G0 ïîëíîñòüþ ñîõðàíÿòñÿ ìåòðè÷åñêèå ñîîòíîøå-
íèÿ, õàðàêòåðèçóþùèå ðàññòîÿíèÿ ìåæäó âåðøèíàìè ãðàôà
G. Âìåñòå ñ òåì G0  ýòî ãðàô ñ ðåáðàìè (äóãàìè) åäèíè÷-
íîé äëèíû, äëÿ êîòîðîãî çàäà÷à ðåøàåòñÿ ïî îïèñàííîé âû-
øå ñõåìå. Î÷åâèäíûé íåäîñòàòîê òàêîãî ïîäõîäà  âûñîêàÿ
òðóäîåìêîñòü èç-çà áîëüøîé ðàçìåðíîñòè ãðàôà G0 . Äåéñòâè-
òåëüíî ÷èñëî âåðøèí (è ðåáåð) âPïîñëåäíåì áîëüøå, ÷åì â
ãðàôå G íà âåëè÷èíó, ðàâíóþ 1r ci,j −m. Ïîýòîìó èñïîëü-
                                     {vi ,vj }∈E
çóþò áîëåå ýôôåêòèâíûå àëãîðèòìû ðåøåíèÿ çàäà÷è. Äâà èç
íèõ  àëãîðèòìû Äåéêñòðû è Ôëîéäà ðàññìîòðåíû íèæå.


                                81

Страницы