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

Инцидентность ребра и вершины

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

Рассмотрим граф [math]G = (V,E)[/math]. Вершина [math]v \in V[/math] и ребро [math]e \in E[/math] инцидентны, если [math]\exist u \in V :(uv) \in E[/math].

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

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

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

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

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