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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

d
(m−1)
im
= ∞ d
(m)
ij
= d
(m−1)
ij
j
d
(m−1)
mj
= ∞ d
(m)
ij
= d
(m−1)
ij
i
i
∞, i
D
(0)
∞
D
(1)
d
(0)
4,2
=15 d
(0)
4,3
=20.
d
(1)
4,2
, d
(0)
1,2
=5 d
(0)
1,4
=7,
d
(0)
4,2
d
(1)
4,2
=12. d
(1)
4,3
=17.
d
(2)
1,3
, d
(2)
1,4
d
(2)
4,3
, D
(2)
D
(1)
.
m=2,
d
(3)
1,4
d
(3)
2,4
, d
(4)
1,2
d
(4)
1,3
d
(4)
2,3
d
(4)
2,1
d
(4)
3,1
d
(4)
3,2
,
Ïîñêîëüêó âåñà âñåõ äóã íå îòðèöàòåëüíû, äèàãîíàëüíûå ýëå-
ìåíòû ìàòðèö ïîñòîÿííû è ðàâíû íóëþ. Êðîìå òîãî,
               (m−1)             (m)        (m−1)
       åñëè dim        = ∞ , òî dij = dij           äëÿ âñåõ j    è
               (m−1)             (m)        (m−1)
   åñëè dmj    = ∞ , òî dij = dij     äëÿ âñåõ i .
   Èíûìè ñëîâàìè, åñëè i ýëåìåíò âûäåëåííîãî ñòîëáöà ðà-
âåí ∞, òî âñå ýëåìåíòû i ñòðîêè íà òåêóùåé èòåðàöèè íå èç-
ìåíÿþòñÿ. Àíàëîãè÷íîå óòâåðæäåíèå ñïðàâåäëèâî è äëÿ âûäå-
ëåííîé ñòðîêè. Ó÷åò ïðèâåäåííûõ ñîîòíîøåíèé ïîçâîëÿåò ñî-
êðàòèòü îáúåì âû÷èñëåíèé íà íà÷àëüíûõ èòåðàöèÿõ, îñîáåííî
äëÿ ðàçðåæåííûõ ãðàôîâ. Ïðîèëëþñòðèðóåì ýòî íà ïðèìåðå.
Âòîðîé è òðåòèé ýëåìåíòû ïåðâîãî ñòîëáöà, à òàêæå ÷åòâåð-
òûé ýëåìåíò ïåðâîé ñòðîêè ìàòðèöû D(0) ðàâíû ∞ .
Ïîýòîìó, êðîìå ïåðâîãî ñòîëáöà è ïåðâîé ñòðîêè, ïðè ïåðå-
õîäå ê D(1) ñîõðàíÿþò ñâîå çíà÷åíèå ýëåìåíòû âòîðîé è òðå-
òüåé ñòðîê, à òàêæå ýëåìåíòû ÷åòâåðòîãî ñòîëáöà. Ïåðåñ÷åòó
                   (0)      (0)
ïîäëåæàò14 ëèøü d4,2 =15 è d4,3 =20. ×òîáû ïîëó÷èòü, íàïðè-
         (1)                                (0)       (0)
ìåð, d4,2 , äîñòàòî÷íî ñëîæèòü d1,2 =5 è d1,4 =7, êîòîðûå íàõî-
äÿòñÿ â ïåðâîé ñòðîêå è ïåðâîì ñòîëáöå íà ïîçèöèÿõ, ñîîòâåò-
ñòâóþùèõ ïåðåñ÷èòûâàåìîìó ýëåìåíòó, ñðàâíèòü íàéäåííóþ
            (0)
ñóììó ñ d4,2 è âûáðàòü íàèìåíüøåå èç äâóõ ÷èñåë. Ïîëó÷àåì
 (1)                                                        (1)
d4,2 =12. Òî÷íî òàê æå ðåøàåòñÿ çàäà÷à è äëÿ d4,3 =17. Íåòðóä-
íî óáåäèòüñÿ, ÷òî íà âòîðîé èòåðàöèè ñëåäóåò âû÷èñëÿòü òîëü-
      (2)     (2)  (2)
êî d1,3 , d1,4 è d4,3 , à âñå îñòàëüíûå ýëåìåíòû ìàòðèöà D(2)
"íàñëåäóåò" îò D(1) . Äåéñòâèòåëüíî, âòîðàÿ ñòðîêà è âòîðîé
ñòîëáåö íå èçìåíÿþòñÿ ïîòîìó, ÷òî m=2, à ïåðâûé ñòîëáåö è
òðåòüÿ ñòðîêà  â ñèëó ïðèâåäåííûõ âûøå ñîîòíîøåíèé. Âñå
òðè íàçâàííûõ ýëåìåíòà ïîëó÷àþò íîâûå çíà÷åíèÿ, ðàâ-
íûå ñîîòâåòñòâåííî 8, 18 è 15. Íà òðåòüåé èòåðàöèè ñ÷èòàþòñÿ
 (3)      (3)                     (4)  (4)    (4)    (4)    (4)    (4)
d1,4 è d2,4 , à íà ÷åòâåðòîé  d1,2 , d1,3 , d2,3 , d2,1 , d3,1 , d3,2 , ïðè-
÷åì èç ýòèõ øåñòè òðè ïåðâûå ñîõðàíÿþò ïðåæíèå çíà÷åíèÿ.
     Åñëè ãðàô èìååò äóãè ñ îòðèöàòåëüíûì âåñîì, öåëåñîîá-
ðàçíî íàðÿäó ñ îñòàëüíûìè ïåðåñ÷èòûâàòü è äèàãîíàëüíûå
  14 Ýëåìåíòû,    ïîäëåæàùèå ïåðåñ÷åòó, â ìàòðèöàõ ïîä÷åðêíóòû.



                                       89

Страницы