Дискретная математика. Сергиевская И.М. - 13 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

13
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
0100100
1011000
0100001
0100111
1001010
0001101
0011010
.
Матрицей инцидентности
)(GB
неориентированного
графа
G с n вершинами и m ребрами называется матрица
размерности
mn ×
, элементы которой определяются сле-
дующим образом:
⎪
⎩
⎪
⎨
⎧
=
.0
,,1
петля - если или случае противном в
ребру инцидентнавершина если
j
ji
ij
a
ax
b
В графе
G обозначим ребро, соединяющее вершины
i
x и
j
x , через
ij
a (два индекса использовать удобнее). Так, напри-
мер, ребро
23
a инцидентно вершинам
2
x и
3
x . Матрица инци-
дентности для нашего графа имеет вид:
12
a
14
a
15
a
23
a
24
a
34
a
37
a
46
a
56
a
67
a
1
x
1 1 1 0 0 0 0 0 0 0
2
x
1 0 0 1 1 0 0 0 0 0
3
x
0 0 0 1 0 1 1 0 0 0
4
x
0 1 0 0 1 1 0 1 0 0
5
x
0 0 1 0 0 0 0 0 1 0
6
x
0 0 0 0 0 0 0 1 1 1
7
x
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
0 0 0 0 0 0 1 0 0 1
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
Обозначения вершин и ребер графа не включаются в
матрицу инцидентности, а записаны только для удобства. 
⎛0    1     0 1 1 0 0⎞
⎜                         ⎟
⎜1    0     1 1 0 0 0⎟
⎜0    1     0 1 0 0 1⎟
⎜                         ⎟
⎜1    1     1 0 0 1 0⎟ .
⎜1    0     0 0 0 1 0 ⎟⎟
⎜
⎜0    0     0 1 1 0 1⎟
⎜                         ⎟
⎝0    0     1 0 0 1 0⎠
           Матрицей инцидентности B(G ) неориентированного
графа G с n вершинами и m ребрами называется матрица
размерности n × m , элементы которой определяются сле-
дующим образом:
       ⎧⎪1, если вершина xi инцидентна ребру a j ,
bij = ⎨
        ⎪⎩0 в противном случае или если a j - петля.
           В графе G обозначим ребро, соединяющее вершины xi и
x j , через aij (два индекса использовать удобнее). Так, напри-
мер, ребро a 23 инцидентно вершинам x 2 и x3 . Матрица инци-
дентности для нашего графа имеет вид:
            a12 a14 a15 a 23 a 24 a 34 a37 a 46 a 56 a67

     x1⎛    1   1   1     0   0   0    0   0    0   0  ⎞
       ⎜                                               ⎟
     x2⎜    1   0   0     1   1   0    0   0    0   0  ⎟
     x3⎜    0   0   0     1   0   1    1   0    0   0  ⎟
       ⎜                                               ⎟
   x4 ⎜     0   1   0     0   1   1    0   1    0   0  ⎟
   x5  ⎜    0   0   1     0   0   0    0   0    1   0  ⎟
       ⎜                                               ⎟
   x6 ⎜     0   0   0     0   0   0    0   1    1   1  ⎟
   x7  ⎜    0   0   0     0   0   0    1   0    0   1  ⎟
       ⎝                                               ⎠
      Обозначения вершин и ребер графа не включаются в
матрицу инцидентности, а записаны только для удобства.
                              13

Страницы