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

Матриця інцидентності - це матриця, яка представляє граф так, що за допомогою цієї матриці можна намалювати граф. Цю матрицю можна позначити як [AC]. Як і в кожній матриці, в матриці інцидентності [AC] є рядки та стовпці.
Рядки матриці [AC] представляють кількість вершин, а стовпці матриці [AC] представляють кількість гілок у даному графі. Якщо в даній матриці інцидентності є 'n' рядків, це означає, що в графі є 'n' вершин. Аналогічно, якщо в даній матриці інцидентності є 'm' стовпців, це означає, що в графі є 'm' гілок.

У вищенаведеному графі або орієнтованому графі є 4 вершини та 6 гілки. Тому матриця інцидентності для цього графу буде мати 4 рядки та 6 стовпці.
Значення елементів матриці інцидентності завжди дорівнюють -1, 0, +1. Ця матриця завжди аналогічна KCL (Закон Кірхгофа для струму). Отже, з KCL ми можемо отримати, що,

Кроки побудови матриці інцидентності

Нижче наведені кроки для побудови матриці інцидентності:

1. Якщо задана k-та вершина має вихідну гілку, то ми запишемо +1.

2. Якщо задана k-та вершина має вхідну гілку, то ми запишемо -1.

3. Інші гілки будуть розглянуті як 0.

Приклади матриці інцидентності

Для вищенаведеного графу напишіть його матрицю інцидентності.

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

Якщо з заданої матриці інцидентності [AC] будь-який довільний рядок видаляється, то нова утворена матриця буде зменшеною матрицею інцидентності. Вона позначається символом [A]. Порядок зменшеної матриці інцидентності становить (n-1) × b, де n - кількість вершин, а b - кількість гілок.
Для вищенаведеного графу зменшена матриця інцидентності буде наступною:

[ПРИМІТКА: У вищенаведеній матриці рядок 4 видалений.]
Зараз розглянемо новий приклад, пов'язаний з зменшеною матрицею інцидентності. Для вищенаведеного графу напишіть його зменшену матрицю інцидентності.

Відповідь: Для побудови зменшеної матриці інцидентності спочатку треба побудувати матрицю інцидентності. Її матриця інцидентності буде наступною:

Тепер побудуємо зменшену матрицю інцидентності. Для цього просто потрібно видалити будь-яку вершину (у цьому випадку ми видалили вершину 2). Зменшена матриця інцидентності буде наступною:

Це шуканий результат.
Пам'ятайте

• Для перевірки правильності побудованої матриці інцидентності, ми повинні перевірити суму стовпців.

• Якщо сума стовпця дорівнює нулю, то матриця інцидентності, яку ми побудували, правильна, інакше - неправильна.

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

• Кількість входжень у рядку, окрім нулів, повідомляє нам кількість гілок, пов'язаних з цією вершиною. Це також називається степенем цієї вершини.

• Ранг повної матриці інцидентності становить (n-1), де n - кількість вершин графу.

• Порядок матриці інцидентності становить (n × b), де b - кількість гілок графу.

• З заданої зменшеної

  Нагорода