Матрица инцидентности графа — различия между версиями
(→Инцидентность ребра и вершины) |
м (rollbackEdits.php mass rollback) |
||
(не показано 8 промежуточных версий 7 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | == Определения для ориентированного и неориентированного графов == |
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | ''' | + | '''Матрицей инцидентности''' (инциденций) ''(англ. Incidence matrix)'' неориентированного графа называется матрица <tex>I (|V| \times |E|)</tex>, для которой <tex>I_{i,j} = 1</tex>, если вершина <tex>v_i</tex> инцидентна ребру <tex>e_j</tex>, в противном случае <tex>I_{i,j} = 0</tex>. |
}} | }} | ||
− | |||
− | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Матрицей инцидентности''' (инциденций) | + | '''Матрицей инцидентности''' (инциденций) ''(англ. Incidence matrix)'' ориентированного графа называется матрица <tex>I (|V| \times |E|)</tex>, для которой <tex>I_{i,j} = 1</tex>, если вершина <tex>v_i</tex> является началом дуги <tex>e_j</tex>, <tex>I_{i,j} = -1</tex>, если <tex>v_i</tex> является концом дуги <tex>e_j</tex>, в остальных случаях <tex>I_{i,j} = 0</tex>. |
}} | }} | ||
− | {{ | + | == Свойства == |
− | | | + | {{Утверждение |
− | + | |statement=Для неориентированных графов без петель и кратных рёбер матрица инцидентности бинарна (состоит из нулей и единиц). | |
+ | }} | ||
+ | |||
+ | {{Утверждение | ||
+ | |statement=Для ориентированных графов без петель и кратных рёбер матрица инцидентности состоит из нулей, единиц и <tex>-1</tex>. | ||
+ | }} | ||
+ | |||
+ | {{Утверждение | ||
+ | |about=о сумме элементов строки матрицы инцидентности для неориентированного графа | ||
+ | |statement=Сумма элементов <tex>i</tex>-й строки равна <tex>deg \; v_i</tex>. | ||
+ | }} | ||
+ | |||
+ | {{Утверждение | ||
+ | |about=о сумме элементов строки матрицы инцидентности для ориентированного графа | ||
+ | |statement=Сумма элементов <tex>i</tex>-й строки равна <tex>deg^+ v_i - deg^- v_i</tex>. | ||
}} | }} | ||
Строка 25: | Строка 37: | ||
!style="background:#f2f2f2"|Матрица инцидентности | !style="background:#f2f2f2"|Матрица инцидентности | ||
|- | |- | ||
− | |style="background:#f9f9f9"|[[Файл: | + | |style="background:#f9f9f9"|[[Файл:incidence_matrix_undirected_graph.png|200px]] |
|style="background:#f9f9f9"|<tex>\begin{pmatrix} | |style="background:#f9f9f9"|<tex>\begin{pmatrix} | ||
1 & 1 & 1 & 0 & 1 & 0\\ | 1 & 1 & 1 & 0 & 1 & 0\\ | ||
Строка 33: | Строка 45: | ||
0 & 0 & 0 & 1 & 1 & 0\\ | 0 & 0 & 0 & 1 & 1 & 0\\ | ||
\end{pmatrix}</tex> | \end{pmatrix}</tex> | ||
− | |style="background:#f9f9f9"|[[Файл: | + | |style="background:#f9f9f9"|[[Файл:incidence_matrix_directed_graph.png|200px]] |
|style="background:#f9f9f9"|<tex>\begin{pmatrix} | |style="background:#f9f9f9"|<tex>\begin{pmatrix} | ||
-1 & 1 & -1 & 0 & -1 & 0\\ | -1 & 1 & -1 & 0 & -1 & 0\\ | ||
Строка 42: | Строка 54: | ||
\end{pmatrix}</tex> | \end{pmatrix}</tex> | ||
|} | |} | ||
+ | |||
+ | == См. также == | ||
+ | * [[Матрица смежности графа]] | ||
==Источники== | ==Источники== | ||
− | + | * Харари Фрэнк :'''Теория графов'''. Под ред. Л. Б. Штейнпресс. Изд. 2-е. — М.: Мир, 1973. — 180 с. — ISBN 5-354-00301-6 | |
− | Асанов М., Баранский В., Расин В. | + | * Асанов М. О., Баранский В. А., Расин В. В.: '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5 |
+ | * [https://en.wikipedia.org/wiki/Incidence_matrix Википедия {{---}} Incidence matrix] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Основные определения теории графов]] | [[Категория: Основные определения теории графов]] |
Текущая версия на 19:36, 4 сентября 2022
Содержание
Определения для ориентированного и неориентированного графов
Определение: |
Матрицей инцидентности (инциденций) (англ. Incidence matrix) неориентированного графа называется матрица | , для которой , если вершина инцидентна ребру , в противном случае .
Определение: |
Матрицей инцидентности (инциденций) (англ. Incidence matrix) ориентированного графа называется матрица | , для которой , если вершина является началом дуги , , если является концом дуги , в остальных случаях .
Свойства
Утверждение: |
Для неориентированных графов без петель и кратных рёбер матрица инцидентности бинарна (состоит из нулей и единиц). |
Утверждение: |
Для ориентированных графов без петель и кратных рёбер матрица инцидентности состоит из нулей, единиц и . |
Утверждение (о сумме элементов строки матрицы инцидентности для неориентированного графа): |
Сумма элементов -й строки равна . |
Утверждение (о сумме элементов строки матрицы инцидентности для ориентированного графа): |
Сумма элементов -й строки равна . |
Пример
Граф | Матрица инцидентности | Ориентированный граф | Матрица инцидентности |
---|---|---|---|
![]() |
![]() |
См. также
Источники
- Харари Фрэнк :Теория графов. Под ред. Л. Б. Штейнпресс. Изд. 2-е. — М.: Мир, 1973. — 180 с. — ISBN 5-354-00301-6
- Асанов М. О., Баранский В. А., Расин В. В.: Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
- Википедия — Incidence matrix