Матриця інціденцій, h4s

Матриця інціденцій - таблиця, яка містить набір рядків і стовпців. Кожен рядок відповідає вузлу, а кожен стовпець - гілки графа. Якщо гілка з номером спрямована від вузла то в i-му рядку і j-му стовпці записуємо +1. Якщо i-ая гілка спрямована до вузла, то в i-му рядку і j-му стовпці записуємо -1. Всі інші елементи матриці інціденцій дорівнюють нулю.

Матриця інціденцій дає повний опис спрямованого графа. За допомогою матриці інціденцій зручно записувати рівняння за першим законом Кірхгофа в матричному вигляді:

де M - матриця інціденцій,
IB - матриця струмів гілок,
J - матриця заданих струмів в вузлах.

Топологічні матриці дозволяють формалізувати запис рівнянь за законами Кірхгофа. що дуже важливо з точки зору машинних розрахунків.

Матриця інціденцій являє собою прямокутну матрицю розміром n x m, де n - кількість вершин графа, а m - кількість дугграфа. Позначається матриця інціденцій B = ij>, i = 1, 2, ..., n, j = 1, 2, ..., m.

Кожен елемент матриці визначається наступним чином:

bij = 1, якщо хi є початковою вершиною дуги aj,

bij = -1, якщо хi є кінцевою вершиною дуги aj,

bij = 0, якщо хi не є кінцевою вершиною дуги aj або якщо aj є петлею.

На рис. 1.5. а, б наведено граф і його матриця суміжності, по якій можна знайти характеристики вершин. Так сума елементів i -ої рядки матриці дає полустепені результату вершини хi. а сума елементів i-го стовпця дає полустепені заходу вершини хi. По матриці смежностіможно знайти прямі і зворотні відображення. Розглянемо i -ю рядок матриці. Якщо елемент aij = 1, то елемент графа хj входить в відображення Г (хi). Наприклад, у 2-му рядку матриці А (рис. 1.5, б) одиниці стоять в 2-м і 5-м шпальтах, отже, Г (х2) = <х2. х5>.

Мал. 1.5. Орграф і його матричне уявлення: а - орграф; б - матриця суміжності; в - матриця інціденцій

Для графа на рис. 1.5, а матриця інціденцій приведена на рис. 1.5, в. Оскільки кожна дуга инцидентна двом різним вершин, за винятком того випадку, коли дуга утворює петлю, то кожен стовпець або містить один елемент рівний 1 і один - рівний - 1, або всі елементи стовпця дорівнюють 0.

Для неорієнтованого графа, матриця інціденцій визначається так само, за винятком того, що всі елементи, рівні -1, замінюються на 1.