Матриця суміжності

Матриця суміжності — один із способів представлення графу у вигляді матриці.

Означення

Матриця суміжності графу G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) — це квадратна матриця A розміру n, в якій значення елементу a_ij рівне числу ребер з i-ї вершини графу в j-у вершину.

Іноді, особливо у разі неорієнтованого графу, петля (ребро з i-ї вершини в саму себе) вважається за два ребра, тобто значення діагонального елементу a_ii в цьому випадку рівне подвоєному числу петель навколо i-ї вершини.

Матриця суміжності простого графу (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.

Приклади

	Матриця суміжності
	${\displaystyle {\begin{pmatrix}1&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. Білі клітинки — нулі, кольорові клітинки — одиниці.
Орієнтований Граф Келі S4	Оскільки граф є орієнтованим, матриця не симетрична.

• Матриця суміжності повного графу K_n містить одиниці у всіх своїх елементах, окрім головної діагоналі, на якій розташовані нулі.

• Матриця суміжності порожнього графу, що не містить жодного ребра, складається лише з нулів.

Властивості

Матриця суміжності неорієнтованого графу симетрична, а значить володіє дійсними власними значеннями і ортогональним базисом з власних векторів. Набір її власних значень називається спектром графу, і є основним предметом вивчення спектральної теорії графів.

Два графи G₁ і G₂ з матрицями суміжності A₁ і A₂ є ізоморфними якщо і тільки якщо існує матриця перестановок P, така що PA₁P^-1 = A₂.

З цього випливає, що матриці A₁ і A₂ подібні, а значить мають рівні набори власних значень, визначників і характеристичні многочлени. Проте зворотне твердження не завжди вірне — два графи з подібними матрицями суміжності можуть бути неізоморфними.

Степені матриці

Якщо A — матриця суміжності графу G, то матриця A^m володіє наступною властивістю: елемент в i-му рядку, j-му стовпці рівний числу шляхів з i-ї вершини в j-ю, що складаються з рівно m ребер.

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

Матриця суміжності і ^[en] є основними структурами даних, що використовуються для представлення графів в комп'ютерних програмах.

Використання матриці суміжності переважно тільки у разі щільних графів, з великим числом ребер, оскільки вона вимагає зберігання по одному біту даних для кожного елементу. Якщо граф розріджений, то велика частина пам'яті марно буде витрачатися на зберігання нулів, зате у разі щільних графів матриця суміжності достатньо компактно представляє граф в пам'яті.

У алгоритмах, що працюють із зваженими графами (наприклад в алгоритмі Флойда-Уоршола), елементи матриці суміжності замість чисел 0 і 1, вказуючих на присутність або відсутність ребра, часто містять ваги самих ребер. При цьому на місце відсутніх ребер ставлять деяке спеціальне значення, залежне від вирішуваної задачі, звичайно 0 або ${\displaystyle \infty }$.

Див. також

• Енергія графу
• Матриця інцидентності
• Матриця Кірхгофа (Матриця Лапласа)

Джерела

1. (англ.) Chris Godsil and Gordon Royle (2001), Algebraic Graph Theory. New York: Springer-Verlag.
2. (рос.) Березина Л. Ю. Графы и их применение: Пособие для учителей — М., 1979.
3. (рос.) Михеева В. С. Математические методы в экономической географии. Ч. 2. Приложение теории графов: Курс лекций — М., 1983.
4. (рос.) Голиков А. П., Трофимов А. М., Черванёв И. Г. Математические методы в географии — Х., 1986.