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

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


Матрица инцидентности определяет граф с точностью до [[изоморфизм графов|изоморфизма]].
Матрица инцидентности определяет граф с точностью до [[изоморфизм графов|изоморфизма]].
==Литература==
==Литература==
[Лекции]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
 
 
[[Категория:Неориентированные графы]]
 
[[Категория:Ориентированные графы]]

Текущая версия от 12:35, 4 мая 2011

Матрица инцидентности ((Vertex-edge) incidence matrix) — [math]\displaystyle{ \,(0,1) }[/math]-матрица [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]-й элемент которой равен [math]\displaystyle{ \,1 }[/math], если вершина [math]\displaystyle{ \,v_{i} }[/math] инцидентна ребру [math]\displaystyle{ \,e_{j} }[/math] в неориентированном графе или если [math]\displaystyle{ \,v_{i} }[/math] есть начало дуги [math]\displaystyle{ \,e_{j} }[/math] равен [math]\displaystyle{ \,-1 }[/math], если вершина [math]\displaystyle{ \,v_{i} }[/math] есть конец дуги [math]\displaystyle{ \,e_{j} }[/math] (только для орграфов), и равен [math]\displaystyle{ \,0 }[/math] в остальных случаях.

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

Литература

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