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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

B=[b
i,j
]
n×m, b
i,j
v
i
e
j
,
B
B
i
. G
B.
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
e
1
e
2
e
3
e
4
e
5
e
6
e
7
B =
v
1
v
2
v
3
v
4
v
5
1 1 1 0 0 0 0
1 0 0 1 1 0 0
0 1 0 1 0 1 0
0 0 1 0 1 1 1
0 0 0 0 0 0 1
=
B
1
B
2
B
3
B
4
B
5
B
i
=(
P
B
j
) (mod 2), 1≤j≤ n j6=i.
B
1
=B
2
⊕B
3
⊕B
4
⊕B
5
= [1, 0, 0, 1, 1, 0, 0]⊕
⊕[0, 1, 0, 1, 0, 1, 0]⊕[0, 0, 1, 0, 1, 1, 1]⊕[0, 0, 0, 0, 0, 0, 1]=[1, 1, 1, 0, 0, 0, 0]
ñóììà ýëåìåíòîâ êàæäîé ñòðîêè è êàæäîãî ñòîëáöà ðàâíà íó-
ëþ) ñîñòîèò â òîì, ÷òî àëãåáðàè÷åñêèå äîïîëíåíèÿ âñåõ ýëå-
ìåíòîâ ìàòðèöû ðàâíû ìåæäó ñîáîé.
   Ïîñêîëüêó èçîìîðôíûå ãðàôû ðàçëè÷àþòñÿ ëèøü ðàçìåò-
êîé (íóìåðàöèåé) âåðøèí ñîîòâåòñòâóþùåãî àáñòðàêòíîãî ãðà-
ôà, ÿñíî, ÷òî èõ ìàòðèöû ñìåæíîñòè (ìàòðèöû Êèðõãîôà)
ìîãóò áûòü ïîëó÷åíû îäíà èç äðóãîé ïóòåì íåêîòîðîé ïåðå-
ñòàíîâêè ñòðîê è ñòîëáöîâ.
   Ìàòðèöà èíöèäåíòíîñòè. Îïðåäåëèì ìàòðèöó èíöè-
äåíòíîñòè ãðàôà êàê ïðÿìîóãîëüíóþ ìàòðèöó B=[bi,j ] ðàç-
ìåðà n×m, â êîòîðîé ýëåìåíò bi,j ðàâåí 1, åñëè âåðøèíà vi
èíöèäåíòíà ðåáðó ej , è 0 â ïðîòèâíîì ñëó÷àå. Ñòðîêè ìàò-
ðèöû B íàçûâàþò âåêòîðàìè èíöèäåíòíîñòè è îáîçíà÷àþò
êàê Bi . Íà ðèñ. 1.14 èçîáðàæåí òîò æå ãðàô G , ÷òî è íà
ðèñ. 1.12, è ïðèâåäåíà åãî ìàòðèöà èíöèäåíòíîñòè B.
                  vs1                    e1      e2   e3   e4   e5   e6   e7
                  Z
                   B Z                 
                                    v1 1         1    1    0    0    0    0      B1   
      v5 s         B Zsv2          v2  1       0    0    1    1    0    0      B2   
         B      B             B = v3                                   0           
    G
          B          B               0        1    0    1    0    1       =   B3   
                                    v4 0         0    1    0    1    1    1        B4
           Bs         Bs
           v4          v3           v5 0         0    0    0    0    0    1        B5
                                        Ðèñ. 1.14
    Êàê ñëåäóåò èç îïðåäåëåíèÿ, îáùåå êîëè÷åñòâî åäèíèö â
ìàòðèöå èíöèäåíòíîñòè ðàâíî óäâîåííîìó ÷èñëó ðåáåð ãðà-
ôà, êîëè÷åñòâî åäèíèö â ëþáîé ñòðîêå ðàâíî ñòåïåíè ñîîò-
âåòñòâóþùåé âåðøèíû, à ñòîëáöû ñîäåðæàò ïî äâå åäèíèöû.
Ïîýòîìó ìåæäó ñòðîêàìè ìàòðèöû ñóùåñòâóåò ïðîñòàÿ çàâè-
ñèìîñòü: ýëåìåíòû ëþáîé ñòðîêè ìîãóò áûòü ïîëó÷åíû ñëî-
æåíèåì îäíîèìåííûõ ýëåìåíòîâ îñòàëüíûõ ñòðîê ïî ìîäóëþ
2. Èñïîëüçóÿ
     P       ïîíÿòèå âåêòîðà èíöèäåíòíîñòè, ìîæíî çàïèñàòü
Bi =( Bj ) (mod 2), ãäå 1≤j≤ n è j6=i. Òàê, äëÿ ïðèâåäåííîé
âûøå ìàòðèöû èìååì: B1 =B2 ⊕B3 ⊕B4 ⊕B5 = [1, 0, 0, 1, 1, 0, 0]⊕
⊕[0, 1, 0, 1, 0, 1, 0]⊕[0, 0, 1, 0, 1, 1, 1]⊕[0, 0, 0, 0, 0, 0, 1]=[1, 1, 1, 0, 0, 0, 0] .
   Ìàòðèöà èíöèäåíòíîñòè íåñâÿçíîãî ãðàôà, êàê è ìàòðèöà
ñìåæíîñòè, ìîæåò áûòü ïðèâåäåíà ê áëî÷íî-äèàãîíàëüíîìó
âèäó, ãäå êàæäûé äèàãîíàëüíûé áëîê ÿâëÿåòñÿ ìàòðèöåé èí-
öèäåíòíîñòè íåêîòîðîé êîìïîíåíòû ñâÿçíîñòè.

                                          20

Страницы