Матрица инцидентности графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение матрицы инцидентностей)
(нет различий)

Версия 08:27, 3 октября 2010

Матрица инцидентностей для ориентированного и неориентированного графов

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

Определение:
Рассмотрим граф [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 в остальных случаях.