Матрица инцидентности: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Rubinbot (обсуждение | вклад) м бот: добавление заголовков в сноски; исправление двойных сносок, см. ЧаВо |
Glovacki (обсуждение | вклад) Нет описания правки |
||
Строка 2:
'''Матрица инцидентности''' — одна из форм представления [[Граф (математика)|графа]], в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их [[инцидентность]]).
В случае ориентированного графа каждой [[дуга (теория графов)|дуге]] <x,y> ставится в соответствие
== Пример ==
:{|class="wikitable" style="text-align: center"
![[Неориентированный граф|Граф]]
!Матрица инцидентности<ref>Строки соответствуют вершинам (от 1 до 6), столбцы — рёбрам (1-2, 2-3, 3-4, 4-5, 1-5, 2-5, 4-6)</ref>
Строка 22:
== Особенности данного представления ==
* Используется для любых графов, даже если есть петля.
* В каждом столбце обязательно должны стоять две единицы (либо 1 и
== См. также ==
* [[Матрица смежности]]▼
▲*[[Матрица смежности]]
== Примечания ==
Строка 32 ⟶ 31 :
== Литература ==
# Харари Ф. ''Теория графов.''
[[Категория:Типы матриц]]
Строка 38 ⟶ 37 :
[[Категория:Графы (структуры данных)]]
[[Категория:Алгебраическая теория графов]]
|