Пути и циклы Гамильтона. Алгоритм Литтла

В 1857 году математик Уильям Роуэн Гамильтон придумал игру. Существует несколько версий того, как это произошло. По одной из версий он описал игру в письме к другу. Согласно другой, он действительно изобрел игру и продал ее производителю игрушек. В любом случае, данная игра включала додекаэдр, т.е. правильный многогранник, 12 граней которых представляли собой равные правильные пятиугольники. В каждом из 20 углов, или вершин тела, просверливалась дырочка, в которую вставлялся колышек, изображавший город. Используя веревку, требовалось найти путь через города, посетив каждый город один раз, и вернуться в исходный город.

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

Пусть – граф.

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

До настоящего времени никому не удалось установить необходимые и достаточные условия существования у графа гамильтонова цикла. Тем не менее доказан ряд теорем, в которых приводятся некоторые условия существования у графа гамильтонова цикла.

Рассмотрим одну из задач, в которой требуется отыскать во взвешенном графе гамильтонов цикл минимальной длины. Приведем формулировку задачи и алгоритм ее решения.

Задача коммивояжера (или бродячего торговца)

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

После текстовой постановки задачи с помощью математического языка (символов, функций, уравнений или неравенств и т.д.) построим математическую модель задачи. Строгое понятие «математическая модель» введем в следующем разделе «Элементы математического моделирования», на данном шаге будем оперировать данным понятием, как некоторым математическим «переводом» текстового условия.

Итак, пусть – матрица расстояний между городами. Для составления математической модели задачи обозначим через переменные факт переезда коммивояжером из города в город . Поскольку переезд из одного города в другой может осуществляться только один раз, то переменные должны принимать только два значения: 1 или 0, т.е. булевы значения. Таким образом:

Математическая модель задачи имеет следующий вид:

(4.1)

(4.2)

(4.3)

.

Система ограничений (4.2) обеспечивает построение маршрута, при котором коммивояжер въезжает в каждый город только один раз, а система (4.3) – маршрута, при котором он выезжает из каждого города только один раз. Устранение подциклов и получение маршрута, образующего полный цикл, включающий все города, достигается при добавлении системы ограничений:

(4.4)

где все переменные и могут принимать произвольные действительные значения.