Матриця інцидентності — Вікіпедія

Ма́триця інциде́нтності (англ. 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: орієнтований граф[ред. | ред. код]

Якщо є граф:

• ${\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}}}$

Особливості цього подання[ред. | ред. код]

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

Див. також[ред. | ред. код]

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

Примітки[ред. | ред. код]

Джерела[ред. | ред. код]

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

Ця стаття містить перелік посилань, але походження тверджень у ній залишається незрозумілим через практично повну відсутність внутрішньотекстових джерел-виносок. Будь ласка, допоможіть поліпшити цю статтю, перетворивши джерела з переліку посилань на джерела-виноски у самому тексті статті. (серпень 2020)