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

Материал из WikiGrapp
Версия от 12:35, 4 мая 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Матрица инцидентности ((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 в остальных случаях.

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

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.