Добавить вершину в граф, для построения кратчайшего обхода всех вершин

#алгоритм #графы

Есть неориентированный полный граф. Значения длины всех ребер заданы. Необходимо
добавить вершину к графу или использовать уже существующую. Причем эта вершина должна
иметь такое значение ребер, что бы начиная обход графа с нее, можно было обойти все
вершины графа и длина пути обхода - минимальная.

Прошу, помогите ответом. Мне подойдет как полностью раскрытый ответ, так и ссылка
на источник с материалом по вышеописанной теме или даже небольшой намек: "в какую сторону
копать"...
    

Ответы

Ответ 1

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