Page 75 - 2589

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

ребру, в ньому записано номери вершин, інцидентних йому. Для
неорієнтованого графа порядок цих вершин у рядку довільний,

для орієнтованого першим записується номер або інше
найменування початку ребра, а другим – його кінця.
За списком ребер графа можна легко визначити матрицю
інцидентності. Справді, кожний рядок цього списку відповідає

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

цьому рядку першим зазначається номер елемента рядка матриці,
який дорівнює -1, другим – номер елемента, що дорівнює 1.
Поняття матриці інцидентності та списку ребер можна легко
узагальнити на випадок мультиграфа.

Приклад 4.1: Матриці інцидентності для графів зображених
на рис.4.3,а і рис.4.3,б відповідно наведені у табл. 4.1,а і

табл.4.1,в. Списки ребер для графів, зображених на рис. 4.3,а та
рис. 4.3,б відповідно наведені у табл. 4.1,б і табл.4.1,г.

Таблиця 4.1 – Матричний опис графів

75