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

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

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

+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}$

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

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

Дивіться також

• Матриця суміжності

Джерело

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