Page 76 - 4386

Рисунок 6.10

Випадок б).

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

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

можливою.

Необхідно відзначити, що побудований максимальний

орієнтований ліс в обох випадках виявився в графі G також і
0
кістяковим орієнтованим деревом з коренем у вершині f.

75