Гамильтоновы циклы

Граф называется гамилътоновым, если в нем имеется простой цикл, проходящий через каждую вершину этого графа (по одному разу). Сам этот цикл также называется гамилътоновым.

Слово “ гамильтонов ” в этих определениях связано с именем известного ирландского мате­матика Уильяма Гамильтона, которым в 1859 году предложена игра “Кругосветное путешествие”. Каждой из двадцати вершин додекаэдра приписано название одного из крупных городов мира. Требуется, переходя от одного города к другому по ребрам додекаэдра, посетить каждый город в точности один раз и вернуться в исходный город. Эта задача, очевидно, сводится к отысканию в графе до­декаэдра простого цикла, проходящего через каждую вершину этого графа.

Рисунок 4.23 - Додекаэдр игры “Кругосветное путешествие”

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

Примером нахождения гамильтонового цикла является задача о коммивояжёре. Коммивояжёр (фр. commisvoyageur) – разъездной представитель торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам.

В этой задаче считается, что имеется n городов, которые непременно должен посетить коммивояжёр, - все и ровно по одному разу, проделав путь между городами наименьшей суммарной протяженности.

В терминах теории графов эта задача формулируется таким образом: в заданном связном взвешенном графе найти гамильтонов цикл наименьшей длины.

Эта задача имеет большое практическое и теоретическое значение. В силу своей вычислительной сложности - при полном переборе существует (n - 1) • (n - 2) • … • 2 • 1 = (n - 1) ­ решений (т.е. сгенерировать все возможные перестановки вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать из них кратчайший), равносильной целому классу переборных задач, она часто используется математиками для сравнительного анализа и изучения сложности алгоритмов оптимизации в дискретной математике.

Таким образом, решение задачи о коммивояжёре методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших n.

Более того, известно, что задача о коммивояжёре принадлежит к числу так называемых NP – полных задач, суть которых вкратце такова. В различных областях дискретной математики, комбинаторики, логики и т.п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющих полиномиальную трудоемкость. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффективных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение, что таких алгоритмов не существует.

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

1. Эвристический.

2. Монте-Карло (статистические выборки).

3. Целочисленного линейного программирования.

4. Динамического программирования.

Дата добавления: 2014-01-06