1
правка
Изменения
См. также, добавление источников, англоязычные термины, тривиальные свойства
== Инцидентность ребра Определения для ориентированного и вершины неориентированного графов ==
{{Определение
|definition=
'''ИнцидентностьМатрицей инцидентности''' - отношение между ребром и его концевыми вершинами, т(инциденций) ''(англ. е. если в графе Incidence matrix)'' неориентированного графа называется матрица <tex>G = I (|V,| \times |E|) </tex> , для которой <tex>u \in VI_{i, v \in Vj} = 1</tex> - вершины, а если вершина <tex>e \in Ev_i</tex> инцидентна ребру <tex>e_j</tex> - соединяющее их ребро (e = (u,v))в противном случае <tex>I_{i, то вершина u и ребро e инцидентны, вершина v и ребро e также инцидентны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>.
}}
== Пример ==
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"
!style="background:#f2f2f2"|Граф
!style="background:#f2f2f2"|Матрица инцидентности
!style="background:#f2f2f2"|Ориентированный граф
!style="background:#f2f2f2"|Матрица инцидентности
|-
|style="background:#f9f9f9"|[[Файл:incidence_matrix_undirected_graph.png|200px]]
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 0\\
1 & 0 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 1 & 0\\
\end{pmatrix}</tex>
|style="background:#f9f9f9"|[[Файл:incidence_matrix_directed_graph.png|200px]]
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
-1 & 1 & -1 & 0 & -1 & 0\\
1 & 0 & 0 & -1 & 0 & 0\\
0 & -1 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 0 & 0 & -1\\
0 & 0 & 0 & 1 & 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 Википедия {{---}} Incidence matrix]
