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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Литература

[Лекции]