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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Визначення[ред.ред. код]

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

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

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

Приклади[ред.ред. код]

Маркований граф Матриця суміжності
6n-graph2.svg \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.

Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg


The Граф Науру

Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg


Координати 0-23.
Білі клітинки — нулі, кольорові клітинки — одиниці.

Symmetric group 4; Cayley graph 4,9; numbers.svg


Орієнтований Граф Келі S4

Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg


Оскільки граф є орієнтованим,
матриця не симетрична.

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

Властивості[ред.ред. код]

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

Два графи G1 і G2 з матрицями суміжності A1 і A2 є ізоморфними якщо і тільки якщо існує матриця перестановок P, така що PA1P-1 = A2.

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

Степені матриці[ред.ред. код]

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

Структура даних[ред.ред. код]

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

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

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

Див. також[ред.ред. код]

Джерела[ред.ред. код]

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