Page 26 - 4386

− α, якщо ребро e є петлею, а v інцидентна їй вершина
i
j
(α≠0, α≠1);

2) у випадку орієнтованого графа:

− 1, якщо вершина v є початком дуги e ;
j
i
− -1, якщо вершина v є кінцем дуги e ;
j
i
− 0, якщо дуга e не інцидентна вершині v ;
j
i
− α, якщо дуга e є петлею, а v інцидентна їй вершина (α≠0,
j
i
α≠-1,α≠1).

Список ребер графа – це таблиця, що складається із трьох

рядків. У першому перераховані всі ребра, у другому і третьому –

інцидентні їм вершини:

− у випадку неорієнтованого графа порядок вершин у

другому та третьому рядках довільний;

− у випадку орієнтованого графа першою записується

вершина, у якій починається дуга (другий рядок); вершина, у якій

закінчується дуга, записується у третій рядок.

Якщо графи рівні, то їхні матриці суміжності та

інцидентності, а також списки ребер однакові.

Відмінність матриці інцидентності орієнтованого графа від

неорієнтованого полягає у вказівці початку і кінця ребер.

Матриця суміжності губить свою симетричність. У списку ребер

важливий порядок вказівки вершин, що з'єднуються зазначеним

ребром (від початку до кінця).

Приклад 2.1. Задати матрицями інцидентності та

суміжності, а також списком ребер неорієнтований граф,

зображений на рис. 2.3.

25