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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

P
(2)
a b c d e
P
(2)
=P
0
×P
(1)
=
a
b
c
d
e
be dc bd+be 0 dc
0 ea+dc+ec 0 ea dc+ec
be ea+ec bd+be ea ec
ce 0 ce cb cb
ce 0 ad+ce ab+cb ab+cb
.
P
(3)
=P
0
×P
(2)
a b c d e
dce bea+bdc+bec dce bea+dcb dcb+bdc+bec
dce+ece 0 ead+dce+ece eab+dcb+ecb eab+dcb+ecb
ece bea+bdc+bec ead+ece bea+eab+ecb
eab+ecb+
+bdc+bec
cbe cea+cec cbd+cbe cea cec
abe+cbe cea+adc+cec
abd+cbd+
+abe+cbe
cea adc+cec
.
l
l≤(n−2),
n−2
G C=[c
i,j
]
s t,
l=n−1
ïîñëå âòîðîãî óìíîæåíèÿ  ìàòðèöó P(2) :
                             a   b        c   d       e
                                             
             a be     dc    bd+be    0    dc
             b 0 ea+dc+ec   0     ea dc+ec 
   (2) 0 (1)                                 
  P =P ×P = c  be ea+ec bd+be ea         ec  .
                                             
             d  ce   0       ce    cb    cb 
             e ce     0     ad+ce ab+cb ab+cb

Íàêîíåö, ìàòðèöà P(3) =P0 ×P(2) ïðèíèìàåò âèä:
           a         b               c            d       e
                                                            
 a     dce   bea+bdc+bec      dce      bea+dcb   dcb+bdc+bec
                                                            
 b  dce+ece      0      ead+dce+ece eab+dcb+ecb eab+dcb+ecb 
                                                            
                                                 eab+ecb+   
 c   ece   bea+bdc+bec   ead+ece   bea+eab+ecb             
                                                 +bdc+bec  .
 d cbe       cea+cec      cbd+cbe      cea         cec
                                                             
                                                             
                                                            
                         abd+cbd+                           
 e abe+cbe cea+adc+cec                   cea       adc+cec
                           +abe+cbe

   Êàê âèäíî èç ïðèìåðà, óæå ïðè íåáîëüøèõ çíà÷åíèÿõ l
ìàòðèöû ìîãóò áûòü âåñüìà ãðîìîçäêèìè. Îäíàêî, åñëè öåëü
ïîèñêà  ïóòè, îáúåì âû÷èñëåíèé ìîæíî ñóùåñòâåííî óìåíü-
øèòü, îòáðàñûâàÿ ïðîèçâåäåíèÿ ñ ïîâòîðÿþùèìèñÿ âåðøèíà-
ìè. Î÷åâèäíî òàêæå, ÷òî â ýòîì ñëó÷àå l≤(n−2), òàê êàê ïóòü
â ãðàôå íå ìîæåò ñîäåðæàòü áîëåå ÷åì n−2 ïðîìåæóòî÷íûõ
âåðøèí 10 . Êðîìå òîãî, ñ óâåëè÷åíèåì äëèíû êîëè÷åñòâî ïóòåé
â îáùåì ñëó÷àå äîëæíî ñîêðàùàòüñÿ.


   4.4. Çàäà÷è î êðàò÷àéøèõ ïóòÿõ
   Áîëüøèíñòâî çàäà÷ ýòîãî âèäà ìîæíî ðàññìàòðèâàòü êàê
ðàñøèðåíèå, îáîáùåíèå èëè ìîäèôèêàöèþ ñëåäóþùåé çàäà÷è.
   Â ãðàôå G ñ ìàòðèöåé âåñîâ C=[ci,j ] òðåáóåòñÿ íàéòè
ïóòü ìåæäó çàäàííîé ïàðîé âåðøèí s è t, ó êîòîðîãî ñóììà
 10    ñëó÷àå çàìêíóòîãî ïóòè (êîíòóðà) l=n−1 .



                                     75

Страницы