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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G(n, m)
C
n−1
m
B
−i
(n−1)×m
i
n−1
G,
B.
s
v
1
s
v
2
s
v
3
s
v
4
e
1
e
2
e
3
e
4
e
5
G
e
1
e
2
e
3
e
4
e
5
B =
v
1
v
2
v
3
v
4
1 1 0 0 0
1 0 1 1 0
0 0 0 1 1
0 1 1 0 1
B
−1
C
3
5
=10
e
1
e
2
e
3
e
4
e
5
e
1
e
2
e
3
e
1
e
2
e
4
B
−1
=
v
2
v
3
v
4
"
−1 0 1 1 0
0 0 0 −1 1
0 −1 −1 0 −1
#
,
¯
¯
¯
¯
¯
−1 0 1
0 0 0
0−1−1
¯
¯
¯
¯
¯
=0
¯
¯
¯
¯
¯
−1 0 1
0 0−1
0−1 0
¯
¯
¯
¯
¯
=1
M
1
M
2
e
1
e
2
e
5
¯
¯
¯
¯
¯
−1 0 0
0 0 1
0−1−1
¯
¯
¯
¯
¯
= − 1,
M
3
e
2
e
3
e
4
¯
¯
¯
¯
¯
0 1 1
0 0−1
−1−1 0
¯
¯
¯
¯
¯
=1,
M
7
e
1
e
3
e
4
¯
¯
¯
¯
¯
−1 1 1
0 0−1
0−1 0
¯
¯
¯
¯
¯
=1,
M
4
e
2
e
3
e
5
¯
¯
¯
¯
¯
0 1 0
0 0 1
−1−1−1
¯
¯
¯
¯
¯
= − 1,
M
8
e
1
e
3
e
5
¯
¯
¯
¯
¯
−1 1 0
0 0 1
0−1−1
¯
¯
¯
¯
¯
= − 1,
M
5
e
2
e
4
e
5
¯
¯
¯
¯
¯
0 1 0
0−1 1
−1 0−1
¯
¯
¯
¯
¯
= − 1,
M
9
e
1
e
4
e
5
¯
¯
¯
¯
¯
−1 1 0
0−1 1
0 0−1
¯
¯
¯
¯
¯
= − 1,
M
6
e
3
e
4
e
5
¯
¯
¯
¯
¯
1 1 0
0−1 1
−1 0−1
¯
¯
¯
¯
¯
=0.
M
10
M
1
M
10
{e
1
, e
2
, e
3
} {e
3
, e
4
, e
5
},
ÿâëÿåòñÿ îñòîâîì ãðàôà G(n, m) è åãî ìàòðèöà çàïîìèíàåò-
ñÿ, â ïðîòèâíîì ñëó÷àå ïîäãðàô íå îñòîâ è åãî ìàòðèöà íå
ó÷èòûâàåòñÿ. Ïðîöåññ çàâåðøàåòñÿ ïîñëå ïåðåáîðà âñåõ Cmn−1

ñî÷åòàíèé ñòîëáöîâ ìàòðèöû èíöèäåíòíîñòè.
    Âìåñòî ìàòðèöû èíöèäåíòíîñòè ìîæíî ñðàçó âçÿòü ìàò-
ðèöó B−i ðàçìåðà (n−1)×m , ïðåäñòàâëÿþùóþ ñîáîé ìàòðè-
öó èíöèäåíòíîñòè ñîîòâåòñòâóþùåãî îðãðàôà ñ óäàëåííîé i-é
ñòðîêîé, è âû÷èñëÿòü âñå åå ìèíîðû ïîðÿäêà n−1 .
     êà÷åñòâå ïðèìåðà ïîëó÷èì âñå îñòîâû ãðàôà G, èçîáðà-
æåííîãî íà ðèñ. 3.8 è èìåþùåãî ìàòðèöó èíöèäåíòíîñòè B.

                 v1 s    e1    sv2                 e1 e2 e3 e4 e5 
                                               v1 1 1 0 0 0
                                               v 1 0 1 1 0
               G e2       e3   e4          B = v2                 
                                                3 0 0 0 1 1
                 v4 s          sv3             v4 0 1 1 0 1
                         e5
                                     Ðèñ. 3.8

   Íèæå ïðèâåäåíà ìàòðèöà B−1 è âñå åå ìèíîðû òðåòüåãî
ïîðÿäêà (èõ ÷èñëî ðàâíî C53 =10 ):
                e1 e2 e3 e4 e5                  ¯ e1 e2 e3   ¯         ¯ e1 e2 e4   ¯
           "                   #
      v2       −1 0 1 1 0                       ¯−1 0 1      ¯         ¯−1 0 1      ¯
                                                ¯            ¯         ¯            ¯
B−1 = v3        0 0 0 −1 1 ,                    ¯ 0 0 0      ¯ =0 ,    ¯ 0 0−1      ¯ =1 ,
      v4        0 −1 −1 0 −1                    ¯ 0−1−1      ¯         ¯ 0−1 0      ¯
                                                    M1                      M2

¯ e1 e2 e5¯             ¯ e1 e3 e4¯         ¯ e1 e3 e5¯               ¯ e1 e4 e5¯
¯−1 0 0 ¯               ¯−1 1 1 ¯           ¯−1 1 0 ¯                 ¯−1 1 0 ¯
¯         ¯             ¯         ¯         ¯         ¯               ¯         ¯
¯ 0 0 1 ¯ = − 1,        ¯ 0 0−1 ¯ =1,       ¯ 0 0 1 ¯ = − 1,          ¯ 0−1 1 ¯ = − 1,
¯ 0−1−1 ¯               ¯ 0−1 0 ¯           ¯ 0−1−1 ¯                 ¯ 0 0−1 ¯
     M3                      M4                  M5                        M6

¯ e2 e3 e4¯             ¯ e2 e3 e5¯         ¯ e2 e4 e5¯               ¯ e3 e4 e5¯
¯ 0 1 1¯                ¯ 0 1 0¯            ¯ 0 1 0¯                  ¯ 1 1 0¯
¯         ¯             ¯         ¯         ¯         ¯               ¯         ¯
¯ 0 0−1 ¯ =1,           ¯ 0 0 1 ¯ = − 1,    ¯ 0−1 1 ¯ = − 1,          ¯ 0−1 1 ¯ =0.
¯−1−1 0 ¯               ¯−1−1−1 ¯           ¯−1 0−1 ¯                 ¯−1 0−1 ¯
     M7                      M8                  M9                        M10
   Ìèíîðû M1 è M10 ðàâíû 0, çíà÷èò, îñòîâíûå ïîäãðà-
ôû, îáðàçîâàííûå ìíîæåñòâàìè ðåáåð {e1 , e2 , e3 } è {e3 , e4 , e5 },
îñòîâàìè íå ÿâëÿþòñÿ, òîãäà êàê ïîäãðàôû, îïðåäåëÿåìûå ìè-


                                          52

Страницы