Гамильтоновой цепьюв неориентированном графе называется цепь, проходящая через каждую его вершину один и только один раз.
Гамильтоновым цикломв неориентированном графе называется цикл, проходящий через каждую вершину один и только один раз за исключением начальной вершины, которая совпадает с конечной.
Гамильтоновым путемв ориентированном графе называется путь S = (х1, ..., хn), проходящий через все вершины графа, притом только по одному разу.
Гамильтоновым контуромназывается контур М=(х0, х1, ..., хn, х0) в ориентированном графе G(X), если он проходит через все вершины графа по одному разу.
Существует следующая распространенная интерпретация задачи о гамильтоновых циклах. Обед накрыт на круглом столе. Среди гостей некоторые являются друзьями. При каких условиях можно рассадить всех так, чтобы по обе стороны от каждого из присутствующих сидели его друзья?
В применении графов к играм вершины соответствуют различным позициям. Существование гамильтонова цикла равносильно существованию циклической последовательности ходов, содержащей каждую позицию по одному разу. Примером является задача о шахматном коне: можно ли, начиная с произвольного поля на доске, ходить конем в такой последовательности, чтобы пройти каждое из шестидесяти четырех полей и вернуться в исходное?
К гамильтоновым циклам относится также известная задача о бродячем торговце (задача о коммивояжере). Район, который должен посетить коммивояжер, содержит определенное количество городов. Расстояния между ними известны, и нужно найти кратчайшую дорогу, проходящую через все пункты и возвращающуюся в исходный. Эта задача имеет ряд приложений в экономике и исследовании операций.
Сформулирован целый ряд достаточных условий существования гамильтоновых цепей, циклов, путей и контуров. Приведем некоторые из них без доказательства.
Теорема Кёнига. В полном конечном графе всегда существует гамильтонов путь.
Если в графе G(X) с n вершинами для любой пары вершин xi и xj справедливо неравенство
m(хi) + m(xj) ³ n - 1,
где m(хi), m(xj) – степени вершин хi и xj, то граф 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. Какие из из графов правильных многогранников имеют гамильтоновы цепи и циклы.
СПИСОК ЛИТЕРАТУРЫ
1. Адельсон-Вельский Г. М., Кузнецов О. П. Дискретная математика для инженера. – М. Энергоатомиздат, 1988.– 479 c.
2. Нефедов В. Н., Осипова В.А. Курс дискретной математики: Учебное пособие. – М.: Изд-во МАИ, 1992.– 262 с.
3. Ерусалимский Я. М. Дискретная математика: теория, задачи, приложения. – М: Вузовская книга, 2000.–280 с.
4. Новиков Ф. А. Дискретная математика для программистов: Учебное пособие. – СПб: Питер, 2002. –304 с.
5. Хаггарти Р. Дискретная математика для программистов: Учебное пособие для вузов / Пер. с англ. – М.: Техносфера, 2003. – 320 с.
6. Корниенко А. В. Дискретная математика: Учебное пособие. – Томск: Изд-во ТПУ, 2000. – 104 с.
7. Сафьянова Е. Н. Дискретная математика. Часть 1: Учебное пособие. – Томск: Изд-во ТУСУР, 2000. – 106 с.
8. Смыслова З. А. Дискретная математика: Учебное пособие. – Томск: Изд-во ТУСУР, 2000. – 116 с.
Для графа, изображенного на рис. 3.44, найдите:
