Матриця суміжності — один із способів представлення графу у вигляді матриці.
Означення
Матриця суміжності графу G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) — це квадратна матриця A розміру n, в якій значення елементу aij рівне числу ребер з i-ї вершини графу в j-у вершину.
Іноді, особливо у разі неорієнтованого графу, петля (ребро з i-ї вершини в саму себе) вважається за два ребра, тобто значення діагонального елементу aii в цьому випадку рівне подвоєному числу петель навколо i-ї вершини.
Матриця суміжності простого графу (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.
Приклади
Маркований графМатриця суміжностіКоординати 1-6.Граф НауруКоординати 0-23.Білі клітинки — нулі, кольорові клітинки — одиниці.Орієнтований Граф Келі S4Оскільки граф є орієнтованим, матриця не симетрична.
Матриця суміжності повного графу Kn містить одиниці у всіх своїх елементах, окрім головної діагоналі, на якій розташовані нулі.
Матриця суміжності порожнього графу, що не містить жодного ребра, складається лише з нулів.
Властивості
Матриця суміжності неорієнтованого графу симетрична, а значить володіє дійсними власними значеннями і ортогональним базисом з власних векторів. Набір її власних значень називається спектром графу, і є основним предметом вивчення спектральної теорії графів.
Два графи G1 і G2 з матрицями суміжності A1 і A2 є ізоморфними якщо і тільки якщо існує матриця перестановок P, така що PA1P-1 = A2.
З цього випливає, що матриці A1 і A2 подібні, а значить мають рівні набори власних значень, визначників і характеристичні многочлени. Проте зворотне твердження не завжди вірне — два графи з подібними матрицями суміжності можуть бути неізоморфними.
Степені матриці
Якщо A — матриця суміжності графу G, то матриця Am володіє наступною властивістю: елемент в i-му рядку, j-му стовпці рівний числу шляхів з i-ї вершини в j-ю, що складаються з рівно m ребер.
Структура даних
Матриця суміжності і списки суміжності є основними структурами даних, що використовуються для представлення графів в комп'ютерних програмах.
Використання матриці суміжності переважно тільки у разі щільних графів, з великим числом ребер, оскільки вона вимагає зберігання по одному біту даних для кожного елементу. Якщо граф розріджений, то велика частина пам'яті марно буде витрачатися на зберігання нулів, зате у разі щільних графів матриця суміжності достатньо компактно представляє граф в пам'яті.
У алгоритмах, що працюють із зваженими графами (наприклад в алгоритмі Флойда-Уоршола), елементи матриці суміжності замість чисел 0 і 1, вказуючих на присутність або відсутність ребра, часто містять ваги самих ребер. При цьому на місце відсутніх ребер ставлять деяке спеціальне значення, залежне від вирішуваної задачі, звичайно 0 або .
Див. також Енергія графу Матриця інцидентності Матриця Кірхгофа (Матриця Лапласа)
Джерела
Chris Godsil and Gordon Royle (2001), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1 Березина Л. Ю. Графы и их применение: Пособие для учителей — М., 1979. Михеева В. С. Математические методы в экономической географии. Ч. 2. Приложение теории графов: Курс лекций — М., 1983.