Тема 11. Эйлеровы и Гамильтоновы графы

Задание 1. Какие из указанных на рисунках графов являются эйлеровыми?

Задание 2. Существует ли эйлеров цикл (путь) в графах, изображенных на рисунках?

Задание 3. Изобразите графы на 8 вершинах, обладающие (не облада­ющие) эйлеровым путем; эйлеровым циклом.

Задание 4. Пусть в связном графе две вершины u и v имеют нечетную степень, а степень остальных вершин четна. Докажите, что вершины u и v соединены путем.

Задание 5. В некоторой стране из любого города выходит ровно 100 дорог таким образом, что из любого города можно попасть в любой другой город. Докажите, что сообщение между горо­дами не нарушится, если в этой стране закрыть одну дорогу на ремонт.

Задание 6. Являются ли эйлеровыми графами полный граф, полный двудольный граф, граф Петерсена, колесо? Есть ли эйлеровы графы среди графов тел Платона?

Задание 7. Докажите, что связный граф является эйлеровым тогда и только тогда, когда множество его ребер можно разбить на непересекающиеся циклы.

Задание 8. Докажите, что линейный граф эйлерова графа является эй­леровым. Если линейный граф эйлеров, будет ли эйлеровым сам граф?

Задание 9. Докажите, что граф имеет 264 эйлеровых цикла.

Задание 10. Пусть граф G – эйлеров. Что можно сказать о его допол­нении ?

Задание 11. На рисунке представлен план художественной выставки. Где на выставке следовало бы сде­лать вход, а где – выход?

Задание 12. Докажите, что для любого связного графа можно постро­ить циклический маршрут, содержащий все ребра графа в точ­ности 2 раза, по 1 разу в каждом направлении.

Решение. Метод построения такого маршрута называется ме­тодом Фарри. Он заключается в следующем. Из любой верши­ны А идем в произвольную вершину В, отмечаем пройденное ребро стрелкой. Ребро, по которому мы впервые прибываем в вершину, обозначаем двойной стрелкой. Выходя из вершины, выбираем либо ребро, по которому не проходили, либо ребро, по которому только что прибыли. Ребро, по которому мы впер­вые попали в вершину, используем только тогда, когда это – единственная оставшаяся возможность. Процесс может закон­чится только в исходной вершине А. Выхода из А нет, так как процесс закончен. Входа в А также не осталось, так как число входов равно числу путей, по которым мы выходили из А. Сле­довательно, ребро АВ пройдено в обоих направлениях. Тогда все ребра, содержащие В, также пройдены в обоих направле­ниях (АВ — последнее из используемых) и т.д.

Замечание. Если у лабиринта все стенки связаны друг с другом, то такой лабиринт всегда можно обойти, касаясь стенки одной рукой.

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

Задание 14. Являются ли указанные на рисунках графы гамильтоновыми?

Задание 15. Являются ли гамильтоновыми графами полный граф, полный двудольный граф, граф Петерсена, колесо?

Задание 16. Покажите, что все графы тел Платона являются гамильтоновыми.

Задание 17. Докажите, что граф Петерсена не является гамильтоновым.

Задание 18. Приведите пример гамильтонова, но не эйлерова графа; эйлерова, но не гамильтонова графа. Что можно сказать о гра­фах, одновременно являющихся и эйлеровыми, и гамильтоно­выми графами?

Задание 19. Постройте гамильтонов цикл на графе додекаэдра.

Решение. Построим гамильтонов путь, заметив, что , , , где L (R) означает поворот налево (напра­во, соответственно). Тогда

– мы получили искомый путь, состоящий из 20 ребер.

Задание 20. Докажите, что если в графе на n ≥ 3 вершинах d (v) +d (u) ≥ n для каждой пары вершин, то граф является гамильтоновым. Выведите отсюда теорему Дирака.

Задание 21. Докажите, что линейный граф гамильтонова графа явля­ется гамильтоновым. Зная, что линейный граф является га­мильтоновым, можно ли утверждать, что и сам граф является гамильтоновым?

Задание 22. Девять гурманов во время конференции садятся за круг­лый стол, причем любые два из них занимают соседние места только 1 раз. Что можно сказать о продолжительности конфе­ренции?

Задание 23. Найдите в графе n гамильтоновых циклов, никакие два из которых не имеют общих ребер. Выполните аналогичное задание для .