Page 70 - 4386

етапу алгоритму, що полягає в наступному. Граф, одержаний по

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

фіктивної вершини контуром, який у неї стягувався при

відповідному перетворенні графів. У новий розширений граф, а

також у відповідну йому множину, включаються всі дуги

зазначеного контуру, за винятком однієї. Виключена дуга

вибирається так, щоб дуги, що входять в нову множину,

утворювали ліс у відповідному графі. Цей процес послідовного

розширення графа триває доти, поки не буде відновлений вхідний

граф. При цьому, дуги відповідної множини утворюють для

вхідного графа максимальний орієнтований ліс.

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

орієнтованого кістякового дерева.

Позначимо вхідний граф, для якого будується максимальний

орієнтований ліс, через G , а через G , G , і т. д, графи, які
2
1
0
послідовно одержуються із графа G у ході процедури стягування
0
контурів, що виявляються. Множину вершин і множину дуг для

відповідних графів позначимо через V , V , V , ... та E , E , E , ...
2
0
l
1
0
2
На початок дії алгоритму всі множини V , V , V , ... та E , E , E , ...
0
2
1
2
l
0
порожні; і=0.
Крок 1. Якщо всі вершини графа G входять у множину V ,
і
і
перейти до кроку 3. Якщо ні, то вибрати в графі G будь-яку
і
вершину v, що не входить у множину V та включити її в V . Далі,
і
і
серед дуг, що заходять у вершину v, вибрати дугу e з
максимальною позитивною вагою. Якщо вершина v не має
відповідної дуги, повернутися до початку даного кроку. Якщо
існує така дуга, то включити знайдену дугу в множину E . Якщо
і
після включення в E дуги e, множина дуг E продовжує
і
і

69