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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

D
(m)
.
D
(m)
P
(m)
. p
(m)
i,j
(i, j)
m i
j p
(0)
i,j
=i, c
ij
6=∞, p
(0)
i,j
=0
P
(m)
D
(m)
p
(m)
i,j
=
(
p
(m−1)
m,j
, d
(m−1)
i,j
> d
(m−1)
i,m
+ d
(m−1)
m,j
,
p
(m−1)
i,j
P
(m)
D
(m)
.
P
(0)
P
(1)
P
(2)
P
(3)
P
(4)
0 1 1 0
0 0 2 2
0 0 3 3
4 4 4 0
,
0 1 1 0
0 0 2 2
0 0 0 3
4 1 1 0
,
0 1 2 2
0 0 2 2
0 0 0 3
4 1 2 0
,
0 1 2 3
0 0 2 3
0 0 0 3
4 1 2 0
,
0 1 2 3
4 0 2 3
4 1 0 3
4 1 2 0
,
D
d
4,2
d
4,3
.
p
4,2
p
4,3
P
p
1,2
p
1,3
m
ýëåìåíòû ìàòðèö D(m) . Ïîÿâëåíèå íà íåêîòîðîé èòåðàöèè
îòðèöàòåëüíûõ çíà÷åíèé íà ãëàâíîé äèàãîíàëè ìàòðèöû ïî-
êàçûâàåò, ÷òî â ãðàôå åñòü êîíòóð (öèêë) ñ îòðèöàòåëüíûì
âåñîì.  ýòîì ñëó÷àå äàëüíåéøèå âû÷èñëåíèÿ òåðÿþò ñìûñë,
òàê êàê â ïîäîáíûõ ñèòóàöèÿõ àëãîðèòì "íå ðàáîòàåò".
   Êðîìå äëèíû, äëÿ êàæäîãî êðàò÷àéøåãî ïóòè íåîáõîäè-
ìî îïðåäåëèòü è ïîñëåäîâàòåëüíîñòü âõîäÿùèõ â íåãî âåð-
øèí. Ñ ýòîé öåëüþ îäíîâðåìåííî ñ ìàòðèöåé D(m) ôîðìèðó-
                                                           (m)
åòñÿ ìàòðèöà "âåðøèí-ïðåäøåñòâåííèö" P(m) . Ýëåìåíò pi,j
ýòîé ìàòðöû óêàçûâàåò ïðåäïîñëåäíþþ âåðøèíó êðàò÷àéøå-
ãî (i, j) -ïóòè, êîòîðûé ìîæåò ñîäåðæàòü â êà÷åñòâå ïðîìåæó-
òî÷íûõ òîëüêî ïåðâûå m âåðøèí ãðàôà. Âíà÷àëå äëÿ âñåõ i è
               (0)                     (0)
j ïîëàãàåì pi,j =i, åñëè cij 6=∞, è pi,j =0  â ïðîòèâíîì ñëó-
÷àå. Äàëåå íà êàæäîé èòåðàöèè ìàòðèöà P(m) ïåðåñ÷èòûâà-
åòñÿ îäíîâðåìåííî ñ ìàòðèöåé D(m) ñ ïîìîùüþ ñîîòíîøåíèÿ
            (
                (m−1)          (m−1)     (m−1)    (m−1)
     (m)
    pi,j =    p m,j   , åñëè d i,j   > d i,m   + dm,j   ,
                (m−1)
              pi,j       â ïðîòèâíîì ñëó÷àå .
Òàêèì îáðàçîì, ýëåìåíò ìàòðèöû P(m) êîððåêòèðóåòñÿ ïðè
êàæäîì èçìåíåíèè ñîîòâåòñòâóþùåãî ýëåìåíòà ìàòðèöû D(m) .
Äëÿ íàøåãî ïðèìåðà èìååì ñëåäóþùèé ðÿä ìàòðèö:
        P(0)                 P(1)                 P(2)                 P(3)                 P(4)
                                                                                              
    0   1 1    0         0   1 1    0         0   1 2    2         0   1 2    3         0   1 2    3
                                                                                              
   0   0 2    2       0   0 2    2       0   0 2    2       0   0 2    3       4   0 2    3   
                  ,                  ,                  ,                  ,                  ,
   0   0 3    3       0   0 0    3       0   0 0    3       0   0 0    3       4   1 0    3   
    4   4 4    0         4   1 1    0         4   1 2    0         4   1 2    0         4   1 2    0

ãäå ïîä÷åðêíóòû ýëåìåíòû, êîòîðûå íà î÷åðåäíîé èòåðàöèè
ïîëó÷àþò íîâûå çíà÷åíèÿ. Íàïðèìåð, êàê áûëî ïîêàçàíî ðà-
íåå, íà ïåðâîé èòåðàöèè â ìàòðèöå D èçìåíèëèñü ýëåìåí-
òû d4,2 è d4,3 . Ïîýòîìó ñîãëàñíî ñ ïðèâåäåííîìó âûøå ñî-
îòíîøåíèþ ýëåìåíòû p4,2 è p4,3 ìàòðèöû P ïîëó÷àþò íî-
âûå çíà÷åíèÿ, ðàâíûå p1,2 è p1,3 ñîîòâåòñòâåííî. È âîîáùå,
íà m-é èòåðàöèè èçìåíÿþùèéñÿ ýëåìåíò ìàòðèöû ïîëó÷àåò
çíà÷åíèå, ðàâíîå ýëåìåíòó, íàõîäÿùåìóñÿ â òîì æå ñòîëáöå íà


                                                   90

Страницы