Матриця суміжності — один із способів представлення графу у вигляді матриці.
Означення
Матриця суміжності графу G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) — це квадратна матриця A розміру n, в якій значення елементу aij рівне числу ребер з i-ї вершини графу в j-у вершину.
Іноді, особливо у разі неорієнтованого графу, петля (ребро з i-ї вершини в саму себе) вважається за два ребра, тобто значення діагонального елементу aii в цьому випадку рівне подвоєному числу петель навколо i-ї вершини.
Матриця суміжності простого графу (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.
Приклади
Матриця суміжності | |
---|---|
![]() | Координати 1-6. |
![]()
| ![]()
|
![]() | ![]()
|
- Матриця суміжності повного графу Kn містить одиниці у всіх своїх елементах, окрім головної діагоналі, на якій розташовані нулі.
- Матриця суміжності порожнього графу, що не містить жодного ребра, складається лише з нулів.
Властивості
Матриця суміжності неорієнтованого графу симетрична, а значить володіє дійсними (власними значеннями) і ортогональним базисом з власних векторів. Набір її власних значень називається (спектром графу), і є основним предметом вивчення спектральної теорії графів.
Два графи G1 і G2 з матрицями суміжності A1 і A2 є ізоморфними якщо і тільки якщо існує матриця перестановок P, така що PA1P-1 = A2.
З цього випливає, що матриці A1 і A2 подібні, а значить мають рівні набори власних значень, визначників і характеристичні многочлени. Проте зворотне твердження не завжди вірне — два графи з подібними матрицями суміжності можуть бути неізоморфними.
Степені матриці
Якщо A — матриця суміжності графу G, то матриця Am володіє наступною властивістю: елемент в i-му рядку, j-му стовпці рівний числу шляхів з i-ї вершини в j-ю, що складаються з рівно m ребер.
Структура даних
Матриця суміжності і [en] є основними структурами даних, що використовуються для представлення графів в комп'ютерних програмах.
Використання матриці суміжності переважно тільки у разі щільних графів, з великим числом ребер, оскільки вона вимагає зберігання по одному біту даних для кожного елементу. Якщо граф розріджений, то велика частина пам'яті марно буде витрачатися на зберігання нулів, зате у разі щільних графів матриця суміжності достатньо компактно представляє граф в пам'яті.
У алгоритмах, що працюють із зваженими графами (наприклад в алгоритмі Флойда-Уоршола), елементи матриці суміжності замість чисел 0 і 1, вказуючих на присутність або відсутність ребра, часто містять ваги самих ребер. При цьому на місце відсутніх ребер ставлять деяке спеціальне значення, залежне від вирішуваної задачі, звичайно 0 або .
Див. також
- (Енергія графу)
- Матриця інцидентності
- Матриця Кірхгофа (Матриця Лапласа)
Джерела
- (англ.) Chris Godsil and Gordon Royle (2001), Algebraic Graph Theory. New York: Springer-Verlag.
- (рос.) Березина Л. Ю. Графы и их применение: Пособие для учителей — М., 1979.
- (рос.) Михеева В. С. Математические методы в экономической географии. Ч. 2. Приложение теории графов: Курс лекций — М., 1983.
- (рос.) Голиков А. П., Трофимов А. М., Черванёв И. Г. Математические методы в географии — Х., 1986.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет