Матричное задание графа

x₄

x₃

x₁

x₂

Рис.15

Матрицей смежности графа G(X, Г) , содержащего n вершин называется квадратная матрица , в которой элементы a_ij равны количеству дуг, идущих из вершины i в вершину j. По матрице смежности можно определять полустепени исхода и захода, а также степень любой вершины (рис.15)

Транспонированная матрица А служит матрицей смежности графа, который отличается от исходного ориентацией дуг (рис.16)

- строки меняются столбцами

x₄

x₁

x₃

x₂

Рис.16

Дополнительная матрица графа G(X, Г) представляет собой квадратную матрицу , которая получается из матрицы смежности А путем замены 0 на 1, а всех остальных значащих цифр на 0.

Дополнительная матрица соответствует некоторому новому графу G(X, Г’), отображение каждой вершины которого определяется выражением .

Проверим формулу

x₄

Возьмем, например

x₁

x₃

Всё совпадает.

x₂

Рис.17

Свойства матрицы смежности

1. Матрица смежности симметрична относительно главной диагонали, если соответствующий ей граф симметричен. Для симметричного графа матрица смежности равна транспонированной матрице

2. Матрица смежности полная, если сумма двух ее симметрично расположенных относительно главной диагонали элементов больше нуля и одинакова

Матрица смежности полная, когда соответствующий ей граф полный (рис.18)

x₂

x₁ x₃

x₄

Рис.18

По полной матрице можно определить степень вершины.

, где n – число вершин. Пример: .

3. Матрица смежности имеет на диагонали 1, если все вершины графа имеют петли.

4. Две матрицы смежности А и В, которые соответствуют графам G₁(X,U) и G₂(X,V) могут быть проссумированы, если они одного и того же размера.

5. Две матрицы смежности А и В, соответствующие графам G₁ и G₂, могут быть перемножены в том случае, если они согласованы для умножения.

6. Матрица смежности может быть возведена в степень , что соответствует умножению . Сумма элементов j-го столбца матрицы смежности указывает на общее количество нулей длиной , заходящих в вершину , а сумма элементов i-ой строки на общее количество нулей длиной , выходящих из вершины .

Матрица инциденций. Пусть задан граф G с n вершинами и m дугами. Матрица инциденций определяется следующим образом:

1. , если вершина является началом дуги ;

2. , если вершина является концом дуги _;

3. , если дуга не инцидентна вершине или является петлей.

Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец матрицы инциденций содержит один элемент равный 1, и один элемент равный -1. Петлям соответствуют нулевые столбцы.

x₂

a₂

x₁ a₄

a₁

a₃

x3

Рис.19