20503

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

Доклад

Информатика, кибернетика и программирование

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

Украинкский

2013-07-25

28 KB

33 чел.

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

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

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

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

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

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

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

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

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

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

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

матриця інцидентності

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

Кожна комірка матриці може набувати трьох значень:

1: якщо ребро виходить з  і входить у ;

-1: якщо ребро входить у  і виходить з ;

0: якщо між  і  немає ребра.


 

А также другие работы, которые могут Вас заинтересовать

69119. Динамічні змінні та динамічна пам’ять. Розподіл оперативної пам’яті. Поняття покажчика та його оголошення. Стандартні функції для роботи з адресами 93.5 KB
  Змінні величини, що розглядались у попередніх розділах, були статичними. Статичні змінні характеризуються тим, що їх значення зберігаютъся в ділянках оперативної пам’яті, які визначаються на етапі компіляції программ і не змінюються під час її виконання.
69120. Спискові структури даних. Визначення лінійного списку та його різновидів. Робота зі стеком, з чергою та лінійним списком 111 KB
  Визначення лінійного списку та його різновидів. Визначення лінійного списку та його різновидів 3. Визначення лінійного списку та його різновидів Як приклад розглянемо таку задачу. Кожен компонент списку крім останнього містить покажчик на наступний або на наступний попередній компонент.
69121. Дерева. Основні поняття. Алгоритм роботи з бінарними деревами 80 KB
  Розглянуті у розділі 10.2 списки, стеки та черги палежать до лінійних динамічних структур даних. Визначальною характеристикою лінійних структур є те, що зв’язок між іншими компонентами описується в терминах «попередній-наступний», тобто для кожного компонента лінійної структури...
69123. Масиви в динамічній пам’яті 37.5 KB
  Як уже зазначалось у розділі 10.2, зображення послідовностей однотипних у формі лінійних списків має і переваги, і недоліки. Основним недоліком є значна трудомісткістъ операції доступу до елемента лінійного списку за його номером. Цей недолік непритаманний масивам.
69124. Поняття архітектури комп’ютера. Архітектура комп’ютера фон Неймана. Типи комп’ютерів. Програмне забезпечення 192 KB
  Поняття архітектури обчислювальних систем є одним з основних в інформатиці. Уперше термін «архітектура комп’ютера» був введений фірмою IBM при розробці обчислювальних систем серії IBM 360 і застосований до тих засобів, які може використовувати програміст під час написання програм на рівні машинних команд.
69125. Засоби створення програм. Класифікація мов програмування. Технологія створення программ 74 KB
  Основна функція всіх мов програмування крім машинної полягає у тому щоб надати програмісту засоби абстрагування від характеристик та особливостей апаратного забезпечення на якому виконуватимуться програми. Такий спосіб написання програм називається програмуванням у числових кодах...
69126. Поняття алгоритму й основні алгоритмічні структури. Властивості та способи опису алгоритму. Алгоритмічна структура розгалуження і перетворення 56.5 KB
  Одним з базових понять інформатики є поняття алгоритму. Алгоритм вказує, які операції, пов’язані з обробкою даних, і в якій послідовності треба виконати, щоб отримати розв’язок задачі. Алгоритм розрахований на певного виконавця, з погляду котрого вказівки мають бути елементарними...
69127. Робота у середовищі Borland Pascal 7.0 202.5 KB
  Інтегроване середовище розробки Borland Pascal 7.0 - далі IDE (Integrated Development Environment) Borland Pascal 7.0 - складається з текстового редактора, компілятора, компонувальника, налагоджувача і довідкової системи. Стандартна поставка IDE Borland Pascal 7.0 являє собою...