Page 137 - 6197

*
Після четвертого кроку алгоритму 10  L   11i  (рис.
2.20).

П’ятий крок алгоритму.
Переходимо до задач, які породжені розгалуженням задачі

2 4,  (рис. 2.20)
 Задача   2, розв’язана на третьому кроці алгоритму з
1
оцінкою   11L i  .

 Задача 2 3,  розв’язана на четвертому кроці алгоритму
з оцінкою   11L i  .

 Розв’язуємо задачу 2 5, . Як випливає із рис. 2.20
вилученню із 1-дерева T (рис. 2.8) підлягають ребра (2,4) і
1
(2,5). Після такого вилучення отримуємо 1-дерево довжиною
 
L   12i  (рис. 2.18). Маємо L i  R і задача 2 5, 
e
відсіюється.
Виконання п’ятого крку алгоритму дало такий результат:
*
10  L   11i  .

Рисунок 2.19 – 1-дерево T після вилучення ребер (2,4) і
1
(2,5)

137