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

В теории графов и информатике матрица смежности — это квадратная матрица, используемая для представления конечного графа . Элементы матрицы указывают , являются ли пары вершин смежными или нет в графе.

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

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

Определение

Для простого графа с множеством вершин $U = {u 1, \dots, u n}$ матрица смежности представляет собой квадратную матрицу $A размером$ $n \times n$ , такую, что ее элемент $A$ $ij$ равен единице, когда есть ребро из вершины $u$ $i$ в вершину $u$ $j$ , и нулю, когда ребра нет. ^[1] Все диагональные элементы матрицы равны нулю, поскольку ребра из вершины в себя ( петли ) не допускаются в простых графах. Иногда в алгебраической теории графов полезно заменять ненулевые элементы алгебраическими переменными. ^[2] Эту же концепцию можно распространить на мультиграфы и графы с петлями, сохранив количество ребер между каждыми двумя вершинами в соответствующем элементе матрицы и разрешив ненулевые диагональные элементы. Петли можно подсчитывать либо один раз (как одно ребро), либо дважды (как два инцидента вершина-ребро), если соблюдается согласованное соглашение. Неориентированные графы часто используют второе соглашение, подсчитывая циклы дважды, тогда как ориентированные графы обычно используют первое соглашение.

Двудольного графа

Матрицу смежности $A$ двудольного графа , две части которого имеют $r$ и $s$ вершин, можно записать в виде

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

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

Формально, пусть $G = (U, V, E)$ — двудольный граф с частями $U = {u1, ..., ur}$ , $V = {v1, ..., vs}$ и ребрами $E.$ Матрица бисмежности — это матрица $B$ $размером$ $r$ $\times$ $s$ 0–1, $в$ которой $b$ $i$ $,$ $j$ $= 1$ тогда и только тогда , $когда$ $($ $u$ $i$ $,$ $v$ $j$ $)$ $\in$ $E.$

Если $G$ — двудольный мультиграф или взвешенный граф , то элементы $b i,j$ считаются равными числу ребер между вершинами или весу ребра $(u i, v j)$ соответственно.

Вариации

Матрица смежности $(a, b, c)$ $A$ простого графа имеет $A i, j = a$ , если $(i, j)$ является ребром, $b$ , если это не так, и $c$ на диагонали. Матрица смежности Зейделя является матрицей смежности $(-1, 1, 0)$ . Эта матрица используется при изучении сильно регулярных графов и двумерных графов . ^[3]

Матрица расстояний имеет в позиции $(i, j)$ расстояние между вершинами $v i$ и $v j$ . Расстояние — это длина кратчайшего пути, соединяющего вершины. Если длины ребер явно не указаны, длина пути — это количество ребер в нем. Матрица расстояний напоминает высокую степень матрицы смежности, но вместо того, чтобы сообщать только о том, соединены ли две вершины (т. е. матрица соединений, которая содержит булевы значения ), она дает точное расстояние между ними.

Примеры

Неориентированные графы

Соглашение, которому здесь следуют (для неориентированных графов), заключается в том, что каждое ребро добавляет 1 к соответствующей ячейке в матрице, а каждая петля (ребро от вершины к себе) добавляет 2 к соответствующей ячейке на диагонали в матрице. ^[4] Это позволяет легко найти степень вершины, взяв сумму значений либо в соответствующей строке, либо в соответствующем столбце в матрице смежности.

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

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

ненулевой элемент $A ij$ указывает ребро от $i$ до $j$ или
он указывает на ребро от $j$ до $i$ .

Первое определение обычно используется в теории графов и анализе социальных сетей (например, социологии, политологии, экономике, психологии). ^[5] Второе определение более распространено в других прикладных науках (например, динамических системах, физике, сетевой науке), где $A$ иногда используется для описания линейной динамики на графах. ^[6]

Используя первое определение, входящие степени вершины можно вычислить, суммируя записи соответствующего столбца, а исходящие степени вершины — суммируя записи соответствующей строки. При использовании второго определения входящая степень вершины определяется соответствующей суммой строки, а исходящие степени определяются соответствующей суммой столбца.

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

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

Характеристики

Спектр

