В теории графов и информатике , матрица смежности является квадратная матрица используется для представления конечного графа . Элементы матрицы указать , является ли пары вершин являются смежными или нет на графике.
В частном случае конечного простого графа матрица смежности представляет собой (0,1) -матрицу с нулями на ее диагонали. Если граф неориентированный (т.е. все его ребра двунаправленные), матрица смежности симметрична . Связь между графом и собственными значениями и собственными векторами его матрицы смежности изучается в спектральной теории графов .
Матрицу смежности графа следует отличать от ее матрицы инцидентности , другого матричного представления, элементы которого указывают, являются ли пары вершина – ребро инцидентными или нет, и его матрицы степеней , которая содержит информацию о степени каждой вершины.
Определение
Для простого графа с множеством вершин U = { u 1 ,…, u n } матрица смежности представляет собой квадратную матрицу A размера n × n , у которой элемент A ij равен единице, когда есть ребро от вершины u i к вершине u. j и ноль, когда ребра нет. [1] Все диагональные элементы матрицы равны нулю, поскольку ребра от вершины к самой себе ( петли ) не допускаются в простых графах. Также иногда полезно в алгебраической теории графов заменять ненулевые элементы алгебраическими переменными. [2] Та же концепция может быть расширена на мультиграфы и графы с циклами, сохраняя количество ребер между каждыми двумя вершинами в соответствующем матричном элементе и разрешая ненулевые диагональные элементы. Циклы могут быть засчитаны один раз (как одно ребро) или дважды (как две вершины-грани инцидентности), если соблюдается согласованное соглашение. Ненаправленные графы часто используют второе соглашение о подсчете циклов дважды, тогда как ориентированные графы обычно используют первое соглашение.
Двудольного графа
Матрица смежности из двудольного графа , чьи две части имеют р и ы вершины могут быть записаны в виде
где B - матрица размера r × s , а 0 r , r и 0 s , s представляют собой нулевые матрицы r × r и s × s . В этом случае меньшая матрица B однозначно представляет граф, а оставшиеся части A могут быть отброшены как избыточные. B иногда называют матрицей двойного сопряжения .
Формально, пусть G = ( U , V , Е ) быть двудольный граф с частями U = { U 1 , ..., у г }, V = { v 1 , ..., v s } и ребер Е . Матрица biadjacency является г × с 0-1 матрица B , в которой B I , J = 1 тогда и только тогда , когда ( U я , v J ) ∈ E .
Если G - двудольный мультиграф или взвешенный граф , то элементы b i, j считаются количеством ребер между вершинами или весом ребра ( u i , v j ) соответственно.
Матрица смежности двудольного графа полностью унимодулярна . Это означает, что определитель каждой квадратной подматрицы равен -1, 0 или +1.
Вариации
( , Ь , с ) -adjacency матрица простого графа имеет я , J = , если ( я , J ) является ребром, Ь , если это не так , и с по диагонали. Матрица смежности Сейдел является (-1, 1, 0) -adjacency матрица. Эта матрица используется при изучении сильно регулярных графов и двуграфов . [3]
Матрица расстояния имеет в положении ( I , J ) расстояние между вершинами v I и v J . Расстояние - это длина кратчайшего пути, соединяющего вершины. Если длина ребер не указана явно, длина пути - это количество ребер в нем. Матрица расстояний напоминает матрицу смежности высокой степени, но вместо того, чтобы сообщать только о том, соединены ли две вершины (т. Е. Матрица соединений, которая содержит логические значения ), она дает точное расстояние между ними.
Примеры
Ненаправленные графы
Следующее здесь соглашение (для неориентированных графов) состоит в том, что каждое ребро добавляет 1 к соответствующей ячейке в матрице, а каждый цикл добавляет 2. [4] Это позволяет легко определить степень вершины, взяв сумму значений в соответствующей строке или столбце матрицы смежности.
Маркированный график | Матрица смежности |
---|---|
| |
|
Направленные графы
Матрица смежности ориентированного графа может быть асимметричной. Матрицу смежности ориентированного графа можно определить так, что
- ненулевой элемент A ij указывает ребро от i до j или
- он указывает край от j до i .
Первое определение обычно используется в теории графов и анализе социальных сетей (например, в социологии, политологии, экономике, психологии). [5] Последнее более распространено в других прикладных науках (например, динамических системах, физике, сетевых науках), где A иногда используется для описания линейной динамики на графах. [6]
Используя первое определение, входные степени вершины могут быть вычислены путем суммирования элементов соответствующего столбца и исходных степеней вершины путем суммирования элементов соответствующей строки. При использовании второго определения входная степень вершины задается соответствующей суммой строк, а исходящая степень задается соответствующей суммой столбцов.
Маркированный график | Матрица смежности |
---|---|
|
|
Тривиальные графики
Матрица смежности полного графа содержит все единицы, кроме по диагонали, где есть только нули. Матрица смежности пустого графа - это нулевая матрица .
Характеристики
Спектр
Матрица смежности неориентированного простого графа симметрична и, следовательно, имеет полный набор действительных собственных значений и ортогональный базис собственных векторов . Набор собственных значений графа - это спектр графа. [7] Собственные значения принято обозначать как
Наибольшее собственное значение ограничена сверху максимальной степенью. Это можно увидеть как результат теоремы Перрона – Фробениуса , но это легко доказать. Пусть v - один собственный вектор, связанный си x компонент, в котором v имеет максимальное абсолютное значение. Без ограничения общности предположим, что v x положительно, поскольку в противном случае вы просто берете собственный вектор, также связанный с . потом
Для d -регулярных графов d - первое собственное значение A для вектора v = (1,…, 1) (легко проверить, что это собственное значение, и оно максимальное из-за вышеприведенной оценки). Кратность этого собственного значения - это количество компонент связности G , в частностидля связных графов. Можно показать, что для каждого собственного значения, его противоположность также является собственным значением A, если G - двудольный граф . [8] В частности, - d является собственным значением двудольных графов.
Различия называется спектральную щель , и это связано с расширением из G . Это также полезно , чтобы ввести спектральный радиус из обозначается . Это число ограничено. Эта граница жесткая в графах Рамануджана , которые имеют приложения во многих областях.
Изоморфизм и инварианты
Предположим, что даны два ориентированных или неориентированных графа G 1 и G 2 с матрицами смежности A 1 и A 2 . G 1 и G 2 являются изоморфны тогда и только тогда , когда существует перестановка матрицы P такой , что
В частности, 1 и 2 являются похожи , и , следовательно , имеют тот же минимальный многочлен , характеристический полином , собственные значения , определитель и след . Следовательно, они могут служить инвариантами изоморфизма графов. Однако два графа могут иметь одинаковый набор собственных значений, но не быть изоморфными. [9] Такие линейные операторы называются изоспектральными .
Матричные полномочия
Если является матрица смежности направленного или ненаправленного графа G , то матрица п (то есть произведение матриц из п копий А ) имеет интересную интерпретацию: элемент ( я , J ) дает число (направленный или неориентированные) блуждания длины n от вершины i до вершины j . Если n - наименьшее неотрицательное целое число, такое, что для некоторых i , j элемент ( i , j ) в A n положителен, то n - это расстояние между вершиной i и вершиной j . Это подразумевает, например, что число треугольников в неориентированном графе G в точности след от А 3 делится на 6. Матрица смежности может быть использована , чтобы определить , является ли или нет графика подключен .
Структуры данных
Матрица смежности может использоваться в качестве структуры данных для представления графов в компьютерных программах для управления графами. Основной альтернативной структурой данных, также используемой в этом приложении, является список смежности . [10] [11]
Поскольку каждая запись в матрице смежности требует только одного бита, ее можно представить очень компактно, занимая только | V | 2 /8 байт для представления ориентированного графа, или (с помощью насадочной треугольной формы , и только хранить нижнюю треугольную часть матрицы) приблизительно | V | 2 /16 байты для представления неориентированного графа. Хотя возможны несколько более сжатые представления, этот метод приближается к теоретико-информационной нижней границе минимального числа битов, необходимых для представления всех графов с n- вершинами. [12] Для хранения графиков в текстовых файлах можно использовать меньшее количество бит на байт, чтобы гарантировать, что все байты являются текстовыми символами, например, с помощью представления Base64 . [13] Помимо экономии места, эта компактность способствует локализации ссылок . Однако для большого разреженного графа списки смежности требуют меньше места для хранения, потому что они не тратят впустую пространство для представления ребер, которых нет . [11] [14]
Альтернативная форма матрицы смежности (которая, однако, требует большего пространства) заменяет числа в каждом элементе матрицы указателями на граничные объекты (при наличии ребер) или нулевые указатели (при отсутствии ребра). [14] Также можно сохранять веса ребер непосредственно в элементах матрицы смежности. [11]
Помимо компромисса пространства, различные структуры данных также облегчают различные операции. Найти все вершины, смежные с данной вершиной в списке смежности, так же просто, как прочитать список, и требуется время, пропорциональное количеству соседей. При использовании матрицы смежности вместо этого необходимо сканировать всю строку, что занимает больше времени, пропорциональное количеству вершин во всем графе. С другой стороны, проверка наличия ребра между двумя заданными вершинами может быть определена сразу с помощью матрицы смежности, при этом требуется время, пропорциональное минимальной степени двух вершин со списком смежности. [11] [14]
Смотрите также
- Матрица лапласа
- Матрица самоподобия
Рекомендации
- ^ Биггс, Норман (1993), алгебраическая теория графов , Кембриджская математическая библиотека (2-е изд.), Cambridge University Press, определение 2.1, стр. 7.
- ^ Харари, Frank (1962), "Определитель матрицы смежности графа", SIAM Review , 4 (3): 202-210, Bibcode : 1962SIAMR ... 4..202H , DOI : 10,1137 / 1004057 , MR 0144330.
- ^ Зайдель, Дж. Дж. (1968). «Сильно регулярные графы с (-1, 1, 0) матрицей смежности, имеющей собственное значение 3» . Лин. Alg. Прил. 1 (2): 281–298. DOI : 10.1016 / 0024-3795 (68) 90008-6 .
- ^ Шум, Кеннет; Блейк, Ян (18 декабря 2003 г.). «Расширительные графики и коды» . Том 68 серии DIMACS по дискретной математике и теоретической информатике . Алгебраическая теория кодирования и теория информации: семинар DIMACS, алгебраическая теория кодирования и теория информации. Американское математическое общество. п. 63.
- ^ Боргатти, Стив; Эверетт, Мартин; Джонсон, Джеффри (2018), Анализ социальных сетей (2-е изд.), SAGE, стр. 20
- ^ Ньюман, Марк (2018), Сети (2-е изд.), Oxford University Press, стр. 110
- ↑ Biggs (1993) , глава 2 («Спектр графа»), стр. 7–13.
- ^ Brouwer, Andries E .; Хемерс, Виллем Х. (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
- ↑ Goodrich & Tamassia (2015) , стр. 361: «Есть две структуры данных, которые люди часто используют для представления графов: список смежности и матрица смежности».
- ^ а б в г Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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 , МР 0749658.
- ^ Маккей, Брендан , Описание кодировок graph6 и sparse6.
- ^ а б в Гудрич, Майкл Т .; Тамассия, Роберто (2015), Разработка алгоритмов и приложения , Wiley, стр. 363.
Внешние ссылки
- Вайсштейн, Эрик В. «Матрица смежности» . MathWorld .
- Fluffschack - обучающая веб-игра на Java, демонстрирующая взаимосвязь между матрицами смежности и графами.
- Структуры открытых данных - Раздел 12.1 - Матрица смежности: представление графа матрицей , Пат Морин
- Café math: Матрицы смежности графов : применение матриц смежности к вычислениям, порождающим серии прогулок.