Ма́триця інциде́нтності () — одна з форм подання графу, в якій вказуються зв'язки між інцидентними елементами графу (ребро (дуга) і вершина). Стовпці матриці відповідають ребрам, рядки — вершинам. Ненульове значення в клітинці матриці вказує на зв'язок між вершиною і ребром (їх інцидентність)Слюсар В. І., Перепеліцин С. О. Аналіз топології багаторангових мереж на основі торцевого добутку матриць. // IX Міжнародна науково-технічна конференція «Радіотехнічні поля, сигнали, апарати та системи». — 16 — 22 листопада 2020. — Київ: НТУУ КПІ. — С. 114—116. — ..
Кожна комірка матриці може набувати трьох значень:
-1: якщо ребро виходить з вершини ;
1: якщо ребро входить у вершину ;
0: якщо вершина не має стосунку до ребра .
Приклади
Приклад № 1: орієнтований граф
Якщо є граф:
то матриця інцидентності виглядатиме так:
Приклад № 2: неорієнтований граф
{|class="wikitable" style="text-align: center" !Неорієнтований граф !Матриця інцидентності
Особливості цього подання
Не використовується для графів з петлями, оскільки в петлі одна вершина є і початком, і кінцем. У кожному стовпці повинні стояти дві одиниці, а всі інші символи — нулі.
Див. також
Матриця суміжності Матриця Кірхгофа (Матриця Лапласа)
Примітки
Джерела
Матриця інцидентності // Джонатан Гросс, Джей Йеллен. Теорія графів та її застосування. 2 вид. стор. 97. — 2006. Райнхард. Теорія графів. стор. 173. — 2005.