Матриця інцидентності

Ма́триця інциде́нтності (англ. Incidence matrix) — одна з форм подання графу, в якій вказуються зв'язки між інцидентними елементами графу (ребро (дуга) і вершина). Стовпці матриці відповідають ребрам, рядки — вершинам. Ненульове значення в клітинці матриці вказує на зв'язок між вершиною і ребром (їх інцидентність)^[1].

Кожна комірка матриці може набувати трьох значень:

-1: якщо ребро ${\displaystyle k_{j}}$ виходить з вершини ${\displaystyle v_{i}}$;

1: якщо ребро ${\displaystyle k_{j}}$ входить у вершину ${\displaystyle v_{i}}$;

0: якщо вершина ${\displaystyle v_{i}}$ не має стосунку до ребра ${\displaystyle k_{j}}$.

Приклади

Приклад № 1: орієнтований граф

Орієнтований граф (до прикладу № 1)

Якщо є граф:

• ${\displaystyle k_{1}\ =\ (1,2)}$
• ${\displaystyle k_{2}\ =\ (1,3)}$
• ${\displaystyle k_{3}\ =\ (3,2)}$
• ${\displaystyle k_{4}\ =\ (3,4)}$
• ${\displaystyle k_{5}\ =\ (4,3)}$

то матриця інцидентності виглядатиме так:

${\displaystyle M=\left[{\begin{matrix}-1&-1&0&0&0\\1&0&1&0&0\\0&1&-1&-1&1\\0&0&0&1&-1\end{matrix}}\right]}$

Приклад № 2: неорієнтований граф

Неорієнтований граф	Матриця інцидентності
	${\displaystyle {\begin{pmatrix}1&0&0&0&1&0&0\\1&1&0&0&0&1&0\\0&1&1&0&0&0&0\\0&0&1&1&0&0&1\\0&0&0&1&1&1&0\\0&0&0&0&0&0&1\\\end{pmatrix}}}$

Особливості цього подання

• Не використовується для графів з петлями, оскільки в петлі одна вершина є і початком, і кінцем.
• У кожному стовпці повинні стояти дві одиниці, а всі інші символи — нулі.

Див. також

• Матриця суміжності
• Матриця Кірхгофа (Матриця Лапласа)