Что такое гамильтонов граф и как он связан с задачей о коммивояжере?

Гамильтонов граф — граф, содержащий гамильтонов цикл, то есть замкнутый путь, который проходит через каждую вершину графа ровно по одному разу. ru.wikipedia.org neerc.ifmo.ru

Задача о коммивояжёре заключается в том, что коммивояжёр должен посетить несколько городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. neerc.ifmo.ru В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей? neerc.ifmo.ru

Гамильтонов граф связан с задачей о коммивояжёре тем, что эту задачу можно переформировать в терминах теории графов — построить граф, вершины которого соответствуют городам, а рёбра — коммуникации между городами. ru.wikipedia.org Решение этой задачи ищут среди гамильтоновых циклов построенного графа. ru.wikipedia.org

Пользователь

Время добавления