![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Задание 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 гамильтоновых циклов, никакие два из которых не имеют общих ребер. Выполните аналогичное задание для
.
Дата публикования: 2015-01-10; Прочитано: 1585 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!