Теория графов

Question

[avonar]

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

Comments

[avonar]

да, по постановке задачи, самая близкая это задача коммивояжера.
самым рациональным(с точки зрения реалий) на мой взгляд алгоритмом оказался «алгоритм составления минимального остовного дерева», возможно, чуть чуть измененный.

Answer 1

[osby]

Кажется, это Задача коммивояжёра

Comments

[Eternalko]

Так точно.

Answer 2

[Cthutq66a]

Если нужен гамильтонов цикл(цепь) то тут только перебор с возвратом. А вот «минимальное количество раз проходить по одним и тем же вершинам», тут, наверное, надо сначала пытаться найти гамильтонов цикл(цепь), а потом увеличивать макс. возможное число вхождений вершин.