Курсовая работа: Эйлеровы графы

Решение:

а) Граф связный, найдём степени вершин:

indeg(a)=1 outdeg(a)=1

indeg(b)=5 outdeg(b)=1

Т.к. второе условие теоремы 5 не выполняется, значит, граф не имеет эйлерова цикла.

б) Граф не связный, то есть первое условие теоремы 5 не выполняется. Значит, граф не имеет эйлерова цикла.

в) Граф связный, найдём степени вершин:

indeg(a)=2 outdeg(a)=1

Второе условие теоремы 5 не выполняется, значит, граф не имеет эйлерова цикла.

г) Граф связный, найдём степени вершин:

indeg(a)=2 outdeg(a)=2

indeg(b)=3 outdeg(b)=1

Граф не имеет эйлерова цикла, т.к. не выполняется второе условие теоремы 5.

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

1		2
3	4			5	6
7	8			9	10
11	12		13	14	15
16	17		18	19
20	21

Построим граф, вершинами которого являются комнаты подземелья, а рёбрами – двери. Затем найдём такой путь, чтобы пройти по всем рёбрам (через все двери) в точности по одному разу.

Данный граф имеет эйлеров путь, так как только две вершины имеют нечётную степень, это вершины 6 и 18. Значит, вход и выход могут быть только в вершинах 6 и 18.

Так как комната 6 является крайней, то в ней будет вход, значит, последней комнатой будет 18-ая, следовательно сокровища скрыты в этой комнате.

Заключение

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

Известно, что эйлеровы графы получили широкое распространение и популярность благодаря тому, что многие головоломки и задачи можно решить с использованием знаний теории графов. Частные примеры таких головоломок и сюжетных задач были приведены в практической части. Задачи на отыскание путей через лабиринты, близкие к задачам на эйлеровы графы, находят применение в современной психологии и при конструировании вычислительных машин. Также с практической точки зрения, сейчас графы применяют во многих других областях науки таких как: программирование, физика, химия, биология, экономика и т.д.

Литература

1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 960с.

2. Березина Л. Ю. Графы и их применение. – М.: Просвещение, 1979.

3. Новиков С.А. Дискретная математика для программистов – СПб.: Питер, 2001. – 304с.

4. Оре о. Графы и их применение. – М.: Мир,1973.

5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.