6. Задача коммивояжера и задача о кратчайшем остове

Как уже отмечалось в предыдущем разделе, симметричная задача коммивояжера тесно связана с задачей о кратчайшем остове графа и открытая задача коммивояжера (т. е. задача нахождения кратчайшей гамильтоновой цепи в графе) практически эквивалентна задаче нахождения кратчайшего остова графа с тем ограничением, что никакая вершина не должна иметь степень, большую чем 2. Ввиду того, что открытая задача коммивояжера несколько более сильно связана с задачей о кратчайшем остове, чем замкнутая, мы начнем с рассмотрения сначала этой задачи, отложив на конец раздела обсуждение тех небольших изменений, которые необходимо сделать в замкнутой (обычной) задаче коммивояжера.

Задача нахождения кратчайшей гамильтоновой цепи была впервые исследована Део и Хакими [13], давшими ее формулировку на языке линейного программирования. Для полного графа с вершинами их формулировка содержит переменных и ограничений, которые формулируются явно. Наряду с этим имеется очень большое число ограничений, которые нельзя сформулировать явно, но которые рассматриваются неявно, причем за один раз (после каждого итерационного применения симплекс-метода) вводятся немногие из них. Хотя метод линейного программирования и дает всегда решение, он не будет здесь больше обсуждаться, так как обладает врожденной громоздкостью и неэффективностью.

6.1. Определения

Пусть реберно-взвешенный неориентированный граф, степень вершины в графе Число вершин в будет обозначаться через

Если задан остов графа и степень вершины в дереве обозначена через можно определить близость этого остова к гамильтоновой цепи одним из следующих двух способов:

или

Выражение (10.8)(а) учитывает близость только по тем вершинам, для которых в то время как принимает во внимание и вершины степени 1. Оба эти выражения для гамильтоновой цепи дают и можно считать, что чем больше тем сильнее дерево отличается от гамильтоновой цепи.

Теперь мы рассмотрим две следующие задачи.

Задача (а). Кратчайшая гамильтонова цепь. Найти кратчайший остов графа такой, что степени всех вершин не превышают 2.

Задача (б). Кратчайшая гамильтонова цепь с отмеченными концевыми вершинами. Заданы две вершины найти кратчайший остов такой, что степени всех вершин не превышают 2, а степени вершин равны 1.

Теперь нужно проверить подразумеваемое в сформулированных задачах утверждение о том, что дерево все вершины которого имеют степень, не больше чем 2, является на самом деле гамильтоновой цепью. Действительно, так как дерево, то степень никакой его вершины не может быть равной нулю и, следовательно, или 2 для всех Пусть вершин имеют степень имеют степень 2. Число ребер в дереве равно

так как при суммировании каждое ребро считается дважды, по одному разу для каждой из его конечных вершин.

Из уравнения (10.9) получим

Так как число ребер в дереве равно то и поэтому ровно две вершины имеют степень вершин — степень 2, т. е. является гамильтоновой цепью.