Курсовая работа на тему: Гамильтоновы графы. Основные определения и результаты. Теоремы достаточности гамильтонова графа

Введение

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

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

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

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

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

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

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

Оглавление

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

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

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

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

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

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

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