Матрица инцидентности: различия между версиями
Перейти к навигации
Перейти к поиску
[непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
→Преамбула: Изменено значение -1 при входящей дуге, 1 при исходящей указано верно. |
отмена правки 80061366 участника 46.32.85.141 (обс) Было правильно, переписал проще |
||
Строка 2: | Строка 2: | ||
'''Матрица инцидентности''' — одна из форм представления [[Граф (математика)|графа]], в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их [[инцидентность]]). |
'''Матрица инцидентности''' — одна из форм представления [[Граф (математика)|графа]], в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их [[инцидентность]]). |
||
В случае ориентированного графа каждой [[дуга (теория графов)|дуге]] <x,y> ставится в |
В случае ориентированного графа каждой [[дуга (теория графов)|дуге]] <x,y> ставится в соответствующем столбце: «-1» в строке вершины x и «1» в строке вершины y; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0». |
||
== Пример == |
== Пример == |
Версия от 17:22, 10 августа 2016
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждой дуге <x,y> ставится в соответствующем столбце: «-1» в строке вершины x и «1» в строке вершины y; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0».
Пример
Особенности данного представления
- Используется для любых графов, даже если есть петля.
- В каждом столбце обязательно должны стоять две единицы (либо 1 и −1 в случае ориентированного графа).
- Может использоваться для представления гиперграфов (в этом случае столбец может содержать больше двух единиц)
См. также
Примечания
- ↑ Строки соответствуют вершинам (от 1 до 6), столбцы — рёбрам (1-2, 2-3, 3-4, 4-5, 1-5, 2-5, 4-6)
Литература
- Харари Ф. Теория графов. — М.: Мир. — 1973. — 300 с.