Page 72 - 4386

Якщо і=0, закінчити процедуру алгоритму – дуги множини

E утворюють максимальний орієнтований ліс для вхідного графа
0
G . Якщо і≠0, дослідити два можливі випадки:
0
а) вершина v є коренем деякого орієнтованого дерева в
і-1
орієнтованому лісі, утвореного дугами з E ;
і
б) вершина v не є коренем деякого орієнтованого дерева в
і-1
лісі, утвореного дугами з E
і.
Для випадку (а) розглянути дуги з множини E у сукупності
і
з дугами контуру C . Ці дуги містять у точності один контур, а
і-1
саме контур C . Вилучити з розглянутої множини дуг таку дугу
і-1
контуру C , яка має найменшу вагу. З отриманої в такий спосіб
і-1
множини дуг скласти нову множину E . Очевидно, дуги нової
і-1
множини E утворюють у графі G орієнтований ліс.
і-1
і-1
Для випадку (б) в E є єдина дуга (х, v ), що заходить у
і-1
і
вершину v . Ця дуга відповідає деякій дузі (х, у) у графі G , де у
і-1
і-1
– деяка вершина контуру C , стягнутого у вершину v .
і-1
і-1
Сформувати множину дуг, що складається з дуг множини E
і
та дуг контуру C Ця множина дуг містить у точності один
і-1.
контур, а саме контур C , та рівно дві дуги, що заходять у
і-1
вершину у, а саме дугу (х, у) і відповідну дугу в контурі C
і-1.
Вилучити із сформованої множини дуг дугу контуру C , що
і-1
заходить у вершину у. З отриманої в такий спосіб множини дуг

скласти нову множину E . Очевидно, дуги нової множини
і-1
утворюють у графі G орієнтований ліс.
і-1
Зменшити і на одиницю та повторити крок 3.

Приклад 6.4. Побудувати максимальний орієнтований ліс

для графа, наведеного на рис. 6.8.

71