ЧАСТЬ II
5. Задача коммивояжера
Задача коммивояжера тесно связана с несколькими другими задачами теории графов, обсуждаемыми в других частях этой книги. Здесь мы изучим две такие связи — с задачей о назначениях (см. гл. 12) и с задачей о кратчайшем остове (см. гл. 7). Обе эти задачи могут быть решены намного проще, чем задача коммивояжера, и можно исследовать эти связи для того, чтобы разработать эффективный метод решения последней задачи.
5.1. Нижняя граница из задачи о назначениях
Линейную задачу о назначениях для графа с произвольной матрицей весов 
можно сформулировать так (см. гл. 12).
Пусть 
-матрица, в которой 
если вершина 
«назначена» к вершине 
если 
не назначена к 
Такую же схему можно использовать и в задаче коммивояжера, полагая 
если коммивояжер едет непосредственно из 
в противном случае. В этой последней задаче можно положить 
чтобы устранить бессмысленные решения с 
Теперь задача о назначениях формулируется так.
Найти величины 
минимизирующие
при условии, что
(для всех 
)
Условие (10—5) просто гарантирует, что решение будет циклическим, т. е. в каждую вершину входит и из нее выходит одна дуга.
Уравнения (10.4) — (10.6) вместе с дополнительным ограничением, состоящим в том, что решение должно давать единственный цикл (гамильтонов), а не просто некоторое число несвязных циклов также могут быть использованы для формулировки задачи коммивояжера. Заметим, что дополнительное условие 
назначениях циклов длины 1. Так как добавление любого ограничения в задаче о назначениях не может увеличить минимального значения 
определяемого из уравнений (10.4) — (10.6), то это значение 
является нижней траницей веса решения задачи коммивояжера для графа с матрицей весов 