Матрица смежности неориентированного простого графа симметрична , и поэтому имеет полный набор действительных собственных значений и ортогональный базис собственных векторов . Набор собственных значений графа — это спектр графа. ^[7] Собственные значения принято обозначать как $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.$

Наибольшее собственное значение ограничено сверху максимальной степенью. Это можно рассматривать как результат теоремы Перрона–Фробениуса , но это можно легко доказать. Пусть $v$ — один собственный вектор, связанный с , а $x —$ запись, в которой $v$ имеет максимальное абсолютное значение. Без потери общности предположим, что $v$ $x$ положительно, так как в противном случае вы просто берете собственный вектор - $v$ , также связанный с . Тогда $\лямбда _{1}$ $\лямбда _{1}$ $\лямбда _{1}$

\lambda _{1}v_{x}=(Av)_{x}=\sum _{y=1}^{n}A_{x,y}v_{y}\leq \sum _{ y=1}^{n}A_{x,y}v_{x}=v_{x}\deg(x).

Для $d$ -регулярных графов $d$ является первым собственным значением $A$ для вектора $v = (1, \dots, 1)$ (легко проверить, что это собственное значение, и оно является максимальным из-за указанной выше границы). Кратность этого собственного значения является числом связных компонент $G$ , в частности, для связных графов. Можно показать, что для каждого собственного значения его противоположность также является собственным значением $A,$ если $G$ является двудольным графом . ^[8] В частности, − $d$ является собственным значением любого $d$ -регулярного двудольного графа. $\lambda _{1}>\lambda _{2}$ $\лямбда _{я}$ $-\lambda _{i}=\lambda _{n+1-i}$

Разница называется спектральным зазором и связана с расширением $G$ . Также полезно ввести спектральный радиус , обозначаемый . Это число ограничено . Эта граница точна в графах Рамануджана , которые имеют приложения во многих областях. $\lambda _{1}-\lambda _{2}$ $А$ $\lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|$ $\lambda (G)\geq 2{\sqrt {d-1}}-o (1)$

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

Предположим, что даны два ориентированных или неориентированных графа $G 1$ и $G 2$ с матрицами смежности $A 1$ и $A 2. Графы$ $G 1$ и $G 2$ изоморфны тогда и только тогда, когда существует матрица перестановки $P$ такая, что

PA_{1}P^{-1}=A_{2}.

В частности, $A 1$ и $A 2$ подобны и , следовательно, имеют одинаковый минимальный многочлен , характеристический многочлен , собственные значения , определитель и след . Поэтому они могут служить инвариантами изоморфизма графов. Однако два графа могут обладать одним и тем же набором собственных значений, но не быть изоморфными. ^[9] Такие линейные операторы называются изоспектральными .

Матричные полномочия

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

Если ориентированный граф имеет нильпотентную матрицу смежности (т.е. если существует $n$ такое, что $A n$ является нулевой матрицей), то это ориентированный ациклический граф . ^[10]

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

Матрица смежности может использоваться как структура данных для представления графов в компьютерных программах для манипулирования графами. Основной альтернативной структурой данных, также используемой для этого приложения, является список смежности . ^[11]^[12]

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

Поскольку каждая запись в матрице смежности требует только один бит, ее можно представить очень компактным способом, занимая всего | V | ² / 8 байт для представления ориентированного графа или (используя упакованный треугольный формат и сохраняя только нижнюю треугольную часть матрицы) приблизительно | V | ² / 16 байт для представления неориентированного графа. Хотя возможны немного более сжатые представления, этот метод приближается к информационной теоретико-нижней границе для минимального числа бит, необходимых для представления всех $n$ -вершинных графов. ^[13] Для хранения графов в текстовых файлах можно использовать меньшее количество бит на байт, чтобы гарантировать, что все байты являются текстовыми символами, например, используя представление Base64 . ^[14] Помимо избежания неиспользуемого пространства, эта компактность способствует локальности ссылок . Однако для большого разреженного графа списки смежности требуют меньше места для хранения, поскольку они не тратят место на представление отсутствующих ребер . ^[12]^[15]

