матриця інцидентності
Говорити про те, що ребро g і кожна з вершин u і y инцидентна g. варто лише в тому випадку, якщо g з'єднує u і y. Усвідомивши це, перейдемо до розгляду даного методу. Матриця інцидентності будуватися за схожим, але не за тим же принципом, що і матриця суміжності. Так якщо остання має розмір n × n, де n - число вершин, то матриця інцидентності - n × m. тут n - число вершин графа, m - число ребер. Тобто тепер щоб задати значення якого-небудь осередку, потрібно зіставити НЕ вершину з вершиною, а вершину з ребром.
У кожного осередку матриці інцидентності неориентированного графа варто 0 або 1, а в разі орієнтованого графа. вносяться 1, 0 або -1. Те ж саме, але найбільш структуроване:
- неорієнтовані граф
- 1 - вершина инцидентна ребру
- 0 - вершини не инцидентна ребру
- орієнтований граф
- 1 - вершина инцидентна ребру, і є його початком
- 0 - вершини не инцидентна ребру
- -1 - вершина инцидентна ребру, і є його кінцем
Побудуємо матрицю інцидентності спочатку для неорієнтованого графа, а потім для орграфа.
Ребра позначені буквами від a до e. вершини - цифрами. Всі ребра графа не направлення, тому матриця інцидентності заповнена позитивними значеннями.
Для орграфа графа матриця має трохи інший вигляд. У кожну з її осередків внесено одне з трьох значень. Зверніть увагу, що нулі в двох цих матрицях (рис. 1 і 2) займають однакові позиції, адже в обох випадках структура графа одна. Але деякі позитивні одиниці змінилися на негативні, наприклад, в неорієнтованому графі осередок (1, b) містить 1, а в орграфе -1. Дійсно, це доречно, т. К. В першому випадку ребро b не направлення, а в другому - спрямоване, і, причому вершиною входу для нього є вершина «1».
Кожен стовпець відповідає за будь-яке одне ребро, тому граф, описаний за допомогою матриці інцидентності, завжди буде мати наступний ознака: будь-який з стовпців матриці інцидентності містить дві одиниці, або 1 і -1 коли це орієнтоване ребро, все інше в ньому - нулі .