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

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

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

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

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

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

Див. також

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

Примітки

1. Слюсар В. І., Перепеліцин С. О. Аналіз топології багаторангових мереж на основі торцевого добутку матриць. // ІХ Міжнародна науково-технічна конференція «Радіотехнічні поля, сигнали, апарати та системи». — 16 — 22 листопада 2020. — Київ: НТУУ КПІ. — С. 114—116. — [1] [ 25 січня 2021 у Wayback Machine.].

Джерела

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