Матричное представление графа

Для задания структуры графа удобно использовать матрицы следующих видов:

1. Матрицу смежности

Она квадратная, n-го порядка, обозначается A=[a_ij]

Элементы матрицы определяются из условия:

- a_ij = 1, если в графе есть дуга (x_i x_j)

- a_{i j}= 0, если в графе нет дуги (x_i x_j).

Например, для графа, изображенного на рисунке,

имеем следующую матрицу смежности

Эта матрица полностью определяет структуру графа:

Сумма всех элементов строки x_{i i} дает полустепень исхода вершины x_i. Сумма элементов столбца x_i дает полустепень захода вершины x_i.

Множество столбцов, имеющих единицы в строках x_i, соответствует множеству Г(x_i).

Множество строк, которые имеют единицы в столбце x_i,соответствует множеству Г^-1(x_i)

2. Матрицу инциденций.

Эта матрица размерностью n×m, обозначается B=[b_ij].

Элементы матрицы определяются следующим образом:

- b_ij= 1, если x_i - начальная вершина дуги a_j;

- b_ij=-1, если x_i - конечная вершина дуги a_j;

- b_ij= 0, если x_i не является концевой вершиной дуги a_j или дуга a_j является петлей.

Например, для графа, изображенного на рисунке,

Имеем следующую матрицу инциденций:

Если граф неориентированный, то его матрица инциденции определяется так же как и для ориентированного графа, за исключением того, что все элементы равные «-1» заменяются на «+1»