6.4. Задачи, родственные задаче коммивояжера

До сих пор в разд. 6 мы имели дело с «открытой» задачей коммивояжера, т. е. с кратчайшей гамильтоновой цепью (а не с циклом). Вначале это было оправдано тем, что при этом мы имели дело с более прямой связью «открытой» задачи с кратчайшим остовом. С другой стороны, нужно сделать только очень небольшие изменения, чтобы подойти и к «замкнутой» задаче коммивояжера. Хелд и Карп [18], например, ввели понятие кратчайшего -дерева графа причем оно определяется как кратчайший остов порожденного подграфа графа с удаленной вершиной 1 плюс два кратчайших ребра, исходящих из вершины 1 к двум другим вершинам дерева. Очевидно, что между понятием кратчайшего -дерева и «замкнутой» задачей коммивояжера существует та же самая связь, что и между понятием кратчайшего остова и «открытой» задачей. Таким образом, штрафование вершин изменяет относительные веса -деревьев, но оставляет инвариантным относительное упорядочение гамильтоновых циклов. Так же совершенно очевидно, что, как в «открытой» задаче, кратчайший остов со всеми вершинами степени 2 (за исключением двух концевых вершин) становится кратчайшей гамильтоновой цепью между этими концевыми вершинами, так и в «замкнутой» задаче кратчайшее -дерево, все вершины которого имеют степень 2, является кратчайшим гамильтоновым циклом графа. Алгоритм штрафования вершин, обсуждавшийся ранее в данном разделе, может быть использован поэтому фактически без изменений и для решения «замкнутой» задачи коммивояжера.