Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Гамильтоновы графы, нахождение минимального пути в задаче коммивояжера - файл мартынов курсовая дискретка.doc


Гамильтоновы графы, нахождение минимального пути в задаче коммивояжера
скачать (360.6 kb.)

Доступные файлы (6):

kommi.exe
мартынов курсовая дискретка.doc1596kb.14.10.2009 17:20скачать
FILE_ID.DIZ
KOMMI1.TAB
KOMMI.EXE
KOMMI.PAS

содержание
Загрузка...

мартынов курсовая дискретка.doc

  1   2   3   4   5   6
Реклама MarketGid:
Загрузка...
Московский городской университет управления Правительства Москвы
Кафедра Прикладной Математики

Гамильтоновы графы, нахождение минимального пути в задаче коммивояжера
Курсовая работа
по дисциплине «Дискретная математика»

Выполнил: студент I курса экономического факультета направление «информационные системы» Мартынов П.В.

Проверил: д.ф.м.н., профессор Ковалев В.А.

2009

СОДЕРДАНИЕ


СОДЕРДАНИЕ 2

ВВЕДЕНИЕ. 3

1.Гамильтоновы циклы. 4

1.1. Основные понятия и определения 4

1.2. Условия существования гамильтонова цикла 4

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

1.4. Алгебраический метод построения гамильтоновых циклов 6

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

^ 2. Задача коммивояжера. 10

2.1. Общее описание 10

2.2. Алгоритм ближайшего соседа решения ЗК 12

2.3. “Деревянный” алгоритм решения ЗК 14

2.4. Метод лексикографического перебора 16

2.5. Применение алгоритма Дейкстры к решению ЗК 17

2.6. Метод выпуклого многоугольника для решения ЗК 18

2.7. Метод ветвей и границ решения ЗК 20

2.7.1 Входные данные. 20

2.7.2. Идея алгоритма. 20

2.7.3. Определение нижних границ 21

2.7.4. Разбиение множества контуров на подмножества 21

2.7.5. Реализация метода на паскале: 26

2.8. Практическое применение задачи коммивояжера 27

ЗАКЛЮЧЕНИЕ 29

^ СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ. 30

Приложения: 31

Прил.1. 31

Результат работы программы: 33

ВВЕДЕНИЕ.


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

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

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

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

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

В 1859 г. У. Гамильтон придумал игру “Кругосветное путешествие”, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений – задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.
  1. ^

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


Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира.
^

1.1. Основные понятия и определения


Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным.

Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе.

Замечание.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,…,vp графа G добавить вершины u1,…,up и множество ребер {(vi,ui)}{(ui,vi+1)}.

Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) — по входящим.
^

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


В отличие от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла оказывается NP-полной. Большинство известных фактов имеет вид: «если граф G имеет достаточное количество ребер, то граф является гамильтоновым». Приведем несколько таких теорем.

Теорема Дирака. Если в графе G(V,E) c n вершинами (n ≥ 3) выполняется условие d(v) ≥ n/2 для любого vV, то граф G является гамильтоновым.

Доказательство.

От противного. Пусть G — не гамильтонов. Добавим к G минимальное количество новых вершин u1, … ,un, соединяя их со всеми вершинами G так, чтобы G’:= G + u1 + … + un был гамильтоновым.

Пусть v, u1, w, … ,v — гамильтонов цикл в графе G’, причем vG, u1G’, u1G. Такая пара вершин v и u1 в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда wG, w {u1,…,un}, иначе вершина u1 была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u1 была бы не нужна.

Далее, если в цикле v,u1,w, … ,u’,w’, … ,v есть вершина w’, смежная с вершиной w, то вершина v’ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v’, … ,w,w’, … ,v без вершины u1, взяв последовательность вершин w, … ,v’ в обратном порядке. Отсюда следует, что число вершин графа G’, не смежных с v, не менее числа вершин, смежных с w. Но для любой вершины w графа G d(w) ≥ p/2+n по построению, в том числе d(v) ≥ p/2+n. Общее число вершин (смежных и не смежных с v) составляет n+p-1. Таким образом, имеем:

n+p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p.

Следовательно, 0 ≥ n+1, что противоречит тому, что n > 0.

Теорема Оре. Если число вершин графа G(V,E) n ≥ 3 и для любых двух несмежных вершин u и v выполняется неравенство:

d(u)+d(v) ≥ n и (u,v)E, то граф G — гамильтонов.

Граф G имеет гамильтонов цикл если выполняется одно из следующих условий:

Условие Поша: d(vk) ≥ k+1 для k < n/2.

Условие Бонди: из d(vi) ≤ i и d(vk) ≤ k => d(vi)+d(vk)≥n (k≠i)

Условие Хватала: из d(vk) ≤ k ≤ n/2 => d(vn-k) ≥ n-k.

Далее, известно, что почти все графы гамильтоновы, то есть

г
де H(p) — множество гамильтоновых графов с p вершинами, а G(p) — множество всех графов с p вершинами. Таким образом, задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для нее неизвестен (и, скорее всего не существует) эффективный алгоритм решения.

Пример графа, когда не выполняется условие теоремы Дирака, но граф является гамильтоновым.



N = 8; d(vi) = 3; 3 ≥ 8/2 = 4 не гамильтонов граф, но существует гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1)
  1   2   3   4   5   6



Скачать файл (360.6 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации