Page 73 - 4386

Рисунок 6.8

Розв'язок.

Позначимо вхідний граф через G . Сформуємо дві множини
0
V та E , які на початок дії алгоритму є порожніми. i=0.
0
0
У процесі виконання алгоритму будемо вибирати вершини в

такому порядку: а, b, c, d, e та f.

У результаті виконання кроку 1 алгоритму, переглянуто

перші чотири вершин а, b, с та d (табл. 6.4).

Таблиця 6.4 – Результати виконання кроку 1 алгоритму

для графа G
0
Переглянуті V E
0
0
вершини

а а (d, а)

b а, b (d, а), (c, b)

c а, b, c (d, а), (c, b), (а, c)

d а, b, c, d (d, а), (c, b), (а, c), (b, d)

Оскільки, після перегляду вершини d, дуги множини E уже
0
не утворюють орієнтований ліс (вони утворюють контур C –
0
(d, а), (а, c), (c, b), (b, d)), то здійснюється перехід до кроку 2.

72