2.3 Матрица смежности

Матрица смежности — один из способов представления графа в виде матрицы. Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i-й вершины графа в j-ю вершину. Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a_ii в этом случае равно удвоенному числу петель вокруг i-й вершины.

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

• Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

• Матрица смежности полного графа Kn содержит единицы во всех своих элементах, кроме главной диагонали, на которой расположены нули.

• Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

• Матрица смежности неориентированного графа симметрична, а значит обладает действительными собственными значениями и ортогональным базисом из собственных векторов. Набор её собственных значений называется спектром графа, и является основным предметом изучения спектральной теории графов.

Два графа G₁ и G₂ с матрицами смежности A₁ и A₂ являются изоморфными если и только если существует перестановочная матрица P, такая что

PA₁P^-1 = A₂.

Из этого следует, что матрицы A₁ и A₂ подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны.

Степени матрицы.

Если A — матрица смежности графа G, то матрица A_m обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.