Матрица инцидентности: различия между версиями
Перейти к навигации
Перейти к поиску
[отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Freezeman (обсуждение | вклад) м →Пример |
Бертран (обсуждение | вклад) |
||
Строка 23: | Строка 23: | ||
== Особенности данного представления == |
== Особенности данного представления == |
||
* Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом. |
* Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом. |
||
* В каждом столбце должны стоять две единицы, а все остальные символы |
* В каждом столбце должны стоять две единицы (либо 1 и -1 в случае ориентированного графа), а все остальные символы — нули. |
||
== См. также == |
== См. также == |
Версия от 08:36, 3 февраля 2013
Для улучшения этой статьи желательно:
|
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".
Пример
Граф Матрица инцидентности
Особенности данного представления
- Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом.
- В каждом столбце должны стоять две единицы (либо 1 и -1 в случае ориентированного графа), а все остальные символы — нули.