Page 132 - 6197

 Після вилучення ребра (2,4) і з’єднання вершин 3 і 4
(рис. 2.8) отримуємо 1-дерево T , яке показано на рис. 2.12.
1
Його довжина   10L T  ; max :d  d  3 і задача 2 4, 
1 i 2
i
розпадається на три задачі   2, , 2 3,  і 2 5,  (рис. 2.20).
1
 Вилучаємо ребро (2,5) (рис. 2.8). З’єднуємо вершини 4 і
5 та знаходимо довжину 1-дерева T (рис. 2.13)   10L T  .
1 1
Оскільки max :d  d  3, то задача 2 5,  породжує три задачі
i i 2
1
  2, , 2 3,  і 2 4,  (рис. 2.20).

Рисунок 2.11 – 1-дерево T після вилучення ребра (2,3)
1
Аналіз отриманих результатів показує, що після виконання
другого кроку алгоритму значення оцінки нижньої межі
маршруту комівояжера змінилося і тепер воно дорівнюватиме
9, тобто
*
9  L   13i  .

132