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

Материал из Викиконспекты
Версия от 05:07, 14 октября 2010; 192.168.0.2 (обсуждение) (добавлен источник)
Перейти к: навигация, поиск

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

Определение:
Инцидентность - отношение между ребром и его концевыми вершинами, т. е. если в графе [math]G = (V,E) [/math] [math]u \in V, v \in V[/math] - вершины, а [math]e \in E[/math] - соединяющее их ребро (e = (u,v)), то вершина u и ребро e инцидентны, вершина v и ребро e также инцидентны.


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

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


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


Источники

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.