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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Матрица смежности — один из способов представления графа в виде матрицы.

Определение[править | править исходный текст]

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

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

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

Примеры[править | править исходный текст]

  • Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент a_{11} может считаться равным либо одному (как показано ниже), либо двум.
Граф Матрица смежности
6n-graph2.svg \begin{pmatrix}
1 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{pmatrix}
  • aij — число рёбер, связывающих вершины v_i и v_j, причем в некоторых приложениях каждая петля (ребро \{v_i, v_i\} при некотором i) учитывается дважды.
  • Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

Свойства[править | править исходный текст]

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

Два графа G1 и G2 с матрицами смежности A1 и A2 являются изоморфными если и только если существует перестановочная матрица P, такая что

PA1P-1 = A2.

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

Степени матрицы[править | править исходный текст]

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

Структура данных[править | править исходный текст]

Матрица смежности и списки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах

Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно n^2 бит памяти, что может быть на порядок лучше списков смежности.

В алгоритмах, работающих со взвешенными графами (например, в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих ребер. При этом на место отсутствующих ребер ставят некоторое специальное граничное значение (англ. sentinel), зависящее от решаемой задачи, обычно 0 или \infty.

См. также[править | править исходный текст]

Литература[править | править исходный текст]

Ссылки[править | править исходный текст]