Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 48 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

48
7. L(v
2,
v
5
)=6, λ
'
5
=8+6=14< λ
5
=∞,
8. L(v
3,
v
4
)=2, λ
'
4
=9+2=11= λ
4
=11,
9. L(v
3,
v
5
)=4, λ
'
5
=9+4=13 < λ
5
=14, îñòàåòñÿ λ
5
=13;
10. L(v
3,
v
6
)=16, λ
'
6
=9+16=25 < λ
6
=∞,
11. L(v
4,
v
6
)=8, λ
'
6
=11+8=19 < λ
6
=25,
12. L(v
5,
v
3
)=2, λ
'
3
=13+2=15 > λ
3
=9,
13. L(v
5,
v
6
)=6, λ
'
6
=13+6=19, îñòàåòñÿ λ
6
=19.
Ýòàï 2 (îáðàòíûé õîä) îïðåäåëåíèå ìèíèìàëüíîãî ïóòè.
Èç âåðøèíû v
6
íàõîäèì:
1. λ
6
L(v
4,
v
6
)=198=11=λ
4
,
λ
4
 L(v
1,
v
4
)=114=7=λ
1
,
λ
1
 L(v
0,
v
1
)=77=0=λ
0
,
çíà÷èò, ïóòü
µ
=( v
0,
v
1
, v
4,
v
6
)  ìèíèìàëüíûé.
2. λ
6
 L(v
3,
v
6
)=1916=3<λ
3
=9,
çíà÷èò, äóãà (v
3,
v
6
) íå âõîäèò â ìèíèìàëüíûé ïóòü.
3. λ
6
 L(v
5,
v
6
)=196=13=λ
5
,
λ
5
 L(v
3,
v
5
)=134=9=λ
3
,
λ
3
 L(v
0,
v
3
)=99=0=λ
0
,
çíà÷èò, ïóòü
µ
= ( v
0,
v
3
, v
5,
v
6
)  ìèíèìàëüíûé.
4. Òàê æå ìîæíî äîêàçàòü, ÷òî ïóòü µ=( v
0,
v
3
, v
4,
v
6
)  ìèíèìàëüíûé.
3.1.2. Îáîñíîâàíèå àëãîðèòìà Ôîðäà
Äîêàæåì, ÷òî ïîñëå êîíå÷íîãî ÷èñëà ïðèìåíåíèé ïðàâèëà 3 äëÿ êàæ-
äîé äóãè ãðàôà ñòàíåò ñïðàâåäëèâûì íåðàâåíñòâî
λ
j
λ
i
≤ L(v
i
,v
j
) (ïðàâèëî 4).
Íà ëþáîì øàãå èçìåíåíèÿ ìåòêà λ
j
>0 ïðè j≠0 (ìåòêà λ
0
=0), ÷òî ìîæ-
íî äîêàçàòü ïî èíäóêöèè.
1. Äåéñòâèòåëüíî, ïðè ïåðâîì ïðèìåíåíèè ïðàâèëà 3 áóäåò èçìåíå-
íà ìåòêà λ
k
ó îäíîé èç âåðøèí v
k
, ñìåæíûõ ñ âåðøèíîé v
0
(v
k
∈Ãv
0
). Ýòà
âåðøèíà v
k
ïîëó÷èò íîâóþ ìåòêó λ
k
= L(v
0
,v
k
)>0, íàïðèìåð v
4
[15].
Ïðåäïîëîæèì, ÷òî ïîñëå ïðèìåíåíèÿ ïðàâèëà 3 m ðàç (m>1), ñòàíåò
ñïðàâåäëèâûì óòâåðæäåíèå, ÷òî λ
0
=0, λ
i
>0 äëÿ i>0. Íà m+1-ì øàãå êà-
êàÿ-òî âåðøèíà v
j
ïîëó÷èò íîâóþ ìåòêó λ
j
= λ
i
+ L(v
i
,v
j
). Íî â ñèëó
ïðåäïîëîæåíèÿ èíäóêöèè λ
i
≥ 0, êðîìå òîãî, L(v
i
,v
j
)>0, ïîýòîìó λ
j
>0.

Страницы