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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

A=[a
i,j
] n,
a
i,j
{v
i
, v
j
},
v
i
v
j
P
n
j=1
a
i,j
=d(v
i
) i,
P
n
i=1
a
i,j
=d(v
j
) j
P
n
i=1
P
n
j=1
a
i,j
=2m,
G,
A deg v
i
.
G
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
Z
Z
Z
B
B
B
B
B
B
B
B
v
1
v
2
v
3
v
4
v
5
deg v
i
A =
v
1
v
2
v
3
v
4
v
5
0 1 1 1 0
1 0 1 1 0
1 1 0 1 0
1 1 1 0 1
0 0 0 1 0
3
3
3
4
1
O
n
A(O
n
)=0
n
K
n
A(K
n
)=1
n
−I
n
.
s
A =
A
11
0 . . . 0
0 A
22
. . . 0
0 0 . . . A
ss
A
ii
s
i
k
   1.4. Ìàòðèöû ãðàôîâ
   Ìàòðèöà ñìåæíîñòè. Îïðåäåëèì ìàòðèöó ñìåæíîñòè
êàê ñèììåòðè÷íóþ êâàäðàòíóþ ìàòðèöó A=[ai,j ] ïîðÿäêà n,
â êîòîðîé ýëåìåíò ai,j ðàâåí 1, åñëè â ãðàôå åñòü ðåáðî {vi , vj },
ò. å. vi è vj ñìåæíû, è 0, åñëè òàêîãî ðåáðà íåò.
                                  Pn
    Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî         a =d(vi ) ïðè ëþáîì i,
Pn                                Pnj=1Pi,j
                                         n
   i=1 ai,j =d(vj ) ïðè ëþáîì j è  i=1   j=1 ai,j =2m, ò. å. êîëè-
÷åñòâî åäèíèö â ëþáîé ñòðîêå èëè ñòîëáöå ìàòðèöû ñìåæíî-
ñòè ðàâíî ñòåïåíè ñîòâåòñòâóþùåé âåðøèíû ãðàôà, à îáùåå
êîëè÷åñòâî åäèíèö ðàâíî óäâîåííîìó ÷èñëó åãî ðåáåð.
     êà÷åñòâå ïðèìåðà íà ðèñ. 1.12 ïðèâåäåíû ãðàô G, åãî
ìàòðèöà ñìåæíîñòè A è ñòåïåííàÿ ïîñëåäîâàòåëüíîñòü deg vi .
              vs1
                                           v1         v2   v3   v4   v5   deg vi
              Z
               B                         
                                      v1 0             1    1   1    0     3
                  Z
     v5 s  B Zsv2                    v2  1           0    1   1    0     3
        B  B 
   G     B       B              A = v3 
                                          1           1    0   1    0    3
          Bs      Bs                v4 1             1    1   0    1      4
          v4       v3                 v5 0             0    0   1    0      1
                         Ðèñ. 1.12
   Îõàðàêòåðèçóåì ìàòðèöû ñìåæíîñòè íåêîòîðûõ âèäîâ ãðà-
ôîâ. Ìàòðèöà ñìåæíîñòè ïóñòîãî ãðàôà On ñîñòîèò èç îä-
íèõ íóëåé, ò. å. A(On )=0n . Ìàòðèöà ñìåæíîñòè ïîëíîãî ãðà-
ôà Kn ñîñòîèò èç îäíèõ åäèíèö, êðîìå äèàãîíàëüíûõ ýëåìåí-
òîâ, êîòîðûå ðàâíû 0. Çàïèøåì ýòî êàê A(Kn )=1n −In . Åñëè
ãðàô íåñâÿçåí è èìååò s êîìïîíåíò, òî, ïåðåñòàâëÿÿ ñòðîêè
è ñòîëáöû, åãî ìàòðèöó ñìåæíîñòè ìîæíî ïðèâåñòè ê áëî÷íî-
äèàãîíàëüíîìó âèäó:
                         A        0   ...    0 
                              11
                         0 A22 . . .         0 
                                                
                 A=
                         .. .. . .
                                    .            ,
                                              .. 
                          .  .                . 
                          0        0   . . . Ass
ãäå êàæäûé äèàãîíàëüíûé áëîê Aii ÿâëÿåòñÿ ìàòðèöåé ñìåæ-
íîñòè êîìïîíåíòû si .  ñëó÷àå k -äîëüíîãî ãðàôà ìàòðèöà


                                         18

Страницы