Інцидентність

Інцидентність уявляє відношення між різнорідними елементами графа – вершинами і ребрами: якщо вершина є кінцем ребра e_k, то вона інцидентна ребру e_k, а ребро e_k інцидентне вершині .

В орграфах розрізняють позитивну інцидентність (дуга виходить з вершини) та негативну інциденність (дуга заходить у вершину).

Відношення інцидентності дозволяє представить - граф у вигляді матриці інцидентності розміру , в якій рядки відповідають вершинам, а стовпці – ребрам (дугам) графа.

Кожен елемент матриці визначається наступним чином:

а) для неорієнтованого графа дорівнює:

1) 1, якщо вершина інцидентна ребру ;

2) 0, якщо та не інцидентні;

б) для орграфа дорівнює:

1) 1, якщо - початкова вершина, тобто позитивна інцидентність;

2) -1, якщо - кінцева вершина, тобто негативна інцидентність;

3) 0 – як у пункті а).

Матриці інцидентності псевдографа А1 (рис. 8.4, а) та орграфа А2 (рис. 8.3) наведені відповідно на рис. 8.6.

Рис. 8.6 Матриці інцидентності графів

Властивості матриць інцидентності. Кожен стовпець матриці інцидентності містить обов’язково два одиничних елемента, а для орграфа ці елементи мають різні знаки і відповідно дорівнюють 1 та -1.

Для неорієнтованого графа кількість одиниць в рядку дорівнює ступеню вершини.

Для орграфа сума позитивних елементів дорівнює позитивному ступеню вершин, сума негативних – негативному ступеню.

Нульовий рядок відповідає ізольованій вершині.

Нульовий стовпець відповідає петлі, при цьому матриця не надає інформації про те, з якою вершиною пов’язана петля.