В 1857 году ирландский математик Гамильтон предложил игру, названную «путешествие по додекаэдру». Игра сводилась к обходу по рёбрам всех вершин правильного додекаэдра при условии, что ни в одну из вершин нельзя заходить более одного раза.
Додекаэдр- это многогранник, граням и которого служат 12 правильных пятиугольников. У него 20 вершин и 30 рёбер. На первом рисунке изображен додекаэдр с прозрачными гранями, а на втором с непрозрачными. Обрати внимание, что в каждой вершине додекаэдра сходятся по три ребра.
Представь, что наш додекаэдр сделан из проволоки и его можно растягивать без разрывов. Взявшись за вершины A, B, C, D, E, растянем додекаэдр на столе. Получим изображенный на рисунке граф.
Как же обойти все вершины додекаэдра, причём в точности по одному разу? Найди несколько маршрутов.
Кстати, все эти маршруты представляют собой цикл. Но не обыкновенный, а гамильтонов цикл.
Гамильтоновым циклом в графе называют цикл, проходящий через каждую вершину графа в точности по одному разу.
Гамильтоновым путём в графе называют путь, проходящий через каждую вершину графа в точности по одному разу.
Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.
Эйлеровы и гамильтоновы пути и циклы сходны по способу задания. Первые содержат все рёбра, и при том по одному разу каждое, вторые – все вершины, по одному разу каждую. Чтобы определить, обладает ли граф эйлеровым путем или циклом, достаточно определить степень каждой из его вершин. Но пока не найден способ, который бы позволил определить заранее, обладает ли граф гамильтоновым путем или циклом.
- Представь, что на графе были изображены 20 городов и дороги, соединяющие их. Начав путешествие в городе Р, надо объехать все остальные города, не заехав ни в один город более одного раза. Выпиши последовательность городов, в которой можно совершить такое путешествие, если:
а) окончить путешествие нужно в городе D;
б) в первую очередь нужно заехать в города T, O, N, M, а вернуться в город Р;
в) в первую очередь нужно заехать в города T и S, а окончить путешествие в городе В.
2. Вокруг дома садовник посадил 20 кустов роз, которые пронумеровал так, чтобы он мог, выйдя из дома, который находился в центре участка, обойти все розы, побывав у каждой в точности один раз. Однажды он, изменив своим правилам, полил сначала розы под номерами 19, 18, 17 и 16.
а) В какой последовательности садовник мог бы дальше поливать розы?
б) После кустика под номером 16 садовник полил ещё 6 кустов. После этого оказалось, что он уже не мог полить остальные, не побывав ни у одной более одного раза. Какие 6 шагов он сделал неосторожно?
3. Найди на рисунках эйлеровы графы и гамильтоновы графы.
4. На рисунке изображена схема, на которой квадратиком отмечен магазин, а остальными вершинами мест жительства заказчиков. Как шофёру машины «Доставка на дом» объехать всех заказчиков, не подъезжая ни к одному дому более одного раза?
