Матриця інцидентності - студопедія

Говорити про те, що ребро g і кожна з вершин u і y инцидентна g. варто лише в тому випадку, якщо g з'єднує u і y. Усвідомивши це, перейдемо до розгляду даного методу. Матриця інцидентності будуватися за схожим, але не за тим же принципом, що і матриця суміжності. Так якщо остання має розмір n × n. де n - число вершин, то матриця інцидентності - n × m. тут n - число вершин графа, m - число ребер. Тобто тепер щоб задати значення якого-небудь осередку, потрібно зіставити НЕ вершину з вершиною, а вершину з ребром.

У кожного осередку матриці інцидентності неориентированного графа варто 0 або 1, а в разі орієнтованого графа. вносяться 1, 0 або -1. Те ж саме, але найбільш структуроване:

1. неорієнтовані граф:

· 1 - вершина инцидентна ребру;

· 0 - вершини не инцидентна ребру.

2. орієнтований граф:

· 1 - вершина инцидентна ребру, і є його початком;

· 0 - вершини не инцидентна ребру;

· -1 - вершина инцидентна ребру, і є його кінцем.

Побудуємо матрицю інцидентності спочатку для неорієнтованого графа (рис. 3.10), а потім для орграфа (рис. 3.11). Ребра позначимо буквами від a до e, вершини - цифрами. Всі ребра графа не направлення, тому матриця інцидентності заповнена позитивними значеннями.

Малюнок 3.10 - неорієнтовані граф і його матриця інцидентності

Для орграфа матриця має трохи інший вигляд. У кожну з її осередків внесено одне з трьох значень. Зверніть увагу, що нулі в двох цих матрицях займають однакові позиції, адже в обох випадках структура графа одна. Але деякі позитивні одиниці змінилися на негативні, наприклад, в неорієнтованому графі осередок (1, b) містить 1, а в орграфе -1. Справа в тому, що в першому випадку ребро b не направлення, а в другому - спрямоване, і, причому вершиною входу для нього є вершина «1».

Малюнок 3.11 - Орієнтований граф і його матриця інцидентності

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