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