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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

s
G C
s v
5
.
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
s
v
6
s
v
7
s
v
8
s
v
9
s
v
10
?
-
?
?
A
A
A
AU
6
?
G
@
@
@
@R
R
@
@
@
@R
-
- -A
A
A
AK
-
I
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
C=
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
3 19 11
10 7 19 22
13
5 3
5 14 20 29 23
2 8
4
8
7 6
9
v
i
∈Γ(v
5
)
l(v
i
), (v
5
, v
i
),
s
v
2
s
v
3
s
v
4
(20)
s
v
5
∗
s
v
6
s
v
8
6
-
v
2
(v
5
, v
2
), l(v
2
)=5.
v
2
l(v
i
).
∞
     Àëãîðèòì Äåéêñòðû. Ýòîò àëãîðèòì ïîçâîëÿåò íàéòè
êðàò÷àéøèé ïóòü ìåæäó íåêîòîðîé âåðøèíîé s è îñòàëüíû-
ìè âåðøèíàìè ïðè óñëîâèè, ÷òî â ãðàôå íåò äóã (ðåáåð) ñ
îòðèöàòåëüíûì âåñîì. Ðàññìîòðèì îñíîâíóþ èäåþ àëãîðèòìà
íà ïðèìåðå ãðàôà G ìàòðèöåé âåñîâ12 C , ïðåäñòàâëåííûõ íà
ðèñ. 4.7, âçÿâ â êà÷åñòâå s âåðøèíó v5 .
                                                v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
        v1         v2           v            v1            3 19    11
        s          s        - s3
        @           @                        v2 10     7 19    22             
                    6        I              v3                13             
           @            @                                                     
               @           @                 v4
                                                                   5 3        
                                                                               
 G   v4 ?
        s @     Rs          @?
                             R
                             -   sv6         v5
                                          C= v 
                                                     5 14 20    29    23       
        A         vAK5                      6                         2 8  
          A       A                        v7
                                                                      4       
                                                                               
            A          A                   v8                         8     
     R? s -AU s        -As - ? s           v9              7             6 
        v7 v8             v9 v10            v10         9
                                       Ðèñ. 4.7
    Âûäåëèì âñå âåðøèíû vi ∈Γ(v5 ) è ïðèïèøåì èì ÷èñëîâûå
ìåòêè l(vi ), ðàâíûå âåñàì äóã (v5 , vi ), êàê ïîêàçàíî íà ðèñ. 4.8
(âåñà ïðîñòàâëåíû îêîëî äóã, à ìåòêè  îêîëî âåðøèí è çà-
                                 êëþ÷åíû â êðóãëûå ñêîáêè). Î÷å-
        min=(5)          (14)    âèäíî, ÷òî êðàò÷àéøèé ïóòü äî
                 v2       v3
                  s        s     v2 ñîñòîèò èç åäèíñòâåííîé äó-
                  6             ãè (v5 , v2 ), à åãî äëèíà l(v2 )=5.
                5    14          Çàôèêñèðóåì ýòó âåðøèíó è áó-
(20)                        (29) äåì ñ÷èòàòü åå ìåòêó ïîñòîÿí-
  v4 s 20        s 29 - sv6
                                 íîé. Òàêèì îáðàçîì, äëÿ v2 çàäà-
                v5
            23  0
                    ∗            ÷à ðåøåíà. Îòíîñèòåëüíî îñòàëü-
                                íûõ ÷åòûðåõ âåðøèí ìîæíî ëèøü
            
           s                    óòâåðæäàòü, ÷òî äëèíû êðàò÷àé-
     (23) v8                     øèõ ïóòåé äî íèõ íå ïðåâîñ-
                                 õîäÿò çíà÷åíèé l(vi ). Ïîýòîìó
               Ðèñ. 4.8
                                 ñîîòâåòñòâóþùèå ìåòêè ïîêà ñ÷è-
òàåì âðåìåííûìè.  äàëüíåéøåì, ÷òîáû ðàçëè÷àòü ïîñòîÿí-
íûå è âðåìåííûå ìåòêè, ïîñòîÿííûå áóäåì çàêëþ÷àòü â ðàìêó.
 12 Ïóñòûå êëåòêè â ìàòðèöå îçíà÷àþò, ÷òî ñîîòâåòñòâóþùèõ äóã â ãðà-
ôå íåò. Ìîæíî ñ÷èòàòü òàêæå, ÷òî äóãè åñòü è êàæäàÿ èìååò âåñ ∞ .



                                             82

Страницы