Чебоксарский политехнический институт (филиал)
УНИВЕРСИТЕТА МАШИНОСТРОЕНИЯ
Кафедра управления в технических системах и программирования
КУРСОВАЯ РАБОТА
по дисциплине Дискретная математика
на тему Гамильтоновы графы и их свойства
вариант 8
Выполнил:
студент группы 09.03.01 -2зс
Коробов Алексей Сергеевич
учебный шифр 1014008
Проверил:
Решетников Алексей Владимирович
Чебоксары 2016
Содержание
Введение
1. Понятие Гамильтонова графа
1.1 Основные понятия теории графов
1.2 Свойства маршрутов, цепей и циклов
1.3 Понятие гамильтонова графа. Теорема Дирака
2. Задача о коммивояжере
2.1 Историческая справка
2.2 Постановка задачи о коммивояжере
2.3 Методы решения задачи о Коммивояжере
2.4 Метод ветвей и границ
Заключение
Список использованной литературы
Введение
Актуальность данной темы заключается в следующем: для решения оптимизационных и других задач строительства, нередко прибегают к формулировке поставленной задачи в виде каких-то хорошо известных математических задач: транспортная задача, задача поиска оптимального пути (задача коммивояжера) и другие. Сформулированную таким образом задачу решают, используя такие математические методы, как метод ветвей и границ.
Переборные алгоритмы не эффективны (в расчете на худшую задачу), поэтому успех в решении каждой конкретной задачи существенным образом зависит от способа организации перебора.
Знаменитая задача коммивояжера, поставленная еще в 1934 г., является одной из самых важнейших задач в теории графов. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются все новые методы.
Целью исследования является нахождение наиболее точного алгоритма поиска оптимального пути.
Задачи исследования:
1. Изучить основополагающие понятия: граф, маршрут, цепь, контур, цикл.
2. Рассмотреть известные способы решения задачи о коммивояжере.
3. Обобщить полученные результаты.
Прaктичeскaя знaчимoсть рaбoты зaключaeтся в тoм, чтo рeзyльтaты исслeдoвaния мoгyт быть испoльзoвaны во многих практических задачах.
Стрyктyрa рaбoты: рaбoтa сoстoит из ввeдeния, двyх глaв, зaключeния и спискa литeрaтyры.
Понятие Гамильтонова графа
Основные понятия теории графов
Пусть V – непустое множество, V(2) – множество всех его двухэлементных подмножеств. Пара (V,E), где E – произвольное подмножество множества V(2), называется простым графом (неориентированным графом). Элементы множества V называются вершинами графа, а элементы множества E – ребрами. Итак, граф – это конечное множество V вершин и множество E ребер, EÌV(2).
Например:
V = {a,b,c,d}; V(2) = {{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}}
G1 = V(2)
G2= {{a,d},{b,d},{c,d}}
Рис. 1 Граф G1 и Граф G2
Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.). Множества вершин и ребер графа G обозначается соответственно V(G) и E(G). Вершины и ребра графа называются его элементами. Число |V(G)| вершин графа G называется его порядком и обозначается |G|. Если |G|=n, |EG|=m, то граф называют (n, m)-графом. Говорят, что две вершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если e={u, v} – ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v. Два ребра называются смежными, если они имеют общий конец. Вершина v и ребро e называются инцидентными, если v является одним из концов ребра e, и не инцидентными в противном случае. Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.
Маршрутом (или путем) в графе G называется чередующаяся последовательность вершин и ребер v0, e1, v1, …, vt−1, et, vt+1, в которой ei = vi−1vi (1 ≤ i ≤ t). Такой маршрут кратко называют (v0, vt)-маршрутом и говорят, что он соединяет v0 c vt; в свою очередь вершины v0, vt — это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v0, v1, …, vt своих вершин. Если v0=vt, то (v0, vt)-маршрут называется замкнутым.
Цепь — это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром).
Свойства маршрутов, цепей и циклов
1) Всякий незамкнутый (u, v)- маршрут, содержит в себе простую (u, v)- цепь. Вчастности, любая (u, v)- цепь, содержит в себе простую (u, v)- цепь. Причем, если (u, v)- маршрут содержит в себе вершину w (w≠u и w≠v), то в общем случае, простая (u, v)- цепь может не содержать в себе вершину w.
2) Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.
3) Всякая непростая (u, v)- цепь, может быть разбита на простую (u, v)- цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.
4) Для любых трех вершин u, w, v из существования (u, w)- цепи их и (w, v)- цепи,следует существование (u, v)- цепи. Причем может не существовать (u,v)- цепи, содержащей вершину w.
5) Объединение двух несовпадающих простых (u, v)- цепей содержит простой цикл.
6) Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.