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

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

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

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

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

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

Див. також

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

Примітки

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

Джерела

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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