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

Матрица инцидентности -((Vertex-edge) incidence matrix) - (0,1)-матрица [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]-й элемент которой равен 1, если вершина [math]\displaystyle{ v_{i} }[/math] инцидентна ребру [math]\displaystyle{ e_{j} }[/math] в неориентированном графе или если [math]\displaystyle{ v_{i} }[/math] есть начало дуги [math]\displaystyle{ e_{j} }[/math] равен -1, если вершина [math]\displaystyle{ v_{i} }[/math] есть конец дуги [math]\displaystyle{ e_{j} }[/math] (только для орграфов), и равен 0 в остальных случаях.

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

Литература

[Лекции]