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

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

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

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

Определение

Для простого графа с множеством вершин U = {ты₁, …, ты_п} матрица смежности представляет собой квадрат п × п матрица А так что его элемент А_ij один, когда есть ребро из вершины ты_я к вершине ты_j, и ноль, когда края нет.^[1] Все диагональные элементы матрицы равны нулю, так как ребра от вершины к самой себе (петли ) не допускаются в простых графах. Это также иногда полезно в алгебраическая теория графов заменить ненулевые элементы алгебраическими переменными.^[2] Ту же концепцию можно распространить на мультиграфы и графы с петлями, сохраняя количество ребер между каждыми двумя вершинами в соответствующем матричном элементе и разрешая ненулевые диагональные элементы. Циклы могут быть засчитаны один раз (как одно ребро) или дважды (как две вершины-ребра), если соблюдается согласованное соглашение. Ненаправленные графы часто используют второе соглашение о подсчете циклов дважды, тогда как ориентированные графы обычно используют первое соглашение.

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

Матрица смежности А из двудольный граф чьи две части имеют р и s вершины можно записать в виде

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

куда B является р × s матрица и 0_р,р и 0_s,s представляют р × р и s × s нулевые матрицы. В этом случае меньшая матрица B однозначно представляет график, а остальные части А могут быть отброшены как избыточные. B иногда называют матрица двойственности.

Формально пусть грамм = (U, V, E) быть двудольный граф с частями U = {ты₁, …, ты_р}, V = {v₁, …, v_s} и края E. Матрица двойственности - это р × s 0–1 матрица B в котором б_я,j = 1 если и только если (ты_я, v_j) ∈ E.

Если грамм двудольный мультиграф или же взвешенный график, то элементы б_{я, j} считаются количество ребер между вершинами или вес ребра (ты_я, v_j), соответственно.

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

Вариации

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

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

Примеры

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

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

Помеченный график	Матрица смежности
	${\displaystyle {\begin{pmatrix}2&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}}}$ Координаты 1–6.
Науру график	Координаты 0–23. Белые поля - нули, цветные - единицы.

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

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

1. ненулевой элемент А_ij указывает край от я к j или же
2. это указывает край от j к я.

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

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

Помеченный график	Матрица смежности
Режиссер Граф Кэли из S4	Координаты 0–23. Поскольку граф ориентирован, матрица не обязательно симметричный.

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

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

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

Спектр

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

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

${\displaystyle \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 - первое собственное значение А для вектора v = (1, …, 1) (легко проверить, что это собственное значение и максимальное значение из-за вышеприведенной оценки). Кратность этого собственного значения равна количеству компонент связности грамм, особенно ${\displaystyle \lambda _{1}>\lambda _{2}}$ для связных графов. Можно показать, что для каждого собственного значения ${\displaystyle \lambda _{i}}$, его противоположность ${\displaystyle -\lambda _{i}=\lambda _{n+1-i}}$ также является собственным значением А если грамм это двудольный граф.^[8] В частности -d является собственным значением двудольных графов.

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

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

Предположим, что два ориентированных или неориентированных графа грамм₁ и грамм₂ с матрицами смежности А₁ и А₂ даны. грамм₁ и грамм₂ находятся изоморфный тогда и только тогда, когда существует матрица перестановок п такой, что

${\displaystyle PA_{1}P^{-1}=A_{2}.}$

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

Матричные силы

Если А матрица смежности ориентированного или неориентированного графа грамм, то матрица А^п (т.е. матричный продукт из п копии А) имеет интересную интерпретацию: элемент (я, j) дает количество (направленных или ненаправленных) прогулки длины п из вершины я к вершине j. Если п это наименьшее неотрицательное целое число, такое, что для некоторых я, j, элемент (я, j) из А^п положительно, то п расстояние между вершинами я и вершина j. Это означает, например, что количество треугольников в неориентированном графе грамм это точно след из А³ делится на 6. Матрица смежности может использоваться, чтобы определить, является ли граф связаны.

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

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

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

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

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

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

• Матрица лапласа
• Матрица самоподобия

Рекомендации

1. Биггс, Норман (1993), Алгебраическая теория графов, Кембриджская математическая библиотека (2-е изд.), Cambridge University Press, Определение 2.1, стр. 7.
2. Харари, Фрэнк (1962), "Определитель матрицы смежности графа", SIAM Обзор, 4 (3): 202–210, Bibcode:1962 г.SIAMR ... 4..202H, Дои:10.1137/1004057, МИСТЕР  0144330.
3. Зайдель, Дж. Дж. (1968). «Сильно регулярные графы с (−1, 1, 0) матрицей смежности, имеющей собственное значение 3». Лин. Alg. Appl. 1 (2): 281–298. Дои:10.1016/0024-3795(68)90008-6.
4. Шум, Кеннет; Блейк, Ян (18 декабря 2003 г.). «Расширительные графики и коды». Том 68 серии DIMACS по дискретной математике и теоретической информатике. Алгебраическая теория кодирования и теория информации: семинар DIMACS, алгебраическая теория кодирования и теория информации. Американское математическое общество. п. 63.
5. Боргатти, Стив; Эверетт, Мартин; Джонсон, Джеффри (2018), Анализ социальных сетей (2-е изд.), МУДРЕЦ, стр. 20
6. Ньюман, Марк (2018), Сети (2-е изд.), Oxford University Press, стр. 110
7. Биггс (1993), Глава 2 («Спектр графа»), стр. 7–13.
8. Brouwer, Andries E .; Хемерс, Виллем Х. (2012), «1.3.6 Двудольные графы», Спектры графиков, Universitext, New York: Springer, стр. 6–7, Дои:10.1007/978-1-4614-1939-6, ISBN  978-1-4614-1938-9, МИСТЕР  2882891
9. Годсил, Крис; Ройл, Гордон Алгебраическая теория графов, Springer (2001), ISBN  0-387-95241-1, стр.164
10. Гудрич и Тамассия (2015), п. 361: «Есть две структуры данных, которые люди часто используют для представления графов: список смежности и матрица смежности».
11. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001), «Раздел 22.1: Представления графов», Введение в алгоритмы (Второе изд.), MIT Press and McGraw-Hill, pp. 527–531, ISBN  0-262-03293-7.
12. Туран, Дьёрдь (1984), "О кратком представлении графов", Дискретная прикладная математика, 8 (3): 289–294, Дои:10.1016 / 0166-218X (84) 90126-4, МИСТЕР  0749658.
13. Маккей, Брендан, Описание кодировок graph6 и sparse6.
14. Гудрич, Майкл Т.; Тамассия, Роберто (2015), Разработка алгоритмов и приложения, Wiley, стр. 363.

внешняя ссылка

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