Курсовая работа на тему: Эйлеровы циклы. Основные понятия и определения. Критерий существования эйлерова цикла

Введение

Целью моей курсовой работы является описание методов нахождения и построения эйлеровых и всех гамильтоновых циклов в графах, а также сравнительный анализ этих методов. Другая цель решаемая в данной работе - это рассмотрение задачи коммивояжера и методов ее решения (включая эвристические и генетические алгоритмы).

Прежде всего, чтобы внести ясность и уточнить терминологию, хотелось бы дать определения некоторым элементам графа таким, как маршрут, цепь, цикл.

Маршрутом в графе G(V,Е) называется чередующаяся последовательность вершин и ребер: v0,е1, … еn,vn, в которой любые два соседних элемента инцидентны. Если v0 = vn, то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, ребра) различны, то маршрут называется простой цепью.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл - контуром.

Оглавление

- Введение 4

- Эйлеровы циклы

- Основные понятия и определения

- Критерий существования эйлерова цикла

- Алгоритмы построения эйлерова цикла

- Некоторые родственные задачи

- Задача китайского почтальона

- Гамильтоновы циклы

- Основные понятия и определения

- Условия существования гамильтонова цикла

- Задачи связанные с поиском гамильтоновых циклов

- Методы построения гамильтоновых циклов в графе

- Алгебраический метод построения гамильтоновых циклов

- Метод перебора Робертса и Флореса

- Улучшение метода Робертса и Флореса

- Мультицепной метод

- Сравнение методов поиска гамильтоновых циклов

- Задача коммивояжера

- Общее описание

- Жадный алгоритм решения ЗК

- Деревянный алгоритм решения ЗК

- Метод лексикографического перебора

- Метод ветвей и границ решения ЗК

- Применение алгоритма Дейкстры к решению ЗК

- Метод выпуклого многоугольника для решения ЗК

- Генетические алгоритмы

- Применение генетических алгоритмов

- Список литературы 41

Список литературы

1. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.

2. Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.

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

4. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.

5. О. Оре. Теория графов, Наука, 1982 г.