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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

A =
0 A
12
. . . A
1k
A
21
0 . . . A
2k
A
k1
A
k2
. . . 0
A
ij
, i6=j,
k i j
A
ij
=A
ji
T
.
G {v
1
, v
2
}, {v
3
, v
4
, v
5
}, {v
6
, v
7
}
A
G
sv
1
sv
2
s
v
3
s
v
4
s
v
5
sv
6
sv
7
!
!
!
!
!
!
!
!
P
P
P
P
P
P
P
P
P
c
c
c
c
c
c
c
c
Q
Q
Q
Q
Q
A
A
A
v
1
v
2
v
3
v
4
v
5
v
6
v
7
A =
v
1
v
2
v
3
v
4
v
5
v
6
v
7
0 0 0 1 0 1 1
0 0 1 0 1 0 1
0 1 0 0 0 0 1
1 0 0 0 0 1 0
0 1 0 0 0 1 0
1 0 0 1 1 0 0
1 1 1 0 0 0 0
K=[k
i,j
],
n,
k
i,j
=
(
−1, v
i
v
j
0, v
i
v
j
deg v
i
, i=j.
A
K K=D−A, D= diag(deg v
1
, deg v
2
, . . . , deg v
n
),
ñìåæíîñòè ìîæåò áûòü ïðèâåäåíà ê áëî÷íîìó âèäó, êîãäà ïî
ãëàâíîé äèàãîíàëè èäóò òîëüêî "íóëåâûå" áëîêè:
                    0 A ... A 
                          12      1k
                   A                
                    21 0 . . . A2k 
                 A=
                    .. .. . .   ..   .
                    .   .     . .  
                        Ak1 Ak2 . . .     0

Áëîêè Aij , ãäå i6=j, ìîãóò ðàññìàòðèâàòüñÿ êàê ïðèâåäåííûå4
ìàòðèöû ñìåæíîñòè äâóäîëüíûõ âåðøèííî-ïîðîæäåííûõ ïîä-
ãðàôîâ k -äîëüíîãî ãðàôà, îáðàçîâàííûõ âåðøèíàìè i è j
äîëåé, ïðè÷åì Aij =Aji T .  êà÷åñòâå ïðèìåðà íà ðèñ. 1.13 äàí
òðåõäîëüíûé ãðàô G ñ äîëÿìè {v1 , v2 }, {v3 , v4 , v5 }, {v6 , v7 } è
åãî ìàòðèöà ñìåæíîñòè A .
                                                   v1   v2   v3   v4   v5   v6   v7
             v3     v4    v5                                                       
               s     s !                  v1       0    0    0    1    0    1    1
               c     Q ! !s               v2      0    0    1    0    1    0    1
                         A
             !    ! QQ A
                 c!                       v3   
                                                  0    1    0    0    0    0    1 
  G    v2 !s !  cc
          P                Q
                            QAsv      A = v4      1    0    0    0    0    1    0
             P PP        6                                                    
                       c                  v5      0    1    0    0    0    1    0
                PP c
                         PP               v6   
                                                   1    0    0    1    1    0    0
                                                                                    
       v1 s 
                           c
                            P
                            csv7          v7       1    1    1    0    0    0    0

                                   Ðèñ. 1.13
    Ñâîåîáðàçíûì àíàëîãîì ìàòðèöû ñìåæíîñòè ÿâëÿåòñÿ ìàò-
ðèöà Êèðõãîôà K=[ki,j ], îïðåäåëÿåìàÿ êàê êâàäðàòíàÿ ìàòðè-
öà ïîðÿäêà n, ýëåìåíòû êîòîðîé
            (
                −1, åñëè âåðøèíû vi è vj ñìåæíû,
     ki,j =        0, åñëè âåðøèíû vi è vj íå ñìåæíû,
              deg vi , åñëè i=j.
Câÿçü ìåæäó ìàòðèöåé ñìåæíîñòè A è ìàòðèöåé Êèðõãîôà
K èìååò âèä K=D−A, ãäå D= diag(deg v1 , deg v2 , . . . , deg vn ),
ò. å. ÿâëÿåòñÿ ìàòðèöåé, äèàãîíàëüíûå ýëåìåíòû êîòîðîé ðàâ-
íû ñòåïåíÿì ñîîòâåòñòâóþùèõ âåðøèí. Âàæíàÿ îñîáåííîñòü
ìàòðèöû Êèðõãîôà (êàê è ëþáîé äðóãîé ìàòðèöû, ó êîòîðîé
  4Â  ïðèâåäåííîé ìàòðèöå ñìåæíîñòè äâóäîëüíîãî ãðàôà ñòðîêè ñîîò-
âåòñòâóþò âåðøèíàì îäíîé äîëè, à ñòîëáöû  âåðøèíàì äðóãîé



                                     19

Страницы