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

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

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