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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(v
5
, v
2
, v
1
),
v
1
v
1
,
Γ(v
1
)={v
4
, v
5
, v
7
}
s
v
1
∗
s
v
2
s
v
3
s
v
4
(18)
s
v
5
s
v
6
s
v
7
s
v
8
???
-
-
-
@
@
@
@
@R
@
@
@
@
@R
@
@
@
@
@R
6
-
-
-
@
@
@
@
@R
?
R
?
v
1
l(v
1
)+c(v
1
, v
4
)<l(v
4
),
v
4
v
5
v
7
,
l(v
1
)+c(v
1
, v
7
)=25.
d(v
4
)=18.
v
4
v
1
,
v
1
(v
1
, v
4
)
(v
5
, v
2
, v
1
, v
4
),
p l(p)
÷èò, ÷òî âûÿâëåí êðàò÷àéøèé ïóòü (v5 , v2 , v1 ), à ìåòêà âåðøè-
íû v1 ñòàíîâèòñÿ ïîñòîÿííîé. Ïîñëåäóþùèå äåéñòâèÿ âûïîë-
íÿþòñÿ àíàëîãè÷íî. Äëÿ v1 , êàê ïîñëåäíåé ïîñòîÿííî ïîìå-
÷åííîé, íàõîäèì ìíîæåñòâî âåðøèí Γ(v1 )={v4 , v5 , v7 } è àíàëè-
                                              çèðóåì èõ ìåòêè, ïðèíèìàÿ âî
                  ∗
              15              5         12    âíèìàíèå äëèíû äóã, ñâÿçûâà-
             v1              v2        v3     þùèõ v1 ñ ýòèìè âåðøèíàìè.
              s              s      -s
              @ 19           @6              Òàê êàê l(v1 )+c(v1 , v4 )

Страницы