Пусть дан граф G(X,U), X = {xi}, i = 1, n;
U = {uj}, j = 1, m.
Матрицей смежностей графа G называется матрица A размерностью n n, в которой
1, если вершины xi и xj смежны
aij =
0, в противном случае
x2
G u1 u2
x1 u3 x3
u4 u5 u6
x5 u7 x4
Рис.4.17. Неориентированный граф
Для графа G, изображенного на рис.4.17, матрица A имеет следующий вид.
x1 x2 x3 x4 x5
x1 0 1 1 0 1
x2 1 0 1 0 0
A = x3 1 1 0 1 1
x4 0 0 1 0 1
x5 1 0 1 1 0
Поскольку граф G не ориентирован, то элементы матрицы смежностей симметричны относительно главной диагонали.
Матрицей инциденций графа G называется матрица B размерностью n m, в которой
1, если вершина xi и ребро uj инцидентны
bij =
0, в противном случае
Для графа G, изображенного на рис.4.17, матрица B имеет следующий вид.
u1 u2 u3 u4 u5 u6 u7
x1 1 0 1 1 0 0 0
x2 1 1 0 0 0 0 0
x3 0 1 1 0 1 1 0
x4 0 0 0 0 0 1 1
x5 0 0 0 1 1 0 1
