Матрица инцидентности: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Stannic (обсуждение | вклад) отмена правки 75818877 участника 46.167.74.176 (обс) рассогласование |
|||
| Строка 6: | Строка 6: | ||
== Пример == |
== Пример == |
||
:{|class="wikitable" style="text-align:center" |
:{|class="wikitable" style="text-align:center" |
||
|+ |
|||
![[Неориентированный граф|Граф]] |
![[Неориентированный граф|Граф]] |
||
!Матрица инцидентности |
!Матрица инцидентности |
||
| Строка 12: | Строка 11: | ||
|[[Image:Graph123.png|175px]] |
|[[Image:Graph123.png|175px]] |
||
|<math>\begin{pmatrix} |
|<math>\begin{pmatrix} |
||
1 & |
1 & 0 & 0 & 0 & 1 & 0 & 0\\ |
||
1 & 0 & 0 & 0 & 1 & 0 |
1 & 1 & 0 & 0 & 0 & 1 & 0\\ |
||
0 & 1 & |
0 & 1 & 1 & 0 & 0 & 0 & 0\\ |
||
0 & |
0 & 0 & 1 & 1 & 0 & 0 & 1\\ |
||
0 & 0 & 0 & 1 & 1 & |
0 & 0 & 0 & 1 & 1 & 1 & 0\\ |
||
0 & 0 & |
0 & 0 & 0 & 0 & 0 & 0 & 1\\ |
||
0 & 0 &0 & 1 & 0 & 0 \\ |
|||
\end{pmatrix}</math> |
\end{pmatrix}</math> |
||
|} |
|} |
||
Версия от 22:34, 16 января 2016
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждой дуге <x,y> ставится в соответствие "-1" в строке вершины x и столбце дуги <x,y> и "1" в строке вершины y и столбце дуги <x,y>; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится "0".
Пример
Граф Матрица инцидентности 
Особенности данного представления
- Используется для любых графов, даже если есть петля.
- В каждом столбце обязательно должны стоять две единицы (либо 1 и -1 в случае ориентированного графа).
См. также
Литература
- Харари Ф. Теория графов. — М.: Мир. — 1973. — 300 с.