http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=Migan42Викиконспекты - Вклад участника [ru]2026-06-11T04:23:35ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%B8%D0%BD%D1%86%D0%B8%D0%B4%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%B0&diff=59200Матрица инцидентности графа2017-01-07T21:14:22Z<p>Migan42: См. также, добавление источников, англоязычные термины, тривиальные свойства</p>
<hr />
<div>== Определения для ориентированного и неориентированного графов ==<br />
<br />
{{Определение<br />
|definition=<br />
'''Матрицей инцидентности''' (инциденций) ''(англ. 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>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Матрицей инцидентности''' (инциденций) ''(англ. 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>.<br />
}}<br />
<br />
== Свойства ==<br />
{{Утверждение<br />
|statement=Для неориентированных графов без петель и кратных рёбер матрица инцидентности бинарна (состоит из нулей и единиц).<br />
}}<br />
<br />
{{Утверждение<br />
|statement=Для ориентированных графов без петель и кратных рёбер матрица инцидентности состоит из нулей, единиц и <tex>-1</tex>.<br />
}}<br />
<br />
{{Утверждение<br />
|about=о сумме элементов строки матрицы инцидентности для неориентированного графа<br />
|statement=Сумма элементов <tex>i</tex>-й строки равна <tex>deg \; v_i</tex>.<br />
}}<br />
<br />
{{Утверждение<br />
|about=о сумме элементов строки матрицы инцидентности для ориентированного графа<br />
|statement=Сумма элементов <tex>i</tex>-й строки равна <tex>deg^+ v_i - deg^- v_i</tex>.<br />
}}<br />
<br />
== Пример ==<br />
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"<br />
!style="background:#f2f2f2"|Граф<br />
!style="background:#f2f2f2"|Матрица инцидентности<br />
!style="background:#f2f2f2"|Ориентированный граф<br />
!style="background:#f2f2f2"|Матрица инцидентности<br />
|-<br />
|style="background:#f9f9f9"|[[Файл:incidence_matrix_undirected_graph.png|200px]]<br />
|style="background:#f9f9f9"|<tex>\begin{pmatrix}<br />
1 & 1 & 1 & 0 & 1 & 0\\<br />
1 & 0 & 0 & 1 & 0 & 0\\<br />
0 & 1 & 0 & 0 & 0 & 1\\<br />
0 & 0 & 1 & 0 & 0 & 1\\<br />
0 & 0 & 0 & 1 & 1 & 0\\<br />
\end{pmatrix}</tex><br />
|style="background:#f9f9f9"|[[Файл:incidence_matrix_directed_graph.png|200px]]<br />
|style="background:#f9f9f9"|<tex>\begin{pmatrix}<br />
-1 & 1 & -1 & 0 & -1 & 0\\<br />
1 & 0 & 0 & -1 & 0 & 0\\<br />
0 & -1 & 0 & 0 & 0 & 1\\<br />
0 & 0 & 1 & 0 & 0 & -1\\<br />
0 & 0 & 0 & 1 & 1 & 0\\<br />
\end{pmatrix}</tex><br />
|}<br />
<br />
== См. также ==<br />
* [[Матрица смежности графа]]<br />
<br />
==Источники==<br />
* Харари Фрэнк :'''Теория графов'''. Под ред. Л. Б. Штейнпресс. Изд. 2-е. — М.: Мир, 1973. — 180 с. — ISBN 5-354-00301-6<br />
* Асанов М. О., Баранский В. А., Расин В. В.: '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5<br />
* [https://en.wikipedia.org/wiki/Incidence_matrix Википедия {{---}} Incidence matrix]<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Основные определения теории графов]]</div>Migan42