Page 127 - 6197

Будь-яке 1-дерево, у якого степені всіх вершин
дорівнюють двом є маршрутом комівояжера. Звідси випливає,
L T
що довжина   найкоротшого 1-дерева T визначає нижню
1 1
L T
оцінку   дожини оптимального маршруту комівояжера
1
L T 1 L i 0
  
  .
Розв’язання симетричної задачі комівояжера ґрунтується
на розбитті початкової задачі на окремі підзадачі як це має
місце у методі меж і гілок.
  t
Нехай для розгалуження вибрана задача G . Побудуємо
p
найкоротше 1-дерево для матриці, що відповідає цій вершині,
і знайдемо степені всіх вершин d , i  1,n . Якщо d  для
2
i i
всіх вершин, то отриманий допустимий розв’язок задачі, яки
може стати рекордом.
Допустимо, що існують вершини, для яких d  .
2
i
Знайдемо
d  max :d .
s i
i d  2
  t
Тоді задача G на d підзадач. Нехай із вершини s
p s


виходять ребра s,i , s,i , …,  s,i  . Фрагмент дерева
1 2 s d
розгалуження показаний на рис. 2.7.

Рисунок 2.7 –Фрагмент дерева розгалуження

127