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

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

Пример

Граф	Матрица инцидентности
	$\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix}$

Особенности данного представления

• Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом.
• В каждом столбце должны стоять две единицы (либо 1 и -1 в случае ориентированного графа), а все остальные символы — нули.

См. также

• Матрица смежности

Литература

1. Харари Ф. Теория графов. — М.: Мир. — 1973. — 300 с.