Курсовая работа на тему: Должн., уч. степень, уч. зван. подпись, дата инициалы, фамилия

Введение

Целью моей курсовой работы является:

1. Ознакомление с основными понятиями, связанными с гамильтоновыми графами и циклами.

2. Рассмотреть задачи и методы отыскания гамильтоновых циклов в графах

3. Создание программы для нахождения гамильтоновых циклов.

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

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

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

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

Оглавление

- Введение

- Гамильтоновы графы

- Основные определения и результаты

- Теоремы достаточности гамильтонова графа

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

- Алгебраические методы

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

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

- Заключение

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

Заключение

В данной работе мы познакомились с основными понятиями, определениями и результатами, связанными с гамильтоновыми графами и циклами. Так же мы рассмотрели ту часть теории сложности, которая затрагивает задачи отыскания гамильтонова цикла. И в итоги проведённых изучений была написана программа отыскания гамильтонова цикла в графе.