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

Граф і матриця інцидентності

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

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

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

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

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

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

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

Якщо у нас є граф:

  •  
  •  
  •  
  •  
  •  

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

 

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

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

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

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

Дивіться такожРедагувати

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

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