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

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

Определение

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

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

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

Матрица смежности двудольного графа[править | править код]

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

\mathbf {A} ={\begin{pmatrix}\mathbf {0} _{r,r}&\mathbf {B} \\\mathbf {B} ^{T}&\mathbf {0} _{s,s}\end{pmatrix}},

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

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

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

Примеры

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

Граф	Матрица смежности
	${\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}}$

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

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

Свойства

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

Два графа $G_{1}$ и $G_{2}$ с матрицами смежности $\mathbf {A} _{1}$ и $\mathbf {A} _{2}$ являются изоморфными тогда и только тогда, когда существует перестановочная матрица $\mathbf {P}$ , такая что

\mathbf {P} \mathbf {A} _{1}\mathbf {P} ^{-1}=\mathbf {A} _{2}

.

Из этого следует, что матрицы $\mathbf {A} _{1}$ и $\mathbf {A} _{2}$ подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны (это бывает в случае, если матрица $\mathbf {P}$ не является перестановочной, например, матрицы ${\begin{pmatrix}0&1\\0&0\end{pmatrix}}$ и ${\begin{pmatrix}0&2\\0&0\end{pmatrix}}$ являются подобными, но соответствующие им графы не изоморфны).

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

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

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

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

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

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

См. также

Литература

Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Ссылки

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