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

UptoLike

ВУЗ: 

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

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

Рубрика: 

12
Степенью (валентностью) вершины
i
x неориентиро-
ванного графа
G называется число ребер )(
i
x
σ
, инцидентных
данной вершине. Таблица степеней вершин данного графа имеет
вид:
i
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
)(
i
x
σ
3 3 3 4 2 3 2
Матрицей смежности
)(GA
неориентированного графа
G называется матрица размерности nn
×
, элементы которой
определяются следующим образом:
⎩
⎨
⎧
=
.0
,,1
случае противном в
смежны и вершины если
ji
ij
xx
a
Матрица смежности для данного графа имеет вид:
24
a
14
a
344
ax
1
x
2
x
3
x
6
x
5
x
7
x
G
12
a
23
a
15
a
37
a
56
a
46
a
67
a
                           G

                           x2
               a12                         a 23
     x1                         a 24              x3

                     a14       x 4 a34
    a15                           a 46            a37



          x5         a56   x6       a 67     x7


      Степенью (валентностью) вершины xi неориентиро-
ванного графа G называется число ребер σ ( xi ) , инцидентных
данной вершине. Таблица степеней вершин данного графа имеет
вид:
   xi      x1    x2      x3     x4     x5         x6     x7
 σ ( xi )  3      3      3       4      2         3      2
        Матрицей смежности A(G ) неориентированного графа
G называется матрица размерности n × n , элементы которой
определяются следующим образом:
      ⎧1, если вершины xi и x j смежны,
aij = ⎨
      ⎩0 в противном случае.
        Матрица смежности для данного графа имеет вид:

                                             12

Страницы