Теория графов
Автор: Пользователь скрыл имя, 16 Декабря 2012 в 11:54, курсовая работа
Краткое описание
Теория графов представляет собой раздел математики, имеющий широкие практические приложения. Теория графов – область дискретной математики, особенностью которой является геометрический подход к изучению объектов.
Во многих случаях жизни и, в частности, в проектной практике нам приходится рисовать на бумаге точки, изображающие населенные пункты, отдельные объекты, планировочные узлы и т.п., и соединять эти точки линиями или стрелками, обозначающими некоторые связи или отношения.
Оглавление
ВВЕДЕНИЕ………………………………………………………………….…..3-4
1. Глава 1. Граф и его элементы………………………………………..……6-11
§1.1 Основные понятия…………………………………………………6-7
§1.2 Ориентированный граф…………………….………………………..8
§1.3 Неориентированный граф………………….…………………….…8
§1.4 Смежность………………………………….………………..……9-10
§1.5 Маршруты и пути…………………………………….…………10-11
2. Глава 2. Гамильтоновы графы……………………………………...……12-19
§2.1 Основные определения и результаты……………...…………..12-15
§2.2 Условия существования гамильтонова цикла…………….…..16-17
§2.3 Теорема Дирака…………………………………………………18-19
3. Глава 3. Применение гамильтоновых графов…………………………..20-30
§3.1 Задачи коммивояжера: сущность и применение на практике..20-24
§3.2 Методы решения задачи коммивояжера………………….....…24-26
§3.3 Задачи и их решения………………………………..…………...27-30
ЗАКЛЮЧЕНИЕ……………………………………………………………….…31
СПИСОК ЛИТЕРАТУРЫ…………………..………………………………….. 32
Файлы: 1 файл
ВВЕДЕНИЕ.doc
— 425.00 Кб (Скачать)
Этапы и результат решения можно отметить на графе (см. рис. 13 и 13 а.)
Шаг 1. Шаг.2.
Шаг 3.
Рис. 13.
Решение
Рис. 13 а.
ЗАКЛЮЧЕНИЕ
В данной работе мы познакомились с основными понятиями, определениями и результатами, связанными с гамильтоновыми графами и циклами. Так же мы рассмотрели ту часть теории сложности, которая затрагивает задачи отыскания гамильтонова цикла.
СПИСОК ЛИТЕРАТУРЫ
1. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978.-432с.
2. Белов В.В. Теория графов: Учеб. пособие для студ.высш.техн.учеб. заведений.-М.: Высш.школа, 1976.-392с.
3. Культин Н.Б. Программирование в Turbo Pascal 7.0 и Delphi.- Санкт-Петербург:BHV, 1998.-240c.
4. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.
5. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.
6. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.
7. О. Оре. Теория графов, Наука, 1982 г.
8. www.codenet.ru
9. www.algolist.ru