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

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

Определение:

Матрицей инцидентности (инциденций) неориентированного графа называется матрица [math]I (|V| \times |E|)[/math], для которой [math]I_{i,j} = 1[/math], если вершина [math]v_i[/math] инцидентна ребру [math]e_j[/math], в противном случае [math]I_{i,j} = 0[/math].

Определение:

Матрицей инцидентности (инциденций) ориентированного графа называется матрица [math]I (|V| \times |E|)[/math], для которой [math]I_{i,j} = 1[/math], если вершина [math]v_i[/math] является началом дуги [math]e_j[/math], [math]I_{i,j} = -1[/math], если [math]v_i[/math] является концом дуги [math]e_j[/math], в остальных случаях [math]I_{i,j} = 0[/math].

Пример

Граф	Матрица инцидентности	Ориентированный граф	Матрица инцидентности
	[math]\begin{pmatrix} 1 & 1 & 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 0\\ \end{pmatrix}[/math]		[math]\begin{pmatrix} -1 & 1 & -1 & 0 & -1 & 0\\ 1 & 0 & 0 & -1 & 0 & 0\\ 0 & -1 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & -1\\ 0 & 0 & 0 & 1 & 1 & 0\\ \end{pmatrix}[/math]

Источники

Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.