Матрица инцидентности: различия между версиями
Перейти к навигации
Перейти к поиску
[отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Stannic (обсуждение | вклад) категория |
Фраза, которая была исправлена, имела смысл для матрицы смежностей, в которой описываются связи между вершинами. |
||
Строка 2: | Строка 2: | ||
'''Матрица инцидентности''' — одна из форм представления [[Граф (математика)|графа]], в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их [[инцидентность]]). |
'''Матрица инцидентности''' — одна из форм представления [[Граф (математика)|графа]], в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их [[инцидентность]]). |
||
В случае ориентированного графа |
В случае ориентированного графа каждой [[ребро (теория графов)|дуге]] <x,y> ставится в соответствие "-1" в строке вершины x и столбце дуги <x,y> и "1" в строке вершины y и столбце дуги <x,y>; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится "0". |
||
== Пример == |
== Пример == |
Версия от 08:55, 3 сентября 2013
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждой дуге <x,y> ставится в соответствие "-1" в строке вершины x и столбце дуги <x,y> и "1" в строке вершины y и столбце дуги <x,y>; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится "0".
Пример
Граф Матрица инцидентности
Особенности данного представления
- Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом.
- В каждом столбце должны стоять две единицы (либо 1 и -1 в случае ориентированного графа), а все остальные символы — нули.
См. также
Литература
- Харари Ф. Теория графов. — М.: Мир. — 1973. — 300 с.