Page 75 - 4386

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

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

e e (f, e)

f e, f (f, e)

v e, f, v (f, e), (e, v )
0
0
0
або (f, e), (f, v )
0

Під час виконання кроку 3 розглянемо два випадки:

а) множини E є такою: E ={(f, e), (e, v )};
0
1
1
б) множини E є такою: E ={(f, e), (f, v )}.
0
1
1
Випадок а).
Оскільки вершина v не є коренем орієнтованого дерева в
0
лісі G , утвореного дугами з множини E , то єдина дуга (e, v ), що
0
1
1
заходить у вершину v в графі G , відповідає дузі (e, a) в графі G .
0
1
0
Сформуємо множину дуг, що складається з дуг множини E
1
та дуг контуру C : {(f, e), (e, a), (d, а), (а, c), (c, b), (b, d)}. Ця
0
множина дуг містить у точності один контур, а саме контур C , та
0
рівно дві дуги, що заходять у вершину а, а саме дугу (e, a) та дугу

в контурі C – (d, а). Вилучимо із сформованої множини дуг дугу
0
контуру C (d, а), що заходить у вершину а. З отриманої в такий
0
спосіб множини дуг складемо нову множину E ={(f, e), (e, a), (а,
0
c), (c, b), (b, d)}. Одержана сукупність дуг нової множини E
0
визначає максимальний орієнтований ліс у графі G (рис. 6.10 а).
0
Дійсно, вага такого лісу рівна 1+2+3+2+2=10 і є максимально

можливою.

74