Выполнил:
Студент 4 курса 4 гр. МФ
Цургулов Алил Гасанович
Научный руководитель:
Якубов А. 3.
§1. Основные понятия и определения 5
§2. Критерий существования эйлерова цикла 5
§3. Алгоритмы построения эйлерова цикла 6
§4. Некоторые родственные задачи 8
§5. Задача китайского почтальона 9
Глава 2. Гамильтоновы циклы 11
§1. Основные понятия и определения 11
§2. Условия существования гамильтонова цикла 11
§3. Задачи связанные с поиском гамильтоновых циклов 13
§4. Методы построения гамильтоновых циклов в графе. 15
§5. Алгебраический метод построения гамильтоновых циклов 15
§6. Метод перебора Робертса и Флореса 16
§8. Улучшение метода Робертса и Флореса 18
§10. Сравнение методов поиска гамильтоновых циклов 21
Глава 3. Задача коммивояжера 23
§2. “Жадный” алгоритм решения ЗК 26
§3. “Деревянный” алгоритм решения ЗК 27
§4. Метод лексикографического перебора 29
§5. Метод ветвей и границ решения ЗК 30
§6. Применение алгоритма Дейкстры к решению ЗК 35
§7. Метод выпуклого многоугольника для решения ЗК 35
§9. Применение генетических алгоритмов 39
ВведениеЦелью моей курсовой работы является описание методов нахождения и построения эйлеровых и всех гамильтоновых циклов в графах, а также сравнительный анализ этих методов. Другая цель решаемая в данной работе — это рассмотрение задачи коммивояжера и методов ее решения (включая эвристические и генетические алгоритмы).
Прежде всего, чтобы внести ясность и уточнить терминологию, хотелось бы дать определения некоторым элементам графа таким, как маршрут, цепь, цикл.
Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер: v0 ,e1 , … en ,vn , в которой любые два соседних элемента инцидентны. Если v0 = vn , то маршрут замкнут, иначе открыт.
Если все ребра различны, то маршрут называется цепью . Если все вершины (а значит, ребра) различны, то маршрут называется простой цепью .
Замкнутая цепь называется циклом ; замкнутая простая цепь называется простым циклом . Граф без циклов называется ациклическим . Для орграфов цепь называется путем , а цикл — контуром .
Глава 1. Эйлеровы циклыТребуется найти цикл, проходящий по каждой дуге ровно один раз. Эту задачу впервые поставил и решил Леонард Эйлер, чем и заложил основы теории графов, а соответствующие циклы теперь называются эйлеровыми. Фигуры, которые требуется обрисовать, не прерывая и не повторяя линии, также относятся к эйлеровым циклам.
Задача возникла из предложенной Эйлеру головоломки, получившей название "проблема кенигсбергских мостов". Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом), омывает два острова. Берега реки связаны с островами так,
как это показано на рисунке.
В головоломке требовалось найти маршрут, проходящий по всем участкам суши таким образом, чтобы каждый из мостов был пройден ровно один раз, а начальный и конечный пункты маршрута совпадали.
Дадим теп
Одними из наиболее популярных услуг на рынке IT-технологий являются создание и продвижение лендингов. Они способны положительно влиять на деятельность любого бизнес-проекта в интернете. Судя по многочисленным отзывам, заказавшие создание лендингов люди ни разу не пожалели о потраченных деньгах. Они вложили в будущее, которое неразрывно связано с интернетом. Всё больше и больше предпринимателей обращаются к услугам разных агентств, веб-студий, чтобы заказать создание лендинга у профессионалов.