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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

i m m j,
m−1
m
d
(m)
im
= d
(m−1)
im
, d
(m)
mj
= d
(m−1)
mj
.
m m
D
(m−1)
D
(m)
D
(m)
n
2
−3n+2.
n
O(n
3
).
G,
C. D
(0)
=C,
s
v
1
s
v
2
s
v
3
s
v
4
-
@
@
@
@R
?
6
G
D
(0)
=C=
0 5 10 ∞
∞ 0 3 13
∞ ∞ 0 8
7 15 20 0
, D
(1)
=
0 5 10 ∞
∞ 0 3 13
∞ ∞ 0 8
7 12 17 0
,
D
(2)
=
0 5 8 18
∞ 0 3 13
∞ ∞ 0 8
7 12 15 0
, D
(3)
=
0 5 8 16
∞ 0 3 11
∞ ∞ 0 8
7 12 15 0
, D
(4)
=
0 5 8 16
18 0 3 11
15 20 0 8
7 12 15 0
.
D
(1)
, D
(2)
, D
(3)
, D
(4)
,
D
(4)
m m
ïóòåé èç i â m è èç m â j, â êîòîðûõ ïðîìåæóòî÷íûìè ìî-
ãóò áûòü ëèøü ïåðâûå m−1 âåðøèí. Ðàñ÷åòíîå ñîîòíîøåíèå
ñóùåñòâåííî óïðîùàåòñÿ, êîãäà m ÿâëÿåòñÿ íà÷àëüíîé èëè
êîíå÷íîé âåðøèíîé ðàññìàòðèâàåìîãî ïóòè. Òîãäà èìååì:
                   (m)    (m−1)         (m)       (m−1)
                  dim = dim        , dmj = dmj            .
Ýòî îçíà÷àåò, ÷òî m -ÿ ñòðîêà è m -é ñòîëáåö íå ìåíÿþòñÿ ïðè
ïåðåõîäå îò ìàòðèöû D(m−1) ê ìàòðèöå D(m) è ïîýòîìó ìîãóò
íå ïåðåñ÷èòûâàòüñÿ. Åñëè çàðàíèå èçâåñòíî, ÷òî â ãðàôå íåò
êîíòóðîâ îòðèöàòåëüíîãî âåñà, òî è äèàãîíàëüíûå ýëåìåíòû
ìàòðèö òàêæå ìîæíî íå ïåðåñ÷èòûâàòü. Îòìå÷åííûå ôàêòû
ïîçâîëÿþò óòâåðæäàòü, ÷òî òðóäîåìêîñòü âû÷èñëåíèÿ ëþáîé
èç ìàòðèö D(m) ïðîïîðöèîíàëüíà n2 −3n+2. Ó÷èòûâàÿ, ÷òî
äëÿ ïîëó÷åíèÿ ðåçóëüòàòà òðåáóåòñÿ n èòåðàöèé, â öåëîì òðó-
äîåìêîñòü àëãîðèòìà ìîæíî îöåíèòü êàê O(n3 ).
     êà÷åñòâå ïðèìåðà íàéäåì ìàòðèöó äëèí êðàò÷àéøèõ ïó-
òåé ìåæäó âñåìè ïàðàìè âåðøèí äëÿ ãðàôà G, èçîáðàæåííî-
ãî íà ðèñ. 4.12 è èìåþùåãî ìàòðèöó âåñîâ C. Ïîëàãàÿ D(0) =C,
      v1s                                                                 
              - sv2            0    5   10   ∞             0     5   10   ∞
        @
        6                                                                
          @                  ∞     0    3   13         ∞      0    3   13 
     G              D(0) =C=                   , D(1) =                   ,
            @                ∞    ∞     0   8          ∞     ∞     0    8 
        s    @
              R  ?
                 s
      v4                       7   15   20    0            7    12   17   0
               v3
                                                                        
         0 5 8 18              0    5    8   16             0   5     8   16
       ∞ 0 3 13                                                         
                           ∞    0    3    11          18   0     3   11 
D(2) =             , D(3) =                  , D(4) =                   .
      ∞ ∞ 0 8              ∞    ∞     0    8          15   20    0    8 
         7 12 15 0             7   12   15    0             7   12   15    0

                               Ðèñ. 4.12
ñ ïîìîùüþ àëãîðèòìà Ôëîéäà ïîñëåäîâàòåëüíî ïîëó÷àåì ìàò-
ðèöû: D(1) , D(2) , D(3) , D(4) , ïðåäñòàâëåííûå íà ðèñ. 4.12, ïðè-
÷åì D(4) è åñòü èñêîìàÿ ìàòðèöà äëèí êðàò÷àéøèõ ïóòåé.
    Â êàæäîé ìàòðèöå âûäåëåíû m -é ñòîëáåö è m -ÿ ñòðî-
êà, íå ïîäëåæàùèå ïåðåñ÷åòó íà ñîîòâåòñòâóþùåé èòåðàöèè.



                                   88

Страницы