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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

c
i,j
=1.
s. v∈Γ(s)
v∈Γ
2
(s)
v∈Γ
3
(s)
i v∈Γ
i
(s) l(v)=i.
t.
v
5
v
7
s
v
1
(1)
s
v
2
(2)
s
v
3
(4)
s
v
4
(5)
s
v
5
(0)
s
v
6
(3)
s
v
7
(6)
s
v
8
(3)
s
v
9
(2)
s
v
10
(5)
s
v
11
(4)
@
@
@
@
@
@
6
A
A
A
A
A
A-
6
g
g
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
1
1 1 1
v
2
1 1
v
3
1 1 1
v
4
1 1 1 1
v
5
1
v
6
1 1 1
v
7
1 1
v
8
1 1 1
v
9
1 1 1
v
10
1 1 1
v
11
1 1
l(v
i
) 1 2 4 5 0 3 6 3 2 5 4
l(v
i
)
v
5
l(v
1
)=1.
     4.4.1. Ãðàôû ñ äóãàìè åäèíè÷íîé äëèíû
   Ðàññìîòðèì ñëó÷àé, êîãäà âåñà âñåõ äóã (ðåáåð) ãðàôà îäè-
íàêîâû. Íå íàðóøàÿ îáùíîñòè, ìîæíî ñ÷èòàòü, ÷òî äëÿ ëþáîé
äóãè (ðåáðà) ci,j =1. Ýôôåêòèâíîå ðåøåíèå çàäà÷è ïîëó÷àåòñÿ
ñ ïîìîùüþ ïðîñòîé ïðîöåäóðû, â ðåçóëüòàòå êîòîðîé êàæäàÿ
îáðàáîòàííàÿ âåðøèíà ïîëó÷àåò ïîìåòêó, ðàâíóþ ðàññòîÿíèþ
îò s. Ïðîöåññ íà÷èíàåòñÿ ñ òîãî, ÷òî âñå v∈Γ(s) ïîëó÷àþò
ïîìåòêó, ðàâíóþ åäèíèöå. Íà âòîðîé èòåðàöèè âñå v∈Γ2 (s)
ïîìå÷àþòñÿ äâîéêîé, çàòåì âñå v∈Γ3 (s) ïîìå÷àþòñÿ òðîéêîé,
è âîîáùå íà i èòåðàöèè äëÿ âñåõ v∈Γi (s) èìååì l(v)=i. Ïðî-
öåññ çàâåðøàåòñÿ, êîãäà ïîìå÷åííîé îêàçûâàåòñÿ âåðøèíà t.
Îïèñàííàÿ ïðîöåäóðà ðàññòàíîâêè ïîìåòîê íàçûâàåòñÿ ïîèñ-
êîì â øèðèíó. Ðàññìîòðèì ðåàëèçàöèþ òàêîãî âèäà ïîèñêà
íà ïðèìåðå. Ïóñòü òðåáóåòñÿ íàéòè êðàò÷àéøèé ïóòü ìåæäó
âåðøèíàìè v5 è v7 â ãðàôå, ïðåäñòàâëåííîì íà ðèñ. 4.3,à.
   (1)     (0)    (3)               v1 v2 v3 v4 v5        v6 v7 v8 v9 v10 v11
    v1      v5     v8
     s       sg
                   s          v1      1        1                  1
     @          
                               v2   1                           1
         @ 
                              v3      1     1            1
(2) s @
 v2 6                          v4         1               1 1          1
             (3)@
                v6 @           v5   1
(4) s            s @s(2)       v6         1                               1       1
 v3            A     6 v9
              A               v7            1                                    1
                  A s(5)     v8      1        1                         1
                  
                   A v10      v9   1                         1       1
                  A         v10           1                            1       1
     s
                sg -As
    v4          v7     v11     v11                            1               1
   (5)       (6)     (4)      l(vi ) 1   2    4   5   0       3   6   3   2   5   4
            à                                             á
                                  Ðèñ. 4.3
   Äëÿ ðàñ÷åòîâ èñïîëüçóåì ìàòðèöó ñìåæíîñòè ãðàôà, äî-
ïîëíèâ åå ñòðîêîé l(vi ) äëÿ ïîìåòîê âåðøèí, êàê ïîêàçàíî
íà ðèñ. 4.3,á. Ñðàçó ïîìåòèì âåðøèíó v5 íóëåâûì çíà÷åíèåì.
Íà ïåðâîé èòåðàöèè, ïðîñìàòðèâàÿ ïÿòóþ ñòðîêó ìàòðèöû,
íàõîäèì åäèíèöó â ïåðâîì ñòîëáöå. Ñëåäîâàòåëüíî, ïîìåò-
êà ïåðâîé âåðøèíû l(v1 )=1. Íà âòîðîé èòåðàöèè ïðîñìàò-


                                         77

Страницы