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

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

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

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

Определение

Для простого графа с множеством вершин $U = {u 1, \dots, u n}$ матрица смежности представляет собой квадратную $размера n \times n$ матрицу $A$ , такую, что ее элемент $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 = {u 1, ..., u r}$ , $V = {v 1, ..., v s}$ и ребрами $E$ . Матрица двусмежности — это $размера r \times s$ 0–1 $матрица B$ , в которой $b i, j = 1$ тогда и только тогда, когда $(u i, v j) \in E$ .

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

Вариации

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

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

Примеры

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

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

Маркированный график	Матрица смежности
	${\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. Белые поля — нули, цветные — единицы.

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

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

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

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

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

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

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

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

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

Спектр

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

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

Разница $\lambda _{1}-\lambda _{2}$ называется спектральной щелью связана с расширением G $и$ . Полезно также ввести радиус спектральный $A$ обозначается $\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$ A $)$ имеет интересную интерпретацию: элемент $(i, j)$ дает количество (направленных или ненаправленных) обходов длины $n$ от вершины $i$ до вершины $j$ . Если $n$ — наименьшее неотрицательное целое число, такое, что для некоторых $i$ , $j$ элемент $(i, j)$ из $A н$ положительно, то $n$ — расстояние между вершиной $i$ и вершиной $j$ . является подсчет количества треугольников в неориентированном графе $G$ , который в точности является следом A. $Отличным примером того, насколько это полезно , 3$ делится на 3 или 6 в зависимости от того, ориентированный граф или нет. Мы делим на эти значения, чтобы компенсировать пересчет каждого треугольника. В неориентированном графе каждый треугольник будет учитываться дважды для всех трех узлов, поскольку путь можно пройти по или против часовой стрелки: ijk или ikj. Матрицу смежности можно использовать для определения связности графа .

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

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

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

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

Поскольку каждая запись в матрице смежности требует только одного бита, ее можно представить очень компактно, занимая всего | В | ² / 8 байт для представления ориентированного графа или (с использованием упакованного треугольного формата и сохранения только нижней треугольной части матрицы) приблизительно | В | ² / 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 .
^ Зайдель, Джей-Джей (1968). «Строго регулярные графы с (-1, 1, 0) матрицей смежности, имеющей собственное значение 3». Лин. Алг. Прил. 1 (2): 281–298. дои : 10.1016/0024-3795(68)90008-6 .
^ Шум, Кеннет; Блейк, Ян (18 декабря 2003 г.). «Расширитель графиков и кодов» . Том 68 серии DIMACS по дискретной математике и теоретической информатике . Алгебраическая теория кодирования и теория информации: семинар DIMACS, алгебраическая теория кодирования и теория информации. Американское математическое общество. п. 63. ИСБН 9780821871102 .
^ Боргатти, Стив; Эверетт, Мартин; Джонсон, Джеффри (2018), Анализ социальных сетей (2-е изд.), SAGE, стр. 20
^ Ньюман, Марк (2018), Networks (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.
^ Гудрич и Тамассия (2015) , с. 361: «Существуют две структуры данных, которые люди часто используют для представления графов: список смежности и матрица смежности».
^ Jump up to: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «Раздел 22.1: Представления графов», Введение в алгоритмы (второе изд.), MIT Press и McGraw-Hill, стр. 527–531, ISBN 0-262-03293-7 .
^ Туран, Дьёрдь (1984), «О кратком представлении графов», Discrete Applied Mathematics , 8 (3): 289–294, doi : 10.1016/0166-218X(84)90126-4 , MR 0749658 .
^ Маккей, Брендан , Описание кодировок графа6 и разреженного6 , заархивировано из оригинала 30 апреля 2001 г. , получено 10 февраля 2012 г.
^ Jump up to: ^а ^б ^с Гудрич, Майкл Т .; Тамассиа, Роберто (2015), Разработка и применение алгоритмов , Wiley, стр. 363 .

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

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

[1] Биггс, Норман (1993), Алгебраическая теория графов , Кембриджская математическая библиотека (2-е изд.), Cambridge University Press, Определение 2.1, стр. 7 .

[2] Харари, Франк (1962), «Определитель матрицы смежности графа», SIAM Review , 4 (3): 202–210, Bibcode : 1962SIAMR...4..202H , doi : 10.1137/1004057 , MR 0144330 .

[3] Зайдель, Джей-Джей (1968). «Строго регулярные графы с (-1, 1, 0) матрицей смежности, имеющей собственное значение 3». Лин. Алг. Прил. 1 (2): 281–298. дои : 10.1016/0024-3795(68)90008-6 .

[4] Шум, Кеннет; Блейк, Ян (18 декабря 2003 г.). «Расширитель графиков и кодов» . Том 68 серии DIMACS по дискретной математике и теоретической информатике . Алгебраическая теория кодирования и теория информации: семинар DIMACS, алгебраическая теория кодирования и теория информации. Американское математическое общество. п. 63. ИСБН 9780821871102 .

[5] Боргатти, Стив; Эверетт, Мартин; Джонсон, Джеффри (2018), Анализ социальных сетей (2-е изд.), SAGE, стр. 20

[6] Ньюман, Марк (2018), Networks (2-е изд.), Oxford University Press, стр. 110

[7] Биггс (1993) , Глава 2 («Спектр графа»), стр. 7–13.

[8] Брауэр, Андрис Э.; Хемерс, Виллем Х. (2012), «1.3.6 Двудольные графы» , Спектры графов , Universitext, Нью-Йорк: Springer, стр. 6–7, doi : 10.1007/978-1-4614-1939-6 , ISBN 978-1-4614-1938-9 , МР 2882891

[9] Годсил, Крис ; Ройл, Алгебраическая теория графов Гордона , Springer (2001), ISBN 0-387-95241-1 , стр.164.

[10] Николсон, Виктор А (1975). «Матрицы с постоянным равным единице» (PDF) . Линейная алгебра и ее приложения (12): 187.

[11] Гудрич и Тамассия (2015) , с. 361: «Существуют две структуры данных, которые люди часто используют для представления графов: список смежности и матрица смежности».

[clrs-12] Jump up to: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «Раздел 22.1: Представления графов», Введение в алгоритмы (второе изд.), MIT Press и McGraw-Hill, стр. 527–531, ISBN 0-262-03293-7 .

[13] Туран, Дьёрдь (1984), «О кратком представлении графов», Discrete Applied Mathematics , 8 (3): 289–294, doi : 10.1016/0166-218X(84)90126-4 , MR 0749658 .

[14] Маккей, Брендан , Описание кодировок графа6 и разреженного6 , заархивировано из оригинала 30 апреля 2001 г. , получено 10 февраля 2012 г.

[gt-15] Jump up to: ^а ^б ^с Гудрич, Майкл Т .; Тамассиа, Роберто (2015), Разработка и применение алгоритмов , Wiley, стр. 363 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

v т и Представления графов
Data structures	Graph (abstract data type) Adjacency list Edge list Adjacency matrix Incidence matrix
XML-based formats	DGML DotML GEXF GraphML GXL XGMML
Text-based formats	DOT Graph Modelling Language (GML) LCF notation for cubic Hamiltonian graphs Newick format for trees Trivial Graph Format
Related concepts	Graph database Graph drawing Linked data

v т и Матричные классы
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
Mathematics portal List of matrices Category:Matrices