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

редактировать

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

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

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

Содержание

1 Определение
- 1.1 Двудольного графа
- 1.2 Варианты
2 Примеры
- 2.1 Ненаправленные графы
- 2.2 Направленные графы
- 2.3 Тривиальные графы
3 Свойства
- 3.1 Спектр
- 3.2 Изоморфизм и инварианты
- 3.3 Мощности матрицы
4 Структуры данных
5 См. Также
6 Ссылки
7 Внешние ссылки

Определение

Для простого графа с множеством вершин V матрица смежности представляет собой квадрат | V | × | V | матрица A такая, что ее элемент A ij равен единице, когда есть ребро от вершины i до вершины j, и нулю, когда ребра нет. Все диагональные элементы матрицы равны нулю, поскольку ребра от вершины к самой себе (петли ) не допускаются в простых графах. В теории алгебраических графов также иногда бывает полезно заменить ненулевые элементы алгебраическими переменными. Ту же концепцию можно распространить на мультиграфы и графы с циклами, сохранив количество ребер между каждыми двумя вершинами в соответствующем матричном элементе и допустив ненулевые диагональные элементы. Циклы могут быть засчитаны один раз (как одно ребро) или дважды (как две вершины-ребра), если соблюдается согласованное соглашение. Ненаправленные графы часто используют второе соглашение о подсчете циклов дважды, тогда как ориентированные графы обычно используют первое соглашение.

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

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

A = ( 0 r, r BBT 0 s, s), {\ displaystyle A = {\ begin {pmatrix} 0_ {r, r} B \\ B ^ {\ mathsf {T}} 0_ {s, s} \ end {pmatrix }},}

{\ 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, E) будет двудольным графом с частями U = {u 1,…, u r }, V = {v 1,…, v s } и ребра E. Матрица двойного сопряжения - это матрица 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) -матрицей смежности. Эта матрица используется при изучении строго регулярных графов и двухграфов.

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

Примеры

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

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

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

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

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

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

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

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

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

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

Свойства

Spectrum

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

λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n. {\ displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}.}

{\ displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}.}

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

λ 1 v x = (A v) x = ∑ y = 1 n A x, y v y ≤ ∑ y = 1 n A x, y v x = v x deg ⁡ (x). {\ 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).}

{\ 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, в частности $λ 1>λ 2 {\ displaystyle \ lambda _ {1}>\ lambda _ {2}}$ $\lambda _{1}>\ lambda _ {2}$ для подключенных графиков. можно показать, что для каждого собственного значения $λ i {\ displaystyle \ lambda _ {i}}$ $\ лямбда _ {i}$ его противоположное значение $- λ i = λ n + 1 - i {\ displaystyle - \ lambda _ {i} = \ lambda _ {n + 1-i}}$ ${\ displaystyle - \ lambda _ {i} = \ lambda _ {n + 1-i}}$ также является собственным значением A, если G является двудольным графом. В частности, −d является собственным значением двудольного графа графиков.

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

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

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

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

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

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

степенями матрицы

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

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

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

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

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

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

См. Также

Ссылки

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

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

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