Министерство народного образования Республики Дагестан

Дагестанский Государственный Университет

Курсовая работа

Программирование задач на графах

Гамильтоновы и эйлеровы циклы

Выполнил:

Студент 4 курса 4 гр. МФ

Цургулов Алил Гасанович

Научный руководитель:

Якубов А. 3.

Махачкала, 2003 год

Содержание

Содержание 2

Введение 4

Глава 1. Эйлеровы циклы 4

§1. Основные понятия и определения 5

§2. Критерий существования эйлерова цикла 5

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

§4. Некоторые родственные задачи 8

§5. Задача китайского почтальона 9

Глава 2. Гамильтоновы циклы 11

§1. Основные понятия и определения 11

§2. Условия существования гамильтонова цикла 11

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

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