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

Определение:

Матрицей смежности (англ. Adjacency matrix) [math]A=||\alpha_{i,j}||[/math] невзвешенного графа [math]G=(V,E)[/math] называется матрица [math]A_{[V\times{}V]}[/math], в которой [math]\alpha_{i,j}[/math] — количество рёбер, соединяющих вершины [math]v_i[/math] и [math]v_j[/math], причём при [math]i=j[/math] каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.

Определение:

Матрицей смежности (англ. Adjacency matrix) [math]A=||\alpha_{i,j}||[/math] взвешенного графа [math]G=(V,E)[/math] называется матрица [math]A_{[V\times{}V]}[/math], в которой [math]\alpha_{i,j}[/math] — вес ребра, соединяющего вершины [math]v_i[/math] и [math]v_j[/math].

Примеры матриц смежности:

Взвешенность графа	Вид графа	Матрица смежности
Не взвешенный граф		[math]\begin{pmatrix} 0 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0\\ \end{pmatrix}[/math]
Взвешенный граф		[math]\begin{pmatrix} 0 & 40 & \infty & \infty & 18\\ 40 & 0 & 22 & 6 & 15\\ \infty & 22 & 0 & 14 & \infty \\ \infty & 6 & 14 & 0 & 20\\ 18 & 15 & \infty & 20 & 0 \\ \end{pmatrix}[/math]

Оценка памяти и времени работы

Матрица смежности занимает [math]O(|V|^2)[/math] памяти. За [math]O(1)[/math] можно определить вес ребра или его наличие между любыми двумя вершинами. Такой способ хранения графа хорошо подходит для плотных графов, в которых количество ребер примерно равно количеству вершин в квадрате.

Свойства

Утверждение:

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

Утверждение:

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

Утверждение (о сумме элементов строки матрицы смежности для ориентированного графа):

Сумма элементов [math]i[/math]-й строки равна [math]deg^- v_i[/math], то есть [math]\sum\limits_{j=1}^{n}\alpha_{i,j} = deg^- v_i[/math]. Аналогично сумма элементов [math]j[/math]-го стоблца равна [math]deg^+ v_j[/math], то есть [math]\sum\limits_{i=1}^{n}\alpha_{i,j} = deg^+ v_j[/math].

Утверждение (о сумме элементов строки матрицы смежности для неориентированного графа):

Матрица смежности является симметричной.

[math]\triangleright[/math]

Сумма элементов [math]i[/math]-й строки равна [math]deg \; v_i[/math], то есть [math]\sum\limits_{j=1}^{n}\alpha_{i,j} = deg \; v_i[/math]. Вследствие симметричности суммы элементов [math]i[/math]-й строки и [math]i[/math]-го столбца равны.

[math]\triangleleft[/math]

Теорема (Поиск количества путей длины [math]l[/math] с помощью матрицы смежность):

Пусть [math]A_{[V\times{}V]}=\alpha_{i,j}[/math] — матрица смежности ориентированного графа [math]G(V,E)[/math] без петель и [math]A^l=\gamma_{i,j}[/math], где [math]l\in\mathbb{N}[/math]. Тогда [math]\gamma_{i,j}[/math] равно количеству путей [math]v_i\leadsto{}v_j[/math] длины [math]l[/math].

Доказательство:

[math]\triangleright[/math]

Утверждение очевидно при [math]l = 1[/math]. Пусть [math]l \gt 1[/math], и утверждение верно для [math]l - 1[/math]. Тогда [math]A^{l-1}=\varepsilon_{i,j}[/math], где [math]\varepsilon_{i,j}[/math] равно количеству путей [math]v_i\leadsto{}v_j[/math] длины [math]l-1[/math]. Следовательно, [math]\gamma_{i,j}=\sum\limits_{s=1}^{n}{\varepsilon_{i,s}\alpha_{s,j}}[/math] равно числу путей [math]v_i\leadsto{}v_j[/math] длины [math]l[/math], так как каждый такой маршрут состоит из путей [math]v_i\leadsto{}v_s[/math] длины [math]l-1[/math] и ребра, ведущего из предпоследней вершины [math]v_s[/math] пути в его последнюю вершину [math]v_j[/math].

[math]\triangleleft[/math]

См. также

• Матрица инцидентности графа

Источники информации

• Харари Фрэнк Теория графов Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
• Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5