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

Матрица смежности — это один из способов представления графа в виде квадратной таблицы, где строки и столбцы соответствуют вершинам графа, а элемент на пересечении i-й строки и j-го столбца указывает на наличие или отсутствие ребра между вершинами i и j. Матрица смежности является фундаментальным понятием теории графов и широко используется в компьютерных науках, дискретной математике, анализе сетей и других областях, где требуется компактное и удобное для алгоритмической обработки описание структуры связей.

Определение и формальное описание

Пусть дан граф \( G = (V, E) \), где \( V \) — множество вершин, а \( E \) — множество рёбер. Матрица смежности \( A \) — это квадратная матрица размера \( |V| \times |V| \), в которой элемент \( a_{ij} \) определяется следующим образом:

• Для невзвешенного графа: \( a_{ij} = 1 \), если существует ребро, соединяющее вершины \( i \) и \( j \); и \( a_{ij} = 0 \) в противном случае.
• Для взвешенного графа: \( a_{ij} \) равен весу ребра между вершинами \( i \) и \( j \); если ребра нет, то \( a_{ij} = 0 \) или специальное значение (например, бесконечность), в зависимости от контекста.
• Для неориентированного графа матрица симметрична относительно главной диагонали: \( a_{ij} = a_{ji} \).
• Для ориентированного графа (орграфа) матрица, как правило, несимметрична: \( a_{ij} = 1 \) означает наличие дуги от вершины \( i \) к вершине \( j \).

В случае мультиграфа, где между двумя вершинами может быть несколько рёбер, элемент \( a_{ij} \) может быть равен числу таких рёбер. Для графов с петлями (ребро, соединяющее вершину саму с собой) элемент \( a_{ii} \) может быть равен 1 или числу петель.

Свойства

Матрица смежности обладает рядом важных свойств, которые делают её удобным инструментом для анализа графов:

• Симметричность: для неориентированных графов матрица всегда симметрична.
• След матрицы: след матрицы (сумма элементов на главной диагонали) равен удвоенному числу петель в графе (для неориентированных графов) или числу петель (для ориентированных).
• Степень вершины: в неориентированном графе степень вершины \( i \) равна сумме элементов i-й строки (или i-го столбца). В ориентированном графе полустепень исхода равна сумме i-й строки, а полустепень захода — сумме i-го столбца.
• Степени матрицы: элемент \( (A^k)_{ij} \) матрицы \( A^k \) (k-я степень матрицы смежности) равен числу путей длины \( k \) от вершины \( i \) к вершине \( j \). Это свойство широко используется в алгоритмах поиска путей и анализа связности.
• Собственные значения и векторы: спектр матрицы смежности (набор собственных значений) связан с такими характеристиками графа, как его регулярность, число компонент связности, наличие клик и другие. Спектральная теория графов опирается на анализ собственных значений матрицы смежности.
• Связь с матрицей Лапласа: матрица Лапласа графа определяется как \( L = D - A \), где \( D \) — диагональная матрица степеней вершин. Матрица Лапласа используется для изучения связности, разреза графа и в спектральной кластеризации.

Виды и варианты

Матрица смежности может быть модифицирована для различных типов графов и задач:

• Взвешенная матрица смежности: вместо 0 и 1 содержит веса рёбер. Используется для представления сетей с расстояниями, пропускными способностями, стоимостью и т.д.
• Матрица смежности для мультиграфов: элемент \( a_{ij} \) равен числу параллельных рёбер между вершинами.
• Матрица инцидентности: альтернативное представление графа, где строки соответствуют вершинам, а столбцы — рёбрам. В отличие от матрицы смежности, она не является квадратной.
• Список смежности: более компактное представление для разреженных графов, где для каждой вершины хранится список смежных с ней вершин. Матрица смежности, напротив, эффективна для плотных графов.

Применение

Матрица смежности находит применение в самых разных областях:

• Компьютерные науки: реализация алгоритмов на графах (поиск в ширину и глубину, алгоритм Дейкстры, алгоритм Флойда — Уоршелла, алгоритм Прима и Краскала). Матричное представление позволяет использовать эффективные библиотеки линейной алгебры (например, BLAS, LAPACK) для ускорения вычислений.
• Анализ социальных сетей: матрица смежности описывает связи между пользователями. Анализ её спектра позволяет выявлять сообщества, центральные узлы и структуру сети.
• Транспортные и логистические сети: представление карт дорог, маршрутов авиаперелётов, электрических сетей. Взвешенная матрица смежности используется для расчёта кратчайших путей и оптимальных потоков.
• Биоинформатика: моделирование взаимодействий белков, метаболических путей, нейронных сетей. Матрица смежности позволяет анализировать структуру биологических систем.
• Теория кодирования и связь: графы состояний кодеров, коды с исправлением ошибок.
• Химия: представление молекулярных структур, где вершины — атомы, а рёбра — химические связи. Матрица смежности используется для вычисления индексов подобия и прогнозирования свойств.

Преимущества и недостатки

Преимущества

• Простота реализации и интуитивность.
• Возможность проверки наличия ребра за время \( O(1) \) (доступ к элементу по индексу).
• Удобство для выполнения матричных операций (сложение, умножение, возведение в степень).
• Эффективность для плотных графов, где число рёбер близко к \( |V|^2 \).

Недостатки

• Высокая потребность в памяти: \( O(|V|^2) \), что делает её непригодной для очень больших разреженных графов (например, веб-граф с миллиардами вершин).
• Для разреженных графов (где число рёбер \( |E| \ll |V|^2 \)) хранение матрицы приводит к значительному расходу памяти на нулевые элементы.
• Операции перебора всех соседей вершины требуют \( O(|V|) \) времени, что может быть неэффективно по сравнению со списками смежности.

Пример

Рассмотрим неориентированный граф с тремя вершинами (1, 2, 3) и рёбрами: между 1 и 2, между 2 и 3. Матрица смежности \( A \) будет иметь вид:

\[ A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \]

Здесь \( a_{12} = a_{21} = 1 \), \( a_{23} = a_{32} = 1 \), остальные элементы равны 0. Степени вершин: вершина 1 — 1, вершина 2 — 2, вершина 3 — 1. Квадрат матрицы \( A^2 \) даёт число путей длины 2: например, \( (A^2)_{13} = 1 \) (путь 1-2-3).

Альтернативные представления

Помимо матрицы смежности, существуют другие распространённые способы представления графов:

• Список смежности: для каждой вершины хранится список её соседей. Эффективен по памяти для разреженных графов, но проверка наличия ребра может занимать \( O(\deg(v)) \) времени.
• Матрица инцидентности: размер \( |V| \times |E| \), где элемент равен 1, если вершина инцидентна ребру. Используется реже из-за больших размеров.
• Рёберный список: простое перечисление всех рёбер в виде пар вершин. Компактен, но неудобен для быстрого доступа.

Выбор представления зависит от плотности графа, требуемых операций и доступной памяти.

Источники

• Харари Ф. Теория графов. — М.: Мир, 1973.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Дистель Р. Теория графов. — Новосибирск: Изд-во Института математики, 2002.
• Богарт К. П., Штейн К. Дискретная математика для компьютерных наук. — М.: Бином, 2015.