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

Определение

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

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

Ссылки