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

Рейтинг: 4Ответов: 1Опубликовано: 13.04.2011

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

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

алгоритм графы
Источник: Stack Overflow на русском

Ответы

▲ 4Принят

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