Решение задач на тему: Условия существования гамильтонова цикла

Введение

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

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

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

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

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

Оглавление

- Введение 2

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

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

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

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

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

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

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

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

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

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

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

- Заключение 24

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

Заключение

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

Отметим, собственно что выдумано большое количество увеселительных и нужных задач, связанных с розыском гамильтоновых циклов. Сформулируем 2 из них.

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

(Задача о шахматном жеребце.) Возможно ли, начиная с случайного поля шахматной доски, обогнуть жеребцом поочередно все 64 поля по 1 разу и возвратиться в начальное поле?

Проверили, собственно что пока же непонятно ни малейшего незатейливого аспекта или же алгеб-раического способа, позволяющего ответить на вопрос, есть или же нет в случайном графе G гамильтонов цикл.

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

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

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

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

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

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