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

Матрица инцидентности - это матрица вершин и инцидентных им дуг.

Дуга инцидентна вершине, если эта дуга исходит или заходит в данную вершину.

Вершина инцидентна дуге, если в эту вершину заходит или исходит данная дуга.

В матрице инцидентности в первом столбце расположены вершины, в первой строке – дуги. Остальные ячейки матрицы инцидентности заполняются по следующему правилу:

· , если из i-той вершины исходит j-тая дуга:

· , если в i-той вершину заходит j-тая дуга;

· , если i-тая вершина не инцидента j-той дуге;

· , если из i-той вершины исходит j-тая дуга и в нее же заходит, т.е. в i-той вершине j-тая дуга образует петлю.

Для графа, представленного на рис. 3.2 матрица инцидентности имеет вид:

		-1	+1			+1	-1
		+1
			-1	-1
				+1	-1
					+1	-1
							+1

На практике в матрице инцидентности иногда нули не проставляются для наглядности.

		-1	+1			+1	-1
		+1
			-1	-1
				+1	-1
					+1	-1
							+1

Свойство матрицы инцидентности – сумма элементов по столбцам равна 0 или 2.