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

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

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

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

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

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

Приклади

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

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

Якщо є граф:

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

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

$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: неорієнтований граф

Неорієнтований граф	Матриця інцидентності
	${\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}}$

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

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

Див. також

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

Джерела

• Матриця інцидентності // Джонатан Гросс, Джей Йеллен. Теорія графів та її застосування. 2 вид. стор. 97. — 2006.
• Райнхард. Теорія графів. стор. 173. — 2005.