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

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

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

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

Определение [ править ]

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

Двудольного графа [ править ]

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

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

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

Формально, пусть G = ( U , V , Е ) является двудольный граф с частями U = { U ₁ , ..., у _г }, V = { v ₁ , ..., v _s } и ребер Е . Матрица взаимосопряженности - это матрица B размером r × s 0–1, в которой b _{i , j} = 1 тогда и только тогда, когда ( u _i , v _j ) ∈E .

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

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

Варианты [ править ]

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

Матрица расстояния имеет в положении ( I , J ) расстояние между вершинами v _I и 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} {pmatrix} {pmatrix}$ Координаты 1–6.
Науру график	Координаты 0–23. Белые поля - нули, цветные - единицы.

Направленные графики [ править ]

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

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

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

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

Тривиальные графики [ править ]

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

Свойства [ править ]

Спектр [ править ]

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

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

Разница называется спектральная щель , и это связано с расширением из G . Это также полезно , чтобы ввести спектральный радиус в обозначаться . Это число ограничено . Эта граница жесткая в графах Рамануджана , которые имеют приложения во многих областях.${\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)}$

Изоморфизм и инварианты [ править ]

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

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

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

Матричные силы [ править ]

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

Структуры данных [ править ]

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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

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