Введение

Квадратная матрица, используемая для представления графа или сети. В теории графов и информатике матрица смежности — это квадратная матрица, используемая для представления конечного графа. Элементы матрицы указывают, соединены ли пары вершин в графе или нет. В частном случае конечного простого графа матрица смежности является (0,1)-матрицей с нулями на главной диагонали. Если граф неориентированный (то есть все его ребра двунаправленные), матрица смежности симметрична. Связь между графом и собственными значениями и собственными векторами его матрицы смежности изучается в спектральной теории графов. Матрицу смежности графа следует отличать от матрицы инцидентности, другого матричного представления, элементы которого указывают, инцидентны ли пары вершина-ребро, и от матрицы степеней, которая содержит информацию о степени каждой вершины.

Определение

Для простого графа с множеством вершин , матрица смежности — это квадратная матрица A размера n × n, где элемент Aij равен единице, если существует ребро от вершины ui к вершине uj, и нулю, если ребра нет. Все диагональные элементы матрицы равны нулю, поскольку в простых графах не допускаются ребра от вершины к самой себе (петли). В алгебраической теории графов также бывает полезно заменять ненулевые элементы алгебраическими переменными. Та же концепция может быть расширена на мультиграфы и графы с петлями, сохраняя в соответствующем элементе матрицы количество ребер между каждой парой вершин и допуская ненулевые диагональные элементы. Петли можно считать либо один раз (как одно ребро), либо дважды (как два инцидента ребра и вершины), при условии соблюдения единой конвенции. Неориентированные графы часто используют вторую конвенцию, при которой петли считаются дважды, а ориентированные графы обычно используют первую.

Вариации

Матрица смежности A простого графа имеет значение a, если (i, j) является ребром, b, если это не так, и c на диагонали. Матрица смежности Зейделя – это матрица смежности особого вида. Эта матрица используется при изучении сильно регулярных графов и пар графов. Матрица расстояний содержит в позиции (i, j) расстояние между вершинами vi и vj. Расстояние определяется как длина кратчайшего пути, соединяющего эти вершины. Если длины ребер явно не заданы, длина пути считается равной количеству ребер в нем. Матрица расстояний похожа на высокую степень матрицы смежности, но вместо того, чтобы указывать только наличие или отсутствие соединения между двумя вершинами (то есть, матрица связности, содержащая булевы значения), она предоставляет точное расстояние между ними.

Ненаправленные графики

Здесь (для ненаправленных графов) принято, что каждое ребро добавляет 1 к соответствующей ячейке матрицы, а каждая петля добавляет 2. Это позволяет легко определить степень вершины, сложив значения в соответствующей строке или столбце матрицы смежности. Граф с метками. Матрица смежности. Координаты 1–6. Граф Науру. Координаты 0–23. Белые поля обозначают нули, цветные – единицы.

Тривиальные графики

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

Спектр

Матрица смежности ненаправленного простого графа симметрична, и поэтому имеет полный набор вещественных собственных значений и ортогональный базис собственных векторов. Множество собственных значений графа называется спектром графа. Обычно собственные значения обозначают величиной λ.

Наибольшее собственное значение λ₁ ограничено сверху максимальной степенью графа. Это можно увидеть как следствие теоремы Перрона — Фробениуса, но его можно доказать и проще. Пусть v — собственный вектор, соответствующий λ₁, а x — координата, в которой v имеет максимальный абсолютный модуль. Без ограничения общности предположим, что vx положительно, поскольку в противном случае можно взять собственный вектор -v, также соответствующий λ₁. Тогда

Для d-регулярных графов d является первым собственным значением матрицы A для вектора, состоящего из единиц (легко проверить, что это собственное значение, и оно является максимальным в силу вышеуказанной границы). Кратность этого собственного значения равна числу связных компонент графа G, в частности, равна 1 для связных графов. Можно показать, что для каждого собственного значения λ его противоположность -λ также является собственным значением матрицы A, если G — двудольный граф. В частности, −d является собственным значением любого d-регулярного двудольного графа. Разность λ₁ − (-d) = λ₁ + d называется спектральным зазором и связана с расширением графа G. Также полезно ввести спектральный радиус матрицы A, обозначаемый ρ(A). Это число ограничено сверху ρ(A) ≤ d. Это ограничение достигается в графах Рамануджана, которые находят применение во многих областях.

Изоморфизм и инварианты

Предположим, даны два ориентированных или неориентированных графа G1 и G2 с матрицами смежности A1 и A2. Графы G1 и G2 изоморфны тогда и только тогда, когда существует перестановочная матрица P такая, что

В частности, A1 и A2 подобны и, следовательно, имеют один и тот же минимальный полином, характеристический полином, собственные значения, определитель и след. Таким образом, они могут служить инвариантами изоморфизма графов. Однако два графа могут иметь один и тот же набор собственных значений, но при этом не быть изоморфными. Такие линейные операторы называются изоспектральными.

Силы матрицы

Если A является матрицей смежности ориентированного или неориентированного графа G, то матрица A^(n) (то есть матричное произведение n копий A) имеет интересную интерпретацию: элемент a_(ij) дает число (ориентированных или неориентированных) путей длиной n из вершины i в вершину j. Если n – наименьшее неотрицательное целое число, такое, что для некоторых i, j элемент a_(ij) матрицы A^(n) положителен, то n – расстояние между вершиной i и вершиной j. Прекрасный пример полезности этого факта – подсчет числа треугольников в неориентированном графе G, который равен следу A^(3), деленному на 3 или 6 в зависимости от того, является ли граф ориентированным или нет. Мы делим на эти значения, чтобы компенсировать многократный подсчет каждого треугольника. В неориентированном графе каждый треугольник будет подсчитан дважды для всех трех вершин, поскольку путь можно пройти по часовой стрелке или против часовой стрелки: ijk или ikj. Матрицу смежности можно использовать для определения связности графа. Если ориентированный граф имеет нильпотентную матрицу смежности (то есть существует такое n, что A^(n) является нулевой матрицей), то это ориентированный ациклический граф.

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

Матрица смежности может использоваться как структура данных для представления графов в компьютерных программах, предназначенных для работы с графами. Основной альтернативной структурой данных, также применяемой для этой цели, является список смежности. Объем памяти, необходимый для представления матрицы смежности, и время, затрачиваемое на выполнение операций с ней, зависят от выбранного способа представления базовой матрицы. Разреженные матричные представления хранят только ненулевые элементы матрицы, а нулевые элементы представляются неявно. Например, их можно использовать для представления разреженных графов, избегая затрат памяти на хранение множества нулевых элементов в матрице смежности разреженного графа. В следующем разделе предполагается, что матрица смежности представлена структурой данных в виде массива, таким образом, нулевые и ненулевые элементы хранятся непосредственно в памяти. Поскольку каждый элемент матрицы смежности требует всего один бит, ее можно представить в очень компактном виде, занимая всего |V|²/8 байт для представления ориентированного графа или, при использовании сжатого треугольного формата и хранении только нижней треугольной части матрицы, приблизительно |V|²/16 байт для представления неориентированного графа. Хотя существуют и более компактные способы представления, данный метод приближается к теоретическому нижнему пределу необходимого количества бит для представления всех графов с n вершинами. Для хранения графов в текстовых файлах можно использовать меньше бит на байт, чтобы гарантировать, что все байты будут текстовыми символами, например, используя кодировку Base64. Помимо экономии памяти, такая компактность способствует локальности доступа к памяти. Однако для больших разреженных графов списки смежности требуют меньше памяти, поскольку не тратят место на представление отсутствующих ребер.