Матрица инцидентности: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Glovacki (обсуждение | вклад) Нет описания правки |
Нет описания правки |
||
| Строка 17: | Строка 17: | ||
0 & 0 & 0 & 1 & 1 & 1 & 0\\ |
0 & 0 & 0 & 1 & 1 & 1 & 0\\ |
||
0 & 0 & 0 & 0 & 0 & 0 & 1\\ |
0 & 0 & 0 & 0 & 0 & 0 & 1\\ |
||
\end{pmatrix}</math> |
\end{pmatrix}</math><!-- |
||
|- |
|||
|colspan=2|<references group="a" />--> |
|||
|} |
|} |
||
== Особенности данного представления == |
== Особенности данного представления == |
||
# Используется для любых графов, даже если есть петля. |
|||
# В каждом столбце обязательно должны стоять две единицы (либо 1 и −1 в случае ориентированного графа). |
|||
# Может использоваться для представления [[гиперграф]]ов (в этом случае столбец может содержать больше двух единиц) |
|||
== См. также == |
== См. также == |
||
Версия от 09:09, 2 апреля 2016
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждой дуге <x,y> ставится в соответствие «-1» в строке вершины x и столбце дуги <x,y> и «1» в строке вершины y и столбце дуги <x,y>; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0».
Пример
Особенности данного представления
- Используется для любых графов, даже если есть петля.
- В каждом столбце обязательно должны стоять две единицы (либо 1 и −1 в случае ориентированного графа).
- Может использоваться для представления гиперграфов (в этом случае столбец может содержать больше двух единиц)
См. также
Примечания
- ↑ Строки соответствуют вершинам (от 1 до 6), столбцы — рёбрам (1-2, 2-3, 3-4, 4-5, 1-5, 2-5, 4-6)
Литература
- Харари Ф. Теория графов. — М.: Мир. — 1973. — 300 с.