Матрица смежности
Матрица смежности — один из способов представления графа в виде матрицы.
Определение
Матрица смежности графа [math]\displaystyle{ G }[/math] с конечным числом вершин [math]\displaystyle{ n }[/math] (пронумерованных числами от 1 до [math]\displaystyle{ n }[/math]) — это квадратная целочисленная матрица [math]\displaystyle{ \mathbf A }[/math] размера [math]\displaystyle{ n \times n }[/math], в которой значение элемента [math]\displaystyle{ a_{i,j} }[/math] равно числу рёбер из [math]\displaystyle{ i }[/math]-й вершины графа в [math]\displaystyle{ j }[/math]-ю вершину.
Иногда, особенно в случае неориентированного графа, петля (ребро из [math]\displaystyle{ i }[/math]-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента [math]\displaystyle{ a_{i,i} }[/math] в этом случае равно удвоенному числу петель вокруг [math]\displaystyle{ i }[/math]-й вершины.
Матрица смежности простого графа (не содержащего петель и кратных рёбер) является бинарной матрицей и содержит нули на главной диагонали.
Матрица смежности двудольного графа
Матрица смежности [math]\displaystyle{ \mathbf A }[/math] двудольного графа, доли которого имеют [math]\displaystyle{ r }[/math] и [math]\displaystyle{ s }[/math] вершин, может быть записана в следующем виде
- [math]\displaystyle{ \mathbf A = \begin{pmatrix} \mathbf 0_{r,r} & \mathbf B \\ \mathbf B^T & \mathbf 0_{s,s} \end{pmatrix}, }[/math]
где [math]\displaystyle{ \mathbf B }[/math] является [math]\displaystyle{ r \times s }[/math] матрицей, а [math]\displaystyle{ \mathbf 0_{r,r} }[/math] и [math]\displaystyle{ \mathbf 0_{s,s} }[/math] представляют [math]\displaystyle{ r \times r }[/math] и [math]\displaystyle{ s \times s }[/math] нулевые матрицы. В этом случае меньшая матрица [math]\displaystyle{ \mathbf B }[/math] единственным образом представляет граф, а оставшиеся части матрицы [math]\displaystyle{ \mathbf A }[/math] можно отбросить. [math]\displaystyle{ \mathbf B }[/math] иногда называется матрицей бисмежности.
Формально, пусть [math]\displaystyle{ G = (U, V, E) }[/math] будет двудольным графом с долями [math]\displaystyle{ U = \{u_1, \dots, u_r\} }[/math] и [math]\displaystyle{ V = \{v_1, \dots, v_s\} }[/math]. Бисопряжённая матрица является [math]\displaystyle{ r \times s }[/math] 0–1 матрицей [math]\displaystyle{ \mathbf B }[/math], в которой [math]\displaystyle{ b_{i,j} = 1 }[/math] тогда и только тогда, когда [math]\displaystyle{ (u_i, v_j) \in E }[/math].
Если [math]\displaystyle{ G }[/math] является двудольным мультиграфом или взвешенным графом, то элементами [math]\displaystyle{ b_{i,j} }[/math] будет число рёбер между вершинами или веса рёбер [math]\displaystyle{ (u_i, v_j) }[/math] соответственно.
Примеры
- Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности [math]\displaystyle{ \mathbf A }[/math]. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент [math]\displaystyle{ a_{1,1} }[/math] может считаться равным либо одному (как показано ниже), либо двум.
Граф Матрица смежности 
[math]\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} }[/math]
- [math]\displaystyle{ a_{i,j} }[/math]— число рёбер, связывающих вершины [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ v_j }[/math], причём в некоторых приложениях каждая петля (ребро [math]\displaystyle{ \{v_i, v_i\} }[/math] при некотором [math]\displaystyle{ i }[/math]) учитывается дважды.
- Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.
Свойства
Матрица смежности неориентированного графа симметрична, а значит обладает действительными собственными значениями и ортогональным базисом из собственных векторов. Набор её собственных значений называется спектром графа, и является основным предметом изучения спектральной теории графов.
Два графа [math]\displaystyle{ G_1 }[/math] и [math]\displaystyle{ G_2 }[/math] с матрицами смежности [math]\displaystyle{ \mathbf A_1 }[/math] и [math]\displaystyle{ \mathbf A_2 }[/math] являются изоморфными тогда и только тогда, когда существует перестановочная матрица [math]\displaystyle{ \mathbf P }[/math], такая что
- [math]\displaystyle{ \mathbf P \mathbf A_1 \mathbf P^{-1} = \mathbf A_2 }[/math] .
Из этого следует, что матрицы [math]\displaystyle{ \mathbf A_1 }[/math] и [math]\displaystyle{ \mathbf A_2 }[/math] подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны (это бывает в случае, если матрица [math]\displaystyle{ \mathbf P }[/math] не является перестановочной, например, матрицы [math]\displaystyle{ \begin{pmatrix}0 &1\\ 0& 0\end{pmatrix} }[/math] и [math]\displaystyle{ \begin{pmatrix}0 &2\\ 0& 0\end{pmatrix} }[/math] являются подобными, но соответствующие им графы не изоморфны).
Степени матрицы
Если [math]\displaystyle{ \mathbf A }[/math] — матрица смежности графа [math]\displaystyle{ G }[/math], то матрица [math]\displaystyle{ \mathbf A^m }[/math] обладает следующим свойством: элемент в [math]\displaystyle{ i }[/math]-й строке, [math]\displaystyle{ j }[/math]-м столбце равен числу путей из [math]\displaystyle{ i }[/math]-й вершины в [math]\displaystyle{ j }[/math]-ю, состоящих из ровно [math]\displaystyle{ m }[/math] ребер.
Структура данных
Матрица смежности и списки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах.
Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно [math]\displaystyle{ n^2 }[/math] бит памяти, что может быть на порядок лучше списков смежности.
В алгоритмах, работающих со взвешенными графами (например, в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих рёбер. При этом на место отсутствующих рёбер ставят некоторое специальное граничное значение (англ. sentinel), зависящее от решаемой задачи, обычно 0 или [math]\displaystyle{ \infty }[/math].
См. также
Литература
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.