Графу G(X,U), имеющему n вершин, можно поставить в соответствие квадратную матрицу R=║rij║nxn, элементы которой rij соответствуют числу ребер, соединяющих вершину xi с вершиной xj. Это матрица смежности. Она задает в числовом виде связь смежных вершин. Элемент riiопределяет число петель вершины xi.
Для графа, представленного на рис. 1.11 матрица смежности записывается в виде:
R =
x1
x 2
x 3
x 4
x 5
x1
x2
x3
x4
x5
Матрица смежности обладает следующими свойствами:
- симметрична относительно диагонали;
- сумма элементов в строке или столбце равна степени вершины.
Матрица инцидентности S=║sij║nxm -матрица, строки которой соответствуют вершинам графа G(X,U), столбцы – его ребрам:
, если i вершина инцидентна j-му ребру uj;
, если iвершина не инцидентна j-му ребру uj;
где n– число вершин графа (n = card X);
m– число ребер графа (m = card U).
Для графа G(рис. 1.11) матрица инцидентностиимеет вид:
U1
U2
U3
U4
U5
U6
U7
x1
S=
x2
x3
x4
x5
В общем случае S не квадратная матрица. В каждом столбце матрицы S имеется две единицы, так как каждое ребро соединяет 2 вершины. Матрицы R и S однозначно задают информацию о графе.
