Матрица инцидентности

Говорить о том, что ребро 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 когда это ориентированное ребро, все остальное в нем – нули.

В программе матрица инцидентности задается, также как и матрица смежности, а именно при помощи двумерного массива. Его элементы могут быть инициализированы при объявлении, либо по мере выполнения программы.