Курсовая с практикой на тему Задача китайского почтальона

Содержание:

Введение 3
1 Теоретическая часть 4
1.1 Эйлеровы циклы 4
1.2 Постановка задачи китайского почтальона 6
1.3 Алгоритм для задачи китайского почтальона 7
1.4 Описание алгоритма решения задачи китайского почтальона 9
2 Практическая часть 11
2.1 Практические применения задачи «китайского почтальона» 11
2.2 Пример решения «задачи китайского почтальона» 12
Заключение 16

Введение:

 
Целью курсовой работы является изучение эйлеровых циклов в графах. Так же необходимо решить «задачу китайского почтальона». Для достижения поставленной цели в работе рассмотрены теоретические вопросы в данной предметной области, предложен способ решения «задачи китайского почтальона». 
Предмет исследований: Задача «Китайского почтальона»
Цель работы: Изучение таких понятий как: эйлеровы циклы и задача китайского почтальона.
Задачи:
1) Узнать, что такое эйлеровы циклы и задача китайского почтальона.
2) изучить алгоритм решения «задачи китайского почтальона»
3) Решить пример данной задачи
Методы исследования: Теоретические методы: теоретический анализ (выделение и рассмотрение отдельных сторон, признаков, особенностей, свойств явлений), индуктивные и дедуктивные методы обобщения полученных данных, математические методы и практические.

Заключение:

Были выполнены все поставленные задачи. Было разобрано понятие эйлеровых задач, и именно задачи «китайского почтальона», решение которой базируется на понятии эйлерова цикла. Был изучен известный алгоритм решения данной задачи
Главной целью бизнеса является получение прибыли. С экономической точки зрения применение алгоритма решения задачи китайского почтальона в конкретных ситуациях позволяет фирмам, особенно тем, которые занимаются доставкой товара, минимизировать транспортные затраты, выполняя при этом все поставки в срок. В настоящее время при поиске оптимальных маршрутов широко используются современные информационные технологии.
В ходе написания курсовой работы были использованы следующие профессиональные компетенции: способность собрать, проанализировать и обработать исходные данные, необходимые для нахождения оптимального маршрута; способностью на основе алгоритма Флёри построить оптимальный маршрут, требующий наименьших затрат.

Фрагмент текста работы:

1 Теоретическая часть
1.1 Эйлеровы циклы

Если дан неориентированный связный граф G, то эйлеров цикл (эйлерова цепь) – это такой цикл (цепь), который проходит ровно один раз по каждому ребру.
Очевидно, не все графы имеют эйлеровы циклы (см., например, граф на рис.1.1), но если эйлеров цикл существует, то это означает, что, следуя вдоль этого цикла, можно нарисовать граф на бумаге, не отрывая от неё карандаша. Граф на рис.1.2 имеет следующий эйлеров цикл (начиная с вершины x1): a1a2a3a4a15a14a13a12a11a16a17a10a9a8a5a7a6. Направление движения по каждому ребру показано на рис.1.2 стрелками.

Эйлер первым в своей знаменитой задаче о кёнигсбергских мостах рассмотрел вопрос о существовании таких циклов в графах. Сегодня эта задача стала классической.
Кёнигсберг был расположен на обоих берегах реки Преголя и на двух островах этой реки. Берега реки и два острова соединены семью мостами, как показано на карте (рис. 1.3, а).

Вопрос, поставленный в 1736 г., состоит в том, можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Если каждый берег реки и острова считать вершиной графа, а каждый мост – ребром, то карту (см. рис. 1.3, а) можно представить в виде графа, изображённого на рис. 1.3, б, и ответ на поставленный вопрос зависит теперь от существования эйлерова цикла в этом графе. Эйлер установил, что указанный граф не содержит эйлерова цикла, и этот результат ознаменовал рождение теории графов. Основная теорема о существовании эйлеровых циклов формулируется так.
Теорема (Эйлер). Связный неориентированный граф G содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда число вершин нечётной степени равно 0 (0 или 2).
Эйлеровым графом называется неориентированный граф, в котором существует цикл, проходящий ровно один раз по каждому из рёбер графа.
Алгоритм Флёри. Пусть G – эйлеров граф. Тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G: выйдя из произвольной вершины, идём по рёбрам графа произвольным образом, соблюдая лишь следующие правила:
а) стираем рёбра по мере их прохождения, а также изолированные вершины (т.е. вершины, не инцидентные никакому ребру), которые при этом образуются;
б) на каждом шаге идём по мосту (т.е. ребру, удаление которого увеличивает число компонент связности) только тогда, когда нет других возможностей.

1.2 Постановка задачи китайского почтальона

Сразу же вспоминается ряд вопросов, связанных с тем, имеется ли в неориентированном графе эйлеров цикл. Например:
1. Каково наименьшее число цепей или циклов необходимо для того, чтобы каждое ребро графа G содержалось точно в одной цепи или в одном цикле? Очевидно, что если G имеет эйлерову цепь или эйлеров цикл, то ответом будет число один.
2. Рёбрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин n_j∙w(a_j), где число n_j показывает, сколько раз проходилось ребро a_j , а w(a_j)– вес ребра a_j ) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится только один раз и вес этого цикла равен тогда ∑_(j=1)^n▒〖w(a_j 〗).
Сформулированная задача 2 называется задачей китайского почтальона.