Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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


1. Визначення

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

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

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


2. Приклади

  • Нижче наведено приклад неорієнтованого графа і відповідної йому матриці суміжності A. Цей граф містить петлю навколо вершини 1, так що, залежно від конкретних програм, елемент a 11 може вважатися рівним або одиниці (як показано нижче), або двом.
Граф Матриця суміжності
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}
  • Матриця суміжності повного графа K n містить одиниці у всіх своїх елементах, крім головної діагоналі, на якій розташовані нулі.
  • Матриця суміжності порожнього графа, не містить жодного ребра, складається з одних нулів.

3. Властивості

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

Два графа G 1 і G 2 з матрицями суміжності A 1 і A 2 є ізоморфними якщо і тільки якщо існує перестановки матриця P, така що

PA 1 P -1 = A 2.

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


3.1. Ступені матриці

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

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

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

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

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


Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Матриця
Z-матриця
Трехдіагональная матриця
Трикутна матриця
Матриця як філософія
Кососімметрічная матриця
Матриця Якобі
Матриця (фото)
Стохастична матриця
© Усі права захищені
написати до нас
Рейтинг@Mail.ru