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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v
2
v
1
.
(v
1
, v
2
, v
8
, v
12
, v
13
).
v
13
v
12
,
v
8
,
C
(v
i
, v
j
) i<j.
∞.
c
ii
=l(v
i
).
c
3,9
=26, c
5,9
=3 c
8,9
=13.
v
9
,
l(v
3
)=10, l(v
5
)=19 l(v
8
)=13.
min[26+10; 3+19; 13+13]=21,
v
9
v
5
,
c
5,9
.
c
3,3
c
5,5
c
8,8
ñâîþ î÷åðåäü, ýòîé âåðøèíå ïðåäøåñòâóåò v2 , à åé  v1 . Çà-
ïèñûâàÿ íàéäåííóþ ïîñëåäîâàòåëüíîñòü â îáðàòíîì ïîðÿäêå,
ïîëó÷àåì ñîáñòâåííî ñàì êðàò÷àéøèé ïóòü (v1 , v2 , v8 , v12 , v13 ).
Íà ðèñ. 4.14,à ñîñòàâëÿþùèå åãî äóãè èçîáðàæåíû æèðíûìè
ëèíèÿìè.
     Ïðîöåññ îáðàòíîãî õîäà ìîæíî óïðîñòèòü, åñëè ó÷åñòü, ÷òî
âåðøèíà v13 ïîëó÷èëà ñâîþ ïîìåòêó èç v12 , êîòîðàÿ, â ñâîþ
î÷åðåäü, ïîëó÷èëà ïîìåòêó èç v8 , è ò. ä. Ïîýòîìó íà ýòàïå
ïðÿìîãî õîäà öåëåñîîáðàçíî íàðÿäó ñ ïðèñâîåíèåì ïîìåòêè
î÷åðåäíîé âåðøèíå äîïîëíèòåëüíî îòìå÷àòü è òó âåðøèíó, èç
êîòîðîé ýòà ïîìåòêà ïîëó÷åíà. Òîãäà íà ýòàïå îáðàòíîãî õîäà
îñòàåòñÿ òîëüêî ïðîéòè îò ñòîêà ê èñòîêó, äâèãàÿñü ëèøü ïî
ýòèì äîïîëíèòåëüíî îòìå÷åííûì âåðøèíàì.
     Çàäà÷ó ìîæíî ðåøàòü è íå ïðèáåãàÿ ê èçîáðàæåíèþ ãðà-
ôà. Òåõíèêà ïîëó÷åíèÿ ïîìåòîê âåðøèí íåïîñðåäñòâåííî ïî
ìàòðèöå âåñîâ C äàíà íà ðèñ. 4.14,á. Êàê è ðàíåå, âåðøè-
íû äîëæíû áûòü ïðîíóìåðîâàíû òàê, ÷òîáû äëÿ ëþáîé äóãè
(vi , vj ) âûïîëíÿëîñü îòíîøåíèå i

Страницы