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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

j P
(l−1)
l, v
k
, k=1, n,
v
j
, i P
0
(v
i
, v
k
), k=1, n,
P
n
k=1
p
0
ik
p
(l−1)
kj
v
i
v
j
l+1.
P
(l)
P
0
×P
(l−1)
,
P
(1)
, P
(2)
, P
(3)
, . . . , P
(q−1)
,
≤ q
P
(1)
= P
0
× P
(0)
; P
(2)
= P
0
× P
(1)
; P
(3)
= P
0
× P
(2)
,
P
(0)
A.
P
0
a,
b, c
a b c d e a b c d e
P
0
=
a
b
c
d
e
0 b 0 d 0
0 0 0 d e
0 b 0 0 e
0 0 c 0 0
a 0 c 0 0
, P
(0)
= A =
a
b
c
d
e
0 1 0 1 0
0 0 0 1 1
0 1 0 0 1
0 0 1 0 0
1 0 1 0 0
.
P
(1)
a b c d e
P
(1)
= P
0
×P
(0)
=
a
b
c
d
e
0 0 d b b
e 0 d+e 0 0
e 0 e b b
0 c 0 0 c
0 a+c 0 a c
,
äóãà îòñóòñòâóåò. Ïîñêîëüêó j - ñòîëáåö ìàòðèöû P(l−1) îò-
ðàæàåò âñå ìàðøðóòû äëèíû l, ñ íà÷àëîì â vk , ãäå k=1, n,
è êîíöîì â vj , à i - ñòðîêà ìàòðèöû P0  êîíöû âñåõ äóã
                                                 Pn     0 (l−1)
âèäà (vi , vk ), ãäå k=1, n, òî ñóììà              k=1 pik pkj  îòðàæàåò
âñå ìàðøðóòû èç vi â vj äëèíû l+1. Ñëåäîâàòåëüíî, ìàòðè-
öà ìàðøðóòîâ P(l) ìîæåò áûòü ïîëó÷åíà êàê P0 ×P(l−1) , ïðè
ýòîì ñîìíîæèòåëè â ïðîèçâåäåíèÿõ íå ïåðåóïîðÿäî÷èâàþòñÿ
è íå èñïîëüçóåòñÿ ñòåïåííàÿ çàïèñü ïîâòîðÿþùèõñÿ ñîìíîæè-
òåëåé, ÷òîáû íå ïîòåðÿòü èíôîðìàöèþ î ïîðÿäêå ñëåäîâàíèÿ
âåðøèí. Òàêèì îáðàçîì ìîæåò áûòü ñôîðìèðîâàí ðÿä ìàò-
ðèö P(1) , P(2) , P(3) , . . . , P(q−1) , â ñîâîêóïíîñòè îïðåäåëÿþùèõ
âñå ìàðøðóòû äëèíû ≤ q äëÿ ëþáîé ïàðû âåðøèí.
    êà÷åñòâå ïðèìåðà âûïîëíèì ðàñ÷åòû äëÿ ãðàôà, ïðåä-
ñòàâëåííîãî íà ðèñ. 4.1, èñïîëüçóÿ ñîîòíîøåíèÿ:
    P(1) = P0 × P(0) ; P(2) = P0 × P(1) ; P(3) = P0 × P(2) ,
ãäå â êà÷åñòâå ìàòðèöû P(0) (ïóòè áåç ïðîìåæóòî÷íûõ âåð-
øèí) ñëåäóåò âçÿòü ìàòðèöó ñìåæíîñòè ãðàôà A. Ìàòðèöà
P0 ïîëó÷àåòñÿ, åñëè â ìàòðèöå ñìåæíîñòè åäèíèöû ïåðâîãî
ñòîëáöà çàìåíèòü áóêâîé a, åäèíèöû âòîðîãî ñòîëáöà  áóê-
âîé b, òðåòüåãî  áóêâîé c è ò. ä. Â ðåçóëüòàòå èìååì:
           a     b   c   d   e                        a    b   c   d   e
         
        a 0      b   0   d   0                     
                                                  a 0      1   0   1   0   
        b0      0   0   d   e                   b0      0   0   1   1   
    P = c
     0
         0      b   0   0   e   ,
                                      P(0)   =A= c 
                                                    0     1   0   0   1   .
                                                                           
        d 0      0   c   0   0                    d 0      0   1   0   0
        e a      0   c   0   0                    e 1      0   1   0   0

Ïîñëå ïåðâîãî óìíîæåíèÿ ïîëó÷àåì ìàòðèöó P(1) :
                                     a  b  c      d   e
                                                         
                           a         0  0  d      b   b
                           b        e  0 d+e     0   0   
                                                         
                                                         
      P(1) = P0 ×P(0)    = c        e  0  e      b   b   ,
                                                         
                           d        0  c  0      0   c   
                           e         0 a+c 0      a   c




                                        74

Страницы