Альтернативная форма матрицы смежности (которая, однако, требует большего объема пространства) заменяет числа в каждом элементе матрицы указателями на объекты ребер (когда ребра присутствуют) или нулевыми указателями (когда ребра нет). ^[15] Также возможно хранить веса ребер непосредственно в элементах матрицы смежности. ^[12]

Помимо компромисса по пространству, различные структуры данных также облегчают различные операции. Поиск всех вершин, смежных с заданной вершиной в списке смежности, так же прост, как чтение списка, и занимает время, пропорциональное количеству соседей. С матрицей смежности вместо этого необходимо сканировать всю строку, что занимает больше времени, пропорционального количеству вершин во всем графе. С другой стороны, проверка того, есть ли ребро между двумя заданными вершинами, может быть определена сразу с помощью матрицы смежности, при этом требуется время, пропорциональное минимальной степени двух вершин со списком смежности. ^[12]^[15]

Смотрите также

Ссылки

^ Биггс, Норман (1993), Алгебраическая теория графов , Кембриджская математическая библиотека (2-е изд.), Cambridge University Press, Определение 2.1, стр. 7.
^ Харари, Фрэнк (1962), «Определитель матрицы смежности графа», SIAM Review , 4 (3): 202–210, Bibcode : 1962SIAMR...4..202H, doi : 10.1137/1004057, MR 0144330.
^ Seidel, JJ (1968). «Строго регулярные графы с матрицей смежности (−1, 1, 0), имеющей собственное значение 3». Lin. Alg. Appl. 1 (2): 281–298. doi :10.1016/0024-3795(68)90008-6.
^ Шам, Кеннет; Блейк, Ян (2003-12-18). "Расширительные графы и коды". Том 68 серии DIMACS по дискретной математике и теоретической информатике . Алгебраическая теория кодирования и теория информации: DIMACS Workshop, Алгебраическая теория кодирования и теория информации. Американское математическое общество. стр. 63. ISBN 9780821871102.
^ Боргатти, Стив; Эверетт, Мартин; Джонсон, Джеффри (2018), Анализ социальных сетей (2-е изд.), SAGE, стр. 20
^ Ньюман, Марк (2018), Сети (2-е изд.), Oxford University Press, стр. 110
↑ Биггс (1993), Глава 2 («Спектр графа»), стр. 7–13.
^ Брауэр, Андрис Э.; Хемерс, Виллем Х. (2012), «1.3.6 Двудольные графы», Спектры графов , Universitext, Нью-Йорк: Springer, стр. 6–7, doi : 10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, г-н 2882891
^ Годсил, Крис ; Ройл, Гордон Алгебраическая теория графов , Springer (2001), ISBN 0-387-95241-1 , стр.164
^ Николсон, Виктор А (1975). "Матрицы с перманентом, равным единице" (PDF) . Линейная алгебра и ее приложения (12): 187.
^ Goodrich & Tamassia (2015), стр. 361: «Существуют две структуры данных, которые люди часто используют для представления графов: список смежности и матрица смежности».
^ abcd Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), «Раздел 22.1: Представления графов», Введение в алгоритмы (второе изд.), MIT Press и McGraw-Hill, стр. 527–531, ISBN 0-262-03293-7.
^ Туран, Дьёрдь (1984), «О кратком представлении графов», Дискретная прикладная математика , 8 (3): 289–294, doi :10.1016/0166-218X(84)90126-4, MR 0749658.
^ Маккей, Брендан , Описание кодировок graph6 и sparse6, заархивировано из оригинала 2001-04-30 , извлечено 2012-02-10.
^ abc Goodrich, Michael T. ; Tamassia, Roberto (2015), Разработка алгоритмов и их применение , Wiley, стр. 363.

Внешние ссылки

На Викискладе есть медиафайлы по теме Матрицы смежности графов .

Вайсштейн, Эрик В. "Матрица смежности". MathWorld .
Fluffschack — образовательная веб-игра на Java, демонстрирующая связь между матрицами смежности и графами.
Открытые структуры данных - Раздел 12.1 - AdjacencyMatrix: Представление графа матрицей, Пэт Морин
Кафе математики: Матрицы смежности графов: применение матриц смежности к вычислениям, генерирующим серии блужданий.