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

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

Означення

Матриця суміжності графу 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 або .

Див. також

Джерела

  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.