Page 135 - 6197

Рисунок 2.15 – 1-дерево T після вилучення ребер (1,2) і
1
(2,4)
Четвертий крок алгоритму.
Переходимо до розгалуження задачі 2 3,  . У результаті

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

1
рекорду. Тому задача   2, у подальшому не розгалужується.

Рисунок 2.16 – 1-дерево T після вилучення ребер (1,2) і
1
(2,5)
 Переходимо до задачі 2 4,  , де вилучаємо ребра (2,3) і
(2,4) (рис.2.8). Вершини 3 і 6 з’єднуємо з вершиною 4, що дає

135