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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

s
v
11
s
v
12
s
v
13
s
v
9
s
v
8
s
v
4
s
v
10
s
v
5
s
v
6
s
v
2
s
v
7
s
v
3
s
v
1
-
-
-
@
@
@
@I 6
@
@
@
@I
-
6
6 6
@
@
@
@I 6
-
6
6
@
@
@
@I
6
l(v
1
)=0,
v
1
, v
3
, v
5
, v
2
, v
7
, v
4
, v
10
, v
6
, v
8
, v
9
, v
11
, v
12
, v
13
.
v
13
v
13
,
v
10
v
11
v
12
l(v
13
)−l(v
i
)=c
i,13
, v
i
∈{v
10
,
v
11
, v
12
}. v
12
.
v
4
v
8
v
11
v
8
.
àöèêëè÷åñêîì ãðàôå, èçîáðàæåííîì íà ðèñ. 4.13. Íåòðóäíî
óáåäèòüñÿ, ÷òî íóìåðàöèÿ âåðøèí ãðàôà ÿâëÿåòñÿ "ïðàâèëü-
íîé" â óêàçàííîì âûøå ñìûñëå.
                                    12
                                     -
                 vs11              -vs12            -vs13
                  6 I
                    @          19     6I
                                       @      14      6
                      @ 15             17@ 21          8
                         @                @
                           @vs 9     sv8    @vs4   - sv10
                                  13 6         6 18 6
                              6      I
                                       @
                    30       3        11@ 8 14        30
                                         @
                       26 sv5         v6
                                      s     @sv2   - sv7
                         @    I     6 16       9
                        11 @ 19 7          5
                                  @
                  s          10    @s
                 v3                   v1
                                 Ðèñ. 4.13

     Ïðîöåññ âû÷èñëåíèé ìîæíî âûïîëíèòü íåïîñðåäñòâåííî
ïî ðèñóíêó, ïðèíÿâ l(v1 )=0, è äàëåå ïåðåõîäÿ îò âåðøèíû
ê âåðøèíå. Ïðè ýòîì ñîâñåì íå îáÿçàòåëüíî ñîáëþäàòü î÷å-
ðåäíîñòü îáðàáîòêè âåðøèí ñòðîãî â ñîîòâåòñòâèè ñ èõ íóìå-
ðàöèåé. Äëÿ äàííîãî ãðàôà âïîëíå äîïóñòèì, íàïðèìåð, è òà-
êîé ïîðÿäîê: v1 , v3 , v5 , v2 , v7 , v4 , v10 , v6 , v8 , v9 , v11 , v12 , v13 . Âàæ-
íî òîëüêî, ÷òîáû ê ìîìåíòó îáðàáîòêè î÷åðåäíîé âåðøèíû
âñå åå "ïðåäøåñòâåííèöû" áûëè îáðàáîòàíû. Òîãäà â ëþáîì
ñëó÷àå ðåçóëüòàò (çíà÷åíèÿ ïîìåòîê âåðøèí) áóäåò òàêèì, êàê
ïîêàçàíî íà ðèñ. 4.14,à, ïðè÷åì ïîìåòêà v13 ðàâíà 44.
     Äëÿ ïîëó÷åíèÿ òðàññû êðàò÷àéøåãî ïóòè ñëåäóåò âûïîë-
íèòü ïðîöåäóðó "îáðàòíîãî õîäà". Ñïåðâà îòûñêèâàåòñÿ ïðåä-
øåñòâåííèöà äëÿ v13 , ëåæàùàÿ íà èñêîìîì êðàò÷àéøåì ïóòè.
Ýòî îäíà èç òðåõ âåðøèí v10 , v11 , v12 , à èìåííî òà, äëÿ êîòî-
ðîé âûïîëíÿåòñÿ ñîîòíîøåíèå l(v13 )−l(vi )=ci,13 , ãäå vi ∈{v10 ,
v11 , v12 }. Òàêîé âåðøèíîé ÿâëÿåòñÿ v12 . Äëÿ íåå òàêæå èùåò-
ñÿ âåðøèíà-ïðåäøåñòâåííèöà, ëåæàùàÿ íà êðàò÷àéøåì ïóòè.
Èç òðåõ âîçìîæíûõ v4 , v8 è v11 òàêîâîé îêàçûâàåòñÿ v8 . Â



                                         93

Страницы