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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

-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 неорієнтований граф[ред.ред. код]

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