ведение 3
Глава 1. Гамильтоновы графы
1.1 Основные определения и известные результаты 5
1.2 Теорема Дирака 8
Глава 2. Практическая часть
2.1 Задача коммивояжера 9
2.2 Задача о кругосветном путешествии 17
2.3 Задачи, приводящие к графам 19
Заключение 22
Список литературы 23

Купить

Гамильтоновы путь, цикл и граф названы в честь ирландского математика Уильяма Гамильтона, который впервые определил эти классы, исследовав задачу кругосветного путешествия по додекаэдру. Гамильтоновы графы применяются для моделирования многих практических задач, например, служат моделью при составлении расписания движения поездов.
Цель дипломной работы - изучить свойства гамильтоновых графов, определить основные понятия теории графов, доказать теорему Дирака (о достаточных условиях гамильтоновости графа) и решить задачи связанные с гамильтоновыми графами.
Объект дипломной работы - Гамильтоновы графы.
Предмет дипломной работы - Теория графов.
Структура дипломной работы: дипломная работа состоит из введения, двух глав, 5 параграфов, заключения и списка использованных источников и литературы.
Во введении сформулированы: объект и предмет исследования. В первой главе рассматриваются основные теоретические определения, и приводится доказательство теоремы Дирака в авторском варианте. Во второй главе решаются определенные задачи, приводящие к графам.
Для того чтобы изучить гамильтоновы графы, я изучила некоторые статьи и диссертационные работы про гамильтоновых графов последних лет.
В статье «Конструктивные описания гамильтоновых графов» Иорданского Михаила Анатольевича рассматривается процессы построения гамильтоновых графов с помощью операций объединения с пересечением [журнал «Вестник Нижегородского университета им. Н.И. Лобачевского]. Москвин Андрей Юрьевич в своей диссертационной работе предложил метод доказательства полноты гамильтоновых полей, обладающих большим количеством первых интегралов [www.msu.ru.«Топология особенностей дробно¬рациональных интегрируемых систем»]. Коровина Наталья Валентиновна изучила гамильтоновы системы, интегрируемые по Лиувилию[www.msu.ru.«Геометрия интегрируемых случаев динамики твердого тела»]. В её диссертации исследуются интегрируемые гамильтоновы системы с точки зрения траекторной эквивалентности. Севастьянов Сергей Васильевич - его диссертация посвящена разработке эффективных методов решения NP-трудных задач с помощью гамильтоновых циклов и других графов [www.dissercat.com.«Геометрические методы и эффективные алгоритмы в теории расписаний»]. Ролдугин Павел Владимирович с помощью гамильтоновых графов вывел максимально не гамильтоновые графы [www.dissercat.com.«Максимально не гамильтоновые графы»].Новиков Сергей Валерьевич в своей диссертационной работе рассматривал модель распространения вирусных атак в сетях передачи данных общего пользования на основе расчёта длины гамильтонова пути [www.dissercat.com].
После изучения этих статьей сделан вывод, что гамильтоновы циклы, пути, графы можно использовать везде и что они играют важную роль в построении экономических схем товарооборота, при анализе ДНК в биологии, в вопросах организации и автоматизации производства, в электротехнике при проектировании электрических цепей и других прикладных областях. В дипломной работе приводиться доказательство теоремы Дирака, самостоятельно составлены и решены задачи на нахождение гамильтоновых графов. Задачи: изучить известные результаты в области гамильтоновых графов и доказать теорему Дирака.
Купить