Гамильтоновы графы и сложность отыскания гамильтоновых циклов

Содержание

Введение

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

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

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

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

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

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

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

Приложение

Заключение

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

Введение



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

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

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

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

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

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

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

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