Это должно быть решено алгоритмом аппроксимации двойного дерева для решения задачи TSP (задача коммивояжера) / цепи Гамильтона.Для этого необходимо выполнить два условия входного графа:
- неравенство треугольника (у вас есть это)
- полный граф (У вас есть это? Это значит, что должен быть грань междукаждые две вершины графа.)
Алгоритм работает следующим образом:
- найти минимальное остовное дерево входного графа (для этого есть несколько алгоритмов; еслипредставление вашего графа является списком сопряженности, сложность O (e + v * log (v)))
- Удвойте каждое ребро в связующем дереве - у вас будет мультиграф (O (e))
- создайте путь Эйлера в этом графе - если вы встретите вершину во второй раз, пропустите ее и возьмите прямое ребро к следующей вершине (это ребро существует в графе, поскольку у вас есть полный граф) - это также должно быть что-то вродеO (e + некоторый логарифм)
- Вы закончили - вы нашли цепь Гамильтона (и решили TSP)
Этот алгоритм 2-приблизительный (стоимость схемы составляетпри максимальном удвоении оптимальное решение - естьэто доказательство, которое я могу предоставить, если хотите).Худшая сложность - O (e + v log (v)) - e - это число ребер, v количество вершин ... это должно соответствовать вашему O (m + n log (n)).
На данный момент я не смог найти хорошую связь с объяснением алгоритма, постараюсь предоставить его позже.