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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

A+A
2
+ . . . +A
p
=
p
X
l=1
A
l
.
l=1, 2, 3, 4.
A,
a b c d e a b c d e
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
, A
2
=
a
b
c
d
e
0 0 1 1 1
1 0 2 0 0
1 0 1 1 1
0 1 0 0 1
0 2 0 1 1
,
a b c d e a b c d e
A
3
=
a
b
c
d
e
1 1 2 0 1
0 3 0 1 2
1 2 2 1 1
1 0 1 1 1
1 0 2 2 2
, A
4
=
a
b
c
d
e
1 3 1 2 3
2 0 3 3 3
1 3 2 3 4
1 2 2 1 1
2 3 4 1 2
.
c e
(c, b, e)
(c, e, c, e)
(c, b, e, c, e), (c, b, d, c, e),
(c, e, a, b, e), (c, e, c, b, e)
e c
(e, c, e, c), (e, a, d, c)
(e, c, b, e, c), (e, a, b, d, c)
(e, a, b, e, c) (e, c, b, d, c
a
(l)
ce
a
(l)
ec
A
2
, A
3
, A
4
.
ìåæäó âñåìè ïàðàìè âåðøèí îïðåäåëÿåòñÿ êàê ñóììà
                                   p
                                   X
                A+A2 + . . . +Ap =   Al .
                                              l=1

    êà÷åñòâå ïðèìåðà ïðèâåäåì ðåøåíèå çàäà÷è ïåðåñ÷åòà
ìàðøðóòîâ ãðàôà, èçîáðàæåííîãî íà ðèñ. 4.1 ïðè l=1, 2, 3, 4.
Èíôîðìàöèþ î ïóòÿõ â îäíó äóãó íåñåò ìàòðèöà ñìåæíîñòè
A, îñòàëüíûå òðè ìàòðèöû ïîëó÷àåì ïðîñòûì óìíîæåíèåì:
             a    b    c   d   e               a    b   c   d   e
           
         a 0      1    0   1   0            
                                            a 0     0   1   1   1   
         b0      0    0   1   1           b1     0   2   0   0   
      A= c 
           0     1    0   0   1   ,
                                       A = c
                                         2
                                             1     0   1   1   1   ,
                                                                    
         d 0      0    1   0   0            d 0     1   0   0   1
         e 1      0    1   0   0            e 0     2   0   1   1

             a     b   c   d   e                a   b   c   d   e
           
         a 1       1   2   0   1          a 1     3   1   2   3   
         b0       3   0   1   2           b 2    0   3   3   3   
      A = 
       3 c 1      2   2   1   1   ,
                                       A = 
                                         4  c 1    3   2   3   4   .
                                                                    
         d 1       0   1   1   1           d 1      2   2   1   1
         e 1       0   2   2   2           e 2      3   4   1   2

    Íåïîñðåäñòâåííîé ïðîâåðêîé ïî èçîáðàæåíèþ ãðàôà óáåæ-
äàåìñÿ, ÷òî, íàïðèìåð, ìåæäó âåðøèíàìè c è e åñòü
   1 ìàðøðóò (ïóòü) äëèíû 2: (c, b, e) ;
   1 ìàðøðóò äëèíû 3: (c, e, c, e) ;
   4 ìàðøðóòà (öåïè) äëèíû 4: (c, b, e, c, e), (c, b, d, c, e),
                                   (c, e, a, b, e), (c, e, c, b, e) ;
à ìåæäó e è c åñòü
   2 ìàðøðóòà äëèíû 3: (e, c, e, c), (e, a, d, c) (ïóòü);
   4 ìàðøðóòà äëèíû 4: (e, c, b, e, c), (e, a, b, d, c) (ïóòü),
                         (e, a, b, e, c) (öåïü), (e, c, b, d, c (öåïü).
                                                                 (l)  (l)
Ýòî ïîëíîñòüþ ñîîòâåòñòâóåò çíà÷åíèÿì ýëåìåíòîâ ace è aec
(âûäåëåíû øðèôòîì è ïîä÷åðêíóòû) ìàòðèö A2 , A3 , A4 . Ê
ñîæàëåíèþ, îïðåäåëÿåòñÿ ÷èñëî ìàðøðóòîâ, ñâÿçûâàþùèõ ïà-
ðó âåðøèí, à íå ÷èñëî ïóòåé, êîòîðûå ïðåäñòàâëÿþò íàèáîëü-
øèé èíòåðåñ. Êîëè÷åñòâî ïóòåé ìîæíî îïðåäåëèòü, åñëè íàéòè
âñå ìàðøðóòû è îòáðîñèòü òå èç íèõ, ãäå åñòü ïîâòîðÿþùèå-



                                        72

Страницы