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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G A
deg
+
v
i
deg
−
v
i
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
s
v
6
s
]
+
-
O
-
O
q
I
v
1
v
2
v
3
v
4
v
5
v
6
deg
+
v
i
A =
v
1
v
2
v
3
v
4
v
5
v
6
0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 0 0
1 0 0 0 0 1
0 0 0 1 1 0
2
2
2
1
2
2
deg
−
v
i
2 2 2 3 1 1
(v
i
, v
j
)
(v
j
, v
i
)
P
n
j=1
a
i,j
= deg
+
v
i
, i=1, n
P
n
i=1
a
i,j
= deg
−
v
j
, j=1 , n
P
n
i=1
P
n
j=1
a
i,j
= m.
B=[b
i,j
] n×m,
b
i,j
=
(
1 , v
i
a
j
;
−1 , v
i
a
j
;
0 , v
i
a
j
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
a
11
B =
v
1
v
2
v
3
v
4
v
5
v
6
1 1 0 0 −1 0 0 −1 0 0 0
0 −1 1 0 1 −1 0 0 0 0 0
0 0 −1 −1 0 1 1 0 0 0 0
−1 0 0 1 0 0 −1 0 −1 0 0
0 0 0 0 0 0 0 1 0 1 −1
0 0 0 0 0 0 0 0 1 −1 1
ñòàâëåíû îðãðàô G , åãî ìàòðèöà ñìåæíîñòè A è äâå ñòåïåí-
íûå ïîñëåäîâàòåëüíîñòè deg+ vi è deg− vi .
            -                               v1   v2   v3   v4   v5   v6 deg+ vi
                                                                      
                               v1           0    1    0    1    0    0    2
                               v2          1    0    1    0    0    0 2
   v1 s vs s- s+
               v3 s v4         v           0    1    0    1    0    0
      ]
         2
                          A= 3                                       2
            O                  v4          0    0    1    0    0    0
      O                                                                1
                               v5           1    0    0    0    0    1    2
           s qs                v6           0    0    0    1    1    0    2
        v5 I  v6
                               deg− vi 2 2 2 3 1 1

                       Ðèñ. 1.16
   Èç îïðåäåëåíèÿ ñëåäóåò (ïðèìåð ïîäòâåðæäàåò ýòî), ÷òî:
    â îáùåì ñëó÷àå ìàòðèöà íå ñèììåòðè÷íà, òàê êàê íàëè-
÷èå äóãè (vi , vj ) ñîâñåì íå îçíà÷àåò, ÷òî â ãðàôå ïðèñóòñòâóåò
òàêæå è îáðàòíàÿ äóãà (vj , vi ) ;
    êîëè÷åñòâî åäèíèö â ëþáîé P        ñòðîêå ðàâíî ïîëóñòåïåíè
                                          n             +
èñõîäà ñîòâåòñòâóþùåé âåðøèíû:            j=1 ai,j = deg vi , i=1, n ;
    êîëè÷åñòâî åäèíèö â ëþáîì ñòîëáöå Pn          ðàâíî ïîëóñòåïåíè
                                                        −
çàõîäà ñîòâåòñòâóþùåé âåðøèíû:            i=1 ai,j = deg vj , j=1, n ;
    îáùåå
       Pn êîëè÷åñòâî
               Pn             åäèíèö â ìàòðèöå ðàâíî ÷èñëó äóã â
ãðàôå:    i=1      j=1 ai,j = m.
     Ìàòðèöà èíöèäåíòíîñòè îðãðàôà îïðåäåëÿåòñÿ êàê ïðÿ-
ìîóãîëüíàÿ
      (      ìàòðèöà B=[bi,j ] ðàçìåðà n×m, â êîòîðîé
         1 , åñëè vi ÿâëÿåòñÿ íà÷àëüíîé âåðøèíîé äóãè aj ;
bi,j = −1 , åñëè vi ÿâëÿåòñÿ êîíå÷íîé âåðøèíîé äóãè aj ;
         0 , åñëè âåðøèíà vi è äóãà aj íå èíöèäåíòíû.
 ñîîòâåòñòâèè ñ ýòèì îïðåäåëåíèåì ìàòðèöà èíöèäåíòíîñòè,
íàïðèìåð äëÿ ãðàôà íà ðèñ. 1.16, èìååò âèä:
                    a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
                                                    
           v1       1 1 0 0 −1 0 0 −1 0 0 0
           v2     0 −1 1 0 1 −1 0 0 0 0 0 
           v      0 0 −1 −1 0 1 1 0 0 0 0 
       B = v3                                       
             4    −1 0 0 1 0 0 −1 0 −1 0 0 
                                                    
           v5       0 0 0 0 0 0 0 1 0 1 −1
           v6       0 0 0 0 0 0 0 0 1 −1 1



                                   25

Страницы