4625
правок
Матрица инцидентности: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Матрица инцидентности''' | '''Матрица инцидентности''' ([[(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. | |||