Page 68 - 4386

6.4 Алгоритми побудови максимального та мінімального

орієнтованого лісу

Поставимо у відповідність кожній дузі (v, w) орієнтованого

графа G вагу с(v, w). Вага орієнтованого лісу (або орієнтованого

дерева) визначається як сума ваг дуг, що входять у цей ліс (або

дерево).

Максимальним орієнтованим лісом графа G називається

орієнтований ліс графа G з максимально можливою вагою.

Максимальним орієнтованим деревом графа G називається

орієнтоване дерево графа G з максимально можливою вагою.

Мінімальний орієнтований ліс і мінімальне орієнтоване

дерево визначаються аналогічним чином.

Розглянемо алгоритм побудови максимального

орієнтованого лісу (алгоритм Едмондса). Даний алгоритм будує

відповідний ліс для будь-якого орієнтованого графа G.

Мінімальний орієнтований ліс одержується після зміни

знака величини ваги кожної дуги. Максимальний орієнтований

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

для вхідних ваг дуг.

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

множина вершин і множина дуг. Перша містить тільки ті

вершини, які були переглянуті в процесі виконання алгоритму, а

друга – дуги, умовно включені в максимальний орієнтований ліс

під час процедури перегляду вершин (деякі з умовно включених у

шуканий ліс дуг на останньому етапі алгоритму можуть бути

виключені). Під час усієї процедури алгоритму, дуги другої

множини (точніше її поточного варіанту) утворюють ліс для

відповідного графа. Перед початком алгоритму обидві множини

порожні.

67