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

Матрица инцидентности ((Vertex-edge) incidence matrix) — [math]\displaystyle{ \,(0,1) }[/math]-матрица [math]\displaystyle{ \,I(G) }[/math] размером [math]\displaystyle{ n \times m }[/math] ([math]\displaystyle{ \,n }[/math] - число вершин, [math]\displaystyle{ \,m }[/math] - число ребер/дуг графа [math]\displaystyle{ \,G }[/math]), [math]\displaystyle{ \,(i,j) }[/math]-й элемент которой равен [math]\displaystyle{ \,1 }[/math], если вершина [math]\displaystyle{ \,v_{i} }[/math] инцидентна ребру [math]\displaystyle{ \,e_{j} }[/math] в неориентированном графе или если [math]\displaystyle{ \,v_{i} }[/math] есть начало дуги [math]\displaystyle{ \,e_{j} }[/math] равен [math]\displaystyle{ \,-1 }[/math], если вершина [math]\displaystyle{ \,v_{i} }[/math] есть конец дуги [math]\displaystyle{ \,e_{j} }[/math] (только для орграфов), и равен [math]\displaystyle{ \,0 }[/math] в остальных случаях.

Матрица инцидентности определяет граф с точностью до изоморфизма.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.