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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

l(v
1
) := 0;
j := 2 n
v
∗
i
∈Γ
−
(v
j
), l(v
∗
i
)+c
i,j
;
l(v
j
) := l(v
∗
i
)+c
∗
i,j
;
pred(v
j
) := v
∗
i
;
{l(v
n
)}
v := v
n
v6=v
1
½
v → ;
v := pred(v);
{v
1
}
O(m),
O(n),
   Â ôîðìàëèçîâàííîé çàïèñè (ñ èñïîëüçîâàíèåì ðàíåå ââå-
äåííûõ îáîçíà÷åíèé) ðàññìîòðåííûé àëãîðèòì âûãëÿäèò òàê:
begin         {  Àëãîðèòì ïîèñêà êðàò÷àéøåãî  }
               {  ïóòè â àöèêëè÷åñêîì îðãðàôå  }
  l(v1 ) := 0;
  forj := 2 to n do
      Íàéòè vi∗ ∈Γ− (vj ), äëÿ êîòîðîé l(vi∗ )+ci,j ìèíèìàëüíî;
          l(vj ) := l(vi∗ )+c∗i,j ;
      pred(v ) := v ∗ ;
                  j        i
  output{l(vn )};
  v := vn ;
  while
     ½ v6=v1 do
          v → ñòåê;
          v := pred(v);
  output{v1 , ñîäåðæèìîå ñòåêà};
               {  Àëãîðèòì ïîèñêà êðàò÷àéøåãî  }
end.          {  ïóòè â àöèêëè÷åñêîì îðãðàôå  }
   Î÷åâèäíî, ÷òî òðóäîåìêîñòü ïåðâîãî ýòàïà ðàâíà O(m),
ïîñêîëüêó íåîáõîäèìî ïðîñìîòðåòü âñå ðåáðà, à òðóäîåìêîñòü
âòîðîãî  O(n), òàê êàê, â õóäøåì ñëó÷àå, êðàò÷àéøèé ïóòü
ìîæåò âêëþ÷àòü âñå âåðøèíû ãðàôà.
   Êðèòè÷åñêèé ïóòü. Àöèêëè÷åñêèå îðãðàôû ÿâëÿþòñÿ
íàãëÿäíûì ñðåäñòâîì îòîáðàæåíèÿ âçàèìîñâÿçåé è ïîðÿäêà
ñëåäîâàíèÿ ýòàïîâ ñëîæíûõ äîëãîâðåìåííûõ ïðîåêòîâ, òàêèõ
êàê ñòðîèòåëüñòâî êðóïíûõ ñîîðóæåíèé, ïðîâåäåíèå øèðîêî-
ìàñøòàáíûõ íàó÷íî-èññëåäîâàòåëüñêèõ ðàáîò è ò. ï.
   Ïóñòü êàæäàÿ äóãà ãðàôà îòîáðàæàåò îïðåäåëåííóþ ðàáî-
òó ïðè âûïîëíåíèè íåêîòîðîãî ïðîåêòà, à âåñ äóãè óêàçûâàåò
ïðîäîëæèòåëüíîñòü ýòîé ðàáîòû. Òîãäà âåðøèíû ãðàôà ìîæ-
íî ðàññìàòðèâàòü êàê ñîáûòèÿ, ñîñòîÿùèå â çàâåðøåíèè îäíèõ
ðàáîò (âõîäÿùèå äóãè) è íà÷àëå äðóãèõ (èñõîäÿùèå äóãè). Ïðè
ýòîì ïðåäïîëàãàåòñÿ, ÷òî íè îäíà "èñõîäÿùàÿ" ðàáîòà íå ìî-
æåò íà÷àòüñÿ, ïîêà íå áóäóò çàâåðøåíû âñå "âõîäÿùèå".
   Ïðè òàêîé èíòåðïðåòàöèè ãðàô íà ðèñ. 4.13 âïîëíå ìî-
æåò ðàññìàòðèâàòüñÿ êàê ñåòåâîé ãðàôèê íåêîòîðîãî ïðîåêòà.
Ïðè ýòîì åñòåñòâåííî âîçíèêàåò çàäà÷à îïðåäåëåíèÿ íàèáîëåå
ðàííèõ ñðîêîâ åãî çàâåðøåíèÿ. ßñíî, ÷òî ìèíèìàëüíîå âðåìÿ


                               96

Страницы