Гамильтоновы маршруты

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

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

Гамильтоновым путемв ориентированном графе называется путь S = (х₁, ..., х_n), проходящий через все вершины графа, притом только по одному разу.

Гамильтоновым контуромназывается контур М=(х₀, х₁, ..., х_n, х₀) в ориентированном графе G(X), если он прохо­дит через все вер­шины графа по одному разу.

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

В применении графов к играм вершины соответствуют различ­ным позициям. Существование гамильтонова цикла равносильно существованию циклической после­довательности ходов, содержа­щей каждую позицию по одному разу. Примером является задача о шахматном коне: можно ли, начиная с произвольного поля на доске, ходить конем в такой последовательности, чтобы пройти каждое из шестидесяти четырех полей и вернуться в исходное?

К гамильтоновым циклам относится также известная задача о бродячем торговце (задача о коммивояжере). Район, который дол­жен посетить коммивояжер, содержит определенное количество городов. Расстояния между ними известны, и нужно найти кратчай­шую дорогу, проходящую через все пункты и возвращающуюся в исходный. Эта задача имеет ряд приложений в экономике и иссле­довании операций.

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

Теорема Кёнига. В полном конечном графе всегда существу­ет гамильтонов путь.

Если в графе G(X) с n вершинами для любой пары вершин x_i и x_j справедливо неравенство

m(х_i) + m(x_j) ³ n - 1,

где m(х_i), m(x_j) – степени вершин х_i и x_j, то граф G(X) имеет гамильтонову цепь.

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

3.10. Контрольные вопросыи упражнения

 

1. Покажите, что два графа на рис. 3.42 изоморфны.

 

Рис. 3.42. Граф к задаче 1

 

2. «Три дома и три колодца». Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

3. Найдите число частичных графов конечного графа с m ребрами.

4. Каково число ребер в полном неориентированном графе с n вер­шинами?

5. Пусть U – множество положительных целых чисел, на котором задано отношение «а есть делитель b». Постройте граф этого от­ношения для множества целых чисел от 1 до 20.

Рис.3.43. Граф к задаче 6

 

6. Задан граф отношения «быть сестрой» (рис. 3.43) на
множестве студентов-родственников нашего фа-культета. Постройте по рис. 3.43 граф отношения «быть братом».

7. Постройте матрицы смежности и инциденций для правильных многогранников: тетраэдра, куба, октаэдра. Найдите для каждого из них число внутренней устойчивости, число внешней устойчи­вости, центр, периферийные вершины, радиус, диаметр.

8. Для графа, изображенного на рис. 3.44, найдите:

а) матрицу смежности (вершин);

б) матрицу инциденций;

в) наибольшее внутренне устойчивое множество;

г) наименьшее внешне устойчивое множество;

д) матрицу отклонений;

е) вектор отклоненностей;

ж) центр и радиус графа.

Рис. 2.48 - К задаче 9

Рис. 2.48 - К задаче 9

9. Постройте графы, для которых радиус равен 2, 3, и такие графы, для которых диаметр равен 2, 3.

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

11. Какие из из графов правильных многогранников имеют гамильтоновы цепи и циклы.