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

Материал из WEGA
Версия от 14:20, 3 июля 2009; KEV (обсуждение | вклад) (Создана новая страница размером '''Матрица инцидентности''' -((Vertex-edge) incidence matrix) - (0,1)-матриц...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

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

Литература

[Лекции]