1
правка
Изменения
См. также, добавление источников, англоязычные термины, тривиальные свойства
== Инцидентность ребра Определения для ориентированного и вершины неориентированного графов ==
{{Определение
|definition=
'''ИнцидентностьМатрицей инцидентности''' {{---}} отношение между ребром и его концевыми вершинами, т(инциденций) ''(англ. е. если в графе Incidence matrix)'' неориентированного графа называется матрица <tex>G = I (|V,| \times |E|), u \in V, v \in V</tex> {{---}} вершины, а для которой <tex>e \in EI_{i, e j} = (u,v)1</tex> {{---}} соединяющее их ребро, то если вершина <tex>uv_i</tex> и ребро инцидентна ребру <tex>ee_j</tex> инцидентны, вершина в противном случае <tex>v</tex> и ребро <tex>eI_{i,j} = 0</tex> также инцидентны.
}}
{{Определение
|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>.
}}
== Свойства =={{ОпределениеУтверждение|definitionstatement='''Матрицей Для неориентированных графов без петель и кратных рёбер матрица инцидентности''' бинарна (инциденцийсостоит из нулей и единиц) ориентированного графа называется .}} {{Утверждение|statement=Для ориентированных графов без петель и кратных рёбер матрица инцидентности состоит из нулей, единиц и <tex>I (|V| \times |E|)-1</tex>, .}} {{Утверждение|about=о сумме элементов строки матрицы инцидентности для которой неориентированного графа|statement=Сумма элементов <tex>I_{i,j} = 1</tex>, если вершина -й строки равна <tex>deg \; v_i</tex> является началом дуги .}} {{Утверждение|about=о сумме элементов строки матрицы инцидентности для ориентированного графа|statement=Сумма элементов <tex>e_ji</tex>, -й строки равна <tex>I_{i,j} = deg^+ v_i - deg^-1</tex>, если <tex>v_i</tex> является концом дуги <tex>e_j</tex>, в остальных случаях <tex>I_{i,j} = 0</tex>.
}}
!style="background:#f2f2f2"|Матрица инцидентности
|-
|style="background:#f9f9f9"|[[Файл:incidence_matrix_undirected_graph.png|140px200px]]
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 1 & 0\\
\end{pmatrix}</tex>
|style="background:#f9f9f9"|[[Файл:incidence_matrix_directed_graph.png|140px200px]]
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
-1 & 1 & -1 & 0 & -1 & 0\\
\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 Википедия {{---}} Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.Incidence matrix]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
