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

UptoLike

ВУЗ: 

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

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

Рубрика: 

47
Îáðàòíûé õîä.
5. Â ìíîæåñòâå Ã
1
v
n
íàéòè òàêóþ âåðøèíó
1
p
v
, ÷òî
λ
n
= λ
p
1
+ L(v
p
1
, v
n
) èëè λ
n
λ
p
1
= L(v
p
1
, v
n
).
Àíàëîãè÷íî, â ìíîæåñòâå Ã
1
v
p
1
íàéòè òàêóþ âåðøèíó v
p
2
, ÷òîáû áûëî
ñïðàâåäëèâî ðàâåíñòâî
λ
p
1
= λ
p
2
+ L(v
p
2
,v
p
1
) èëè λ
p
1
λ
p
2
= L(v
p
2
,v
p
1
) è ò. ä.
Ïîñëå íåêîòîðîãî ÷èñëà øàãîâ âåðøèíà v
p
k
ñîâïàäåò ñ âåðøèíîé v
0
.
Ïóòü µ = ( v
0
=v
p
k
,v
p
k1
, ... ,v
p
2
, v
p
1
, v
n
) ìèíèìàëüíûé è åãî äëèíà
L(µ) = λ
n
.
Ïðèìåð
Ïðîèëëþñòðèðóåì ðàáîòó àëãîðèòìà ïîèñêà ìèíèìàëüíîãî ïóòè äëÿ
ãðàôà íà ðèñ. 3.2.
Ýòàï 1 (ïðÿìîé õîä) âû÷èñëåíèå íîâûõ ìåòîê ïðè âåðøèíàõ.
Ïðèïèñûâàåì âåðøèíå v
0
ìåòêó 0, à îñòàëüíûì âåðøèíàì  ìåòêó ∞.
Íàõîäèì íîâûå ìåòêè, êîòîðûå ïîêàçàíû â êâàäðàòíûõ ñêîáêàõ ïðè âåð-
øèíàõ ãðàôà:
1. L(v
0,
v
1
)=7, λ
'
1
=0+7< λ
1
=∞, îñòàåòñÿ λ
1
=7;
2. L(v
0,
v
2
)=8, λ
'
2
=0+8< λ
2
=∞, îñòàåòñÿ λ
2
=8;
3. L(v
0,
v
3
)=9, λ
'
3
=0+9< λ
3
=∞, îñòàåòñÿ λ
3
=9;
4. L(v
0,
v
4
)=15, λ
'
4
=0+15< λ
4
=∞;
5. L(v
1,
v
4
)=4, λ
'
4
=7+4=11< λ
4
=15, îñòàåòñÿ λ
4
=11;
6. L(v
2,
v
3
)=3, λ
'
3
=8+3=11 > λ
3
=9;
Ðèñ. 3.2. Îðãðàô ñ äëèíàìè äóã è ìåòêàìè âåðøèí
v
$
[
∞
,25,19]
4
2
2
43
4
v
"
[
∞
,15,11]v
[
∞
,7]
v
[0]
v
[
∞
,8] v
#
[
∞
,14,13]
6
8
6
8
7
7
5
9
v
!
[
∞
,9]
15
16

Страницы