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

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

Определение

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

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

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

Матрица смежности двудольного графа

Матрица смежности $𝐀$ двудольного графа, доли которого имеют $r$ и $s$ вершин, может быть записана в следующем виде

$𝐀=\left(\begin{array}{cc}{\mathrm{𝟎}}_{r,r}& 𝐁\\ {𝐁}^T& {\mathrm{𝟎}}_{s,s}\end{array}\right),$

где $𝐁$ является $r\times s$ матрицей, а ${\mathrm{𝟎}}_{r,r}$ и ${\mathrm{𝟎}}_{s,s}$ представляют $r\times r$ и $s\times s$ нулевые матрицы. В этом случае меньшая матрица $𝐁$ единственным образом представляет граф, а оставшиеся части матрицы $𝐀$ можно отбросить. $𝐁$ иногда называется матрицей бисмежности.

Формально, пусть $G=(U,V,E)$ будет двудольным графом с долями $U=\{u_1,\dots ,u_r\}$ и $V=\{v_1,\dots ,v_s\}$. Бисопряжённая матрица является $r\times s$ 0–1 матрицей $𝐁$, в которой $b_{i,j}=1$ тогда и только тогда, когда $(u_i,v_j)\in E$.

Если $G$ является двудольным мультиграфом или взвешенным графом, то элементами $b_{i,j}$ будет число рёбер между вершинами или веса рёбер $(u_i,v_j)$ соответственно.

Примеры

• Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности $𝐀$. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент $a_{1,1}$ может считаться равным либо одному (как показано ниже), либо двум.

Граф	Матрица смежности
	$\left(\begin{array}{cccccc}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{array}\right)$

• $a_{i,j}$— число рёбер, связывающих вершины $v_i$ и $v_j$, причём в некоторых приложениях каждая петля (ребро $\{v_i,v_i\}$ при некотором $i$) учитывается дважды.

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

Свойства

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

Два графа $G_1$ и $G_2$ с матрицами смежности ${𝐀}_1$ и ${𝐀}_2$ являются изоморфными тогда и только тогда, когда существует перестановочная матрица $𝐏$, такая что

$𝐏{𝐀}_1{𝐏}^{-1}={𝐀}_2$ .

Из этого следует, что матрицы ${𝐀}_1$ и ${𝐀}_2$ подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны (это бывает в случае, если матрица $𝐏$ не является перестановочной, например, матрицы $\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ и $\left(\begin{array}{cc}0& 2\\ 0& 0\end{array}\right)$ являются подобными, но соответствующие им графы не изоморфны).

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

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

Структура данных

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

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

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

См. также

• Список рёбер
• Матрица инцидентности

Литература

• Шаблон:Книга:CLRS

Ссылки

• Матрица смежности графа. Код программ на Паскаль и C++