Page 69 - 4386

В основному алгоритмі послідовно в довільному порядку

проглядаються вершини графа. Перегляд вершини полягає в

тому, що з дуг, що заходять у дану вершину, вибирається дуга з

максимальною вагою (вершина, що не має дуг, що заходять,

може бути взагалі виключена з розгляду). Якщо додавання цієї

дуги до дуг, що вже увійшли в множину, не порушує властивості

множини утворювати ліс, то обрана дуга вводиться в множину

дуг. А якщо ні (коли обрана дуга утворює контур з деякими

дугами, що раніше ввійшли в множину), то формується новий

зменшений граф шляхом стягування дуг і вершин виявленого

контуру в одну вершину (рис. 6.7). У новому графі ваги деяких

дуг відповідним чином коригуються. Крім того, для нового графа

коригується склад множини вершин і множини дуг – у них

залишаються тільки ті елементи (вершини або дуги), які присутні

в новому графі. Після проведеного коригування, процедура

перегляду вершин триває аналогічним чином і закінчується тоді,

коли переглянуті всі вершини вхідного графа.

G G´

Рисунок 6.7 – Вхідний граф G та граф G´, одержаний з вхідного

шляхом стягування контуру (a, b), (b, с), (с, a)

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

відповідному графі. Після цього, здійснюється перехід до другого

68