Составители:
Рубрика:
49
2. Íåòðóäíî çàìåòèòü, ÷òî ïðè êàæäîì èçìåíåíèè ìåòêà âåðøèíû
ãðàôà óìåíüøàåòñÿ íà ïîëîæèòåëüíóþ âåëè÷èíó, íå ìåíüøóþ, ÷åì ìè-
íèìàëüíàÿ ðàçíîñòü äëèí ïóòåé ãðàôà.
Èç ýòèõ äâóõ óòâåðæäåíèé ñëåäóåò, ÷òî ìåòêà ëþáîé âåðøèíû ãðàôà
ìîæåò èçìåíÿòüñÿ ëèøü êîíå÷íîå ÷èñëî ðàç. Òàê êàê âåðøèí êîíå÷íîå
ìíîæåñòâî, òî ïðàâèëî 3 ìîæåò ïðèìåíÿòüñÿ ëèøü êîíå÷íîå ÷èñëî ðàç.
Ðàññìîòðèì îáðàòíûé ýòàï è ïîêàæåì, ÷òî, ïðèìåíÿÿ ïðàâèëî 5, ìû
ìîæåì íàéòè ìèíèìàëüíûå ïóòè.
Äåéñòâèòåëüíî, òàê êàê â ðåçóëüòàòå ïðèìåíåíèÿ ïðàâèëà 3 ìåòêà λ
n
ìîíîòîííî óìåíüøàåòñÿ, òî ìû ïðèäåì ê òàêîé âåðøèíå v
p
1
(ýòî íà÷àëî
äóãè, ñ ïîìîùüþ êîòîðîé â ïîñëåäíèé ðàç óìåíüøèëàñü ìåòêà λ
n
), ÷òî
λ
n
λ
p
1
= L(v
p
1
, v
n
), íàïðèìåð λ
6
λ
4
= L(v
4
, v
6
).
Ïî ýòîé æå ïðè÷èíå íàéäåòñÿ âåðøèíà v
p
2
,
äëÿ êîòîðîé ñîáëþäàåòñÿ
ñîîòâåòñòâèå
λ
p
1
λ
p
2
= L(v
p
2
,v
p
1
) è ò. ä.
Ïî óñëîâèþ çàäà÷è äëèíà äóãè ãðàôà L(v
i
, v
j
)>0, ïîýòîìó ìåòêè λ
n
,
λ
p
1
, λ
p
2
, ... îáðàçóþò ñòðîãî óáûâàþùóþ ïîñëåäîâàòåëüíîñòü íåîòðèöà-
òåëüíûõ ÷èñåë, îòëè÷àþùèõñÿ äðóã îò äðóãà íà âåëè÷èíó, áîëüøóþ èëè
ðàâíóþ äëèíå êðàò÷àéøåé äóãè ãðàôà. Ñëåäîâàòåëüíî, ïðè íåêîòîðîì k
ïîëó÷èì λ
p
k
= 0, v
p
k
= v
0
. (Âåðøèíà v
0
âûäåëåíà òåì, ÷òî åé â ñèëó ïðàâè-
ëà 1 ñ ñàìîãî íà÷àëà ïðèñâîåíà ìåòêà λ
0
=0 è â ôîðìèðîâàíèè ýòîé
ìåòêè íå ó÷àñòâóþò äóãè ãðàôà).
Ïîêàæåì, ÷òî µ = ( v
0
=v
p
k
,v
p
k1
, ... ,v
p
2
, v
p
1
, v
n
) ìèíèìàëüíûé ïóòü ñî
çíà÷åíèåì äëèíû ïóòè L(µ)=λ
n
, ò. å. çíà÷åíèå L( v
0,
v
i
1
, v
i
2
,,v
i
m
, v
n
) ëþ-
áîãî äðóãîãî ïóòè ìåæäó v
0
è v
n
íå ìåíüøå λ
n
.
Èìååì íåðàâåíñòâà (ïî ïðàâèëó 4):
λ
i
1
λ
0
≤ L(v
0
, v
i
1
),
+
λ
i
2
λ
i
1
≤ L(v
i
1
,v
i
2
),
..,
+
λ
n
λ
i
m
≤ L(v
i
m
, v
n
).
Ñêëàäûâàÿ ýòè íåðàâåíñòâà, ïîëó÷èì (ïðè λ
0
=0)
λ
n
≤ L( v
0,
v
i
1
, v
i
2
,,v
i
m
,
v
n
).
Страницы
- « первая
- ‹ предыдущая
- …
- 47
- 48
- 49
- 50
- 51
- …
- следующая ›
- последняя »
