Що таке матриця інцидентності?
Матриця інцидентності - це матриця, яка представляє граф так, що за допомогою цієї матриці можна намалювати граф. Цю матрицю можна позначити як [AC]. Як і в кожній матриці, в матриці інцидентності [AC] є рядки та стовпці.
Рядки матриці [AC] представляють кількість вершин, а стовпці матриці [AC] представляють кількість гілок у даному графі. Якщо в даній матриці інцидентності є 'n' рядків, це означає, що в графі є 'n' вершин. Аналогічно, якщо в даній матриці інцидентності є 'm' стовпців, це означає, що в графі є 'm' гілок.
У вищенаведеному графі або орієнтованому графі є 4 вершини та 6 гілки. Тому матриця інцидентності для цього графу буде мати 4 рядки та 6 стовпці.
Значення елементів матриці інцидентності завжди дорівнюють -1, 0, +1. Ця матриця завжди аналогічна KCL (Закон Кірхгофа для струму). Отже, з KCL ми можемо отримати, що,
| Тип гілки | Значення |
| Вихідна гілка з k-ї вершини | +1 |
| Вхідна гілка до k-ї вершини | -1 |
| Інші | 0 |
Кроки побудови матриці інцидентності
Нижче наведені кроки для побудови матриці інцидентності:
Якщо задана k-та вершина має вихідну гілку, то ми запишемо +1.
Якщо задана k-та вершина має вхідну гілку, то ми запишемо -1.
Інші гілки будуть розглянуті як 0.
Приклади матриці інцидентності
Для вищенаведеного графу напишіть його матрицю інцидентності.
Зменшена матриця інцидентності
Якщо з заданої матриці інцидентності [AC] будь-який довільний рядок видаляється, то нова утворена матриця буде зменшеною матрицею інцидентності. Вона позначається символом [A]. Порядок зменшеної матриці інцидентності становить (n-1) × b, де n - кількість вершин, а b - кількість гілок.
Для вищенаведеного графу зменшена матриця інцидентності буде наступною:
[ПРИМІТКА: У вищенаведеній матриці рядок 4 видалений.]
Зараз розглянемо новий приклад, пов'язаний з зменшеною матрицею інцидентності. Для вищенаведеного графу напишіть його зменшену матрицю інцидентності.
Відповідь: Для побудови зменшеної матриці інцидентності спочатку треба побудувати матрицю інцидентності. Її матриця інцидентності буде наступною:
Тепер побудуємо зменшену матрицю інцидентності. Для цього просто потрібно видалити будь-яку вершину (у цьому випадку ми видалили вершину 2). Зменшена матриця інцидентності буде наступною:
Це шуканий результат.
Пам'ятайте
Для перевірки правильності побудованої матриці інцидентності, ми повинні перевірити суму стовпців.
Якщо сума стовпця дорівнює нулю, то матриця інцидентності, яку ми побудували, правильна, інакше - неправильна.
Матриця інцидентності може бути застосована лише до орієнтованого графу.
Кількість входжень у рядку, окрім нулів, повідомляє нам кількість гілок, пов'язаних з цією вершиною. Це також називається степенем цієї вершини.
Ранг повної матриці інцидентності становить (n-1), де n - кількість вершин графу.
Порядок матриці інцидентності становить (n × b), де b - кількість гілок графу.
З заданої зменшеної
