Матрица инцидентности: различия между версиями
Перейти к навигации
Перейти к поиску
[непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Stannic (обсуждение | вклад) →Пример: комментарий |
Rubinbot (обсуждение | вклад) м бот: добавление заголовков в сноски; исправление двойных сносок, см. ЧаВо |
||
Строка 27: | Строка 27: | ||
*[[Матрица смежности]] |
*[[Матрица смежности]] |
||
== Примечания == |
|||
{{примечания}} |
|||
== Литература == |
== Литература == |
Версия от 15:36, 4 февраля 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 с.