Page 27 - 4386

Рисунок 2.3

Розв'язок. α=2.

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

a b c d e f g 1 2 3 4 5 6 7 8 9 10

a 0 1 1 0 0 0 0 a 1 0 1 0 0 0 0 0 0 0
b 1 0 1 0 0 0 0 b 1 1 0 0 0 0 0 0 0 0

c 1 1 0 2 1 0 0 c 0 1 1 1 1 0 1 0 0 0

A= d 0 0 2 1 1 0 0 B= d 0 0 0 1 1 2 0 1 0 0

e 0 0 1 1 0 1 1 e 0 0 0 0 0 0 1 1 1 1
f 0 0 0 0 1 0 0 f 0 0 0 0 0 0 0 0 1 0

g 0 0 0 0 1 0 0 g 0 0 0 0 0 0 0 0 0 1

Як бачимо, у кожному стовпці матриці інцидентності є

тільки два елементи, відмінних від нуля, або один, якщо ребро є

петлею. Матриця суміжності симетрична щодо головної

діагоналі.

Список ребер

Ребро 1 2 3 4 5 6 7 8 9 10

початок a b a c c d c d e e
Вершини
кінець b c c d d d e e f g

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

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

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

26