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

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

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

1: якщо ребро виходить з вершини ;

-1: якщо ребро входить у вершину ;

0: якщо вершина не має стосунку до ребра .

ПрикладиРедагувати

Приклад № 1: орієнтований графРедагувати

 
Орієнтований граф (до прикладу № 1)

Якщо є граф:

  •  
  •  
  •  
  •  
  •  

то матриця інцидентності виглядатиме так:

 

Приклад № 2: неорієнтований графРедагувати

Неорієнтований граф Матриця інцидентності
   

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

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

Див. такожРедагувати

ПриміткиРедагувати

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

ДжерелаРедагувати

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