Page 74 - 4386

На даному етапі виконання алгоритму (крок 2),

здійснюється стягування контуру C 0 в одну вершину v .
0
Одержаний у результаті такого стягування граф G зображений
1
на рис. 6.9.

Рисунок 6.9

Перерахунок нової ваги дуг є таким (формула 6.1):

с(e, v )=с(e, a)+с(с, b)-с(d, a)=2+2-3=1,
0
с(f, v )=с(f, a)+с(с, b)-с(d, a)=0+2-3=-1,
0
с(f, v )=с(f, d)+с(с, b)-с(b, d)=1+2-2=1.
0
Слід зауважити, що у виявленому контурі C , найменшу
0
вагу мають дві дуги ((с, b) та (b, d)), тому до перерахунку нових

ваг у стягнутому графі залучаємо довільну з них.

Сформуємо дві множини V та E . Оскільки граф G не
1
1
1
містить жодної з вершин та дуг які були в множинах V та E , то
0
0
множини V та E є порожніми. Збільшуємо i на одиницю, та
1
1
переходимо до кроку 1.
У результаті виконання кроку 1 алгоритму, переглянуто такі

вершин e, f та v (табл. 6.4).
0
Після завершення перегляду всіх трьох вершин графа G
1
алгоритм формує в графі G максимальний орієнтований ліс, що
1
складається з дуг ((f, e), (e, v ) або (f, e), (f, v ).
0
0
Оскільки усі вершини графа G входять у множину V , то
1
1
переходимо до кроку 3.

73