Теория графов

 

 

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

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

 

§2.3. Теорема Дирака

Поиск необходимого и  достаточного условия для того, чтобы  граф был гамильтоновым, стал одной  из главных нерешенных задач теории графов! О гамильтоновых графах, в сущности, известно очень мало. Большинство известных теорем имеет вид "если граф   имеет достаточное число ребер, то граф   является гамильтоновым графом". Вероятно, самой знаменитой из этих теорем является следующая теорема, принадлежащая Г.Э.Дираку и потому известная как теорема Дирака.

Теорема (Дирак, 1952) Если в простом графе с   вершинами   для любой вершины  , то граф   является гамильтоновым.

Замечание Существует несколько доказательств этой широко известной теоремы, здесь мы приводим доказательство Д.Дж.Ньюмана.

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

Пусть   гамильтонов цикл в графе  , где   — вершины из  , а   — одна из новых вершин. Тогда   не является смежной с  , так как в противном случае мы могли бы не использовать вершину  , что противоречит минимальности  . Более того, вершина, скажем,  , смежная вершине  , не может непосредственно следовать за вершиной , смежной вершине  , потому что тогда мы могли бы заменить   на  , перевернув часть цикла, заключенную между   и  . Отсюда следует, что число вершин графа  , не являющихся смежными с  , не меньше числа вершин, смежных с   (то есть равно, по меньшей мере,   ); с другой стороны, очевидно, что число вершин графа  , смежных с  , тоже равно, по меньшей мере,  . А так как ни одна вершина графа   не может быть одновременно смежной и не смежной вершине  , то общее число вершин графа  , равное  , не меньше, чем  . Это и есть искомое противоречие.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 3.  Применение гамильтоновых графов.

Гамильтоновы  графы применяются для моделирования  многих практических задач, например, служат моделью при составлении  расписания движения поездов. Основой  всех таких задач служит классическая задача:  коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.

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

      -операционные системы;

- алгоритмизация;

- структуры  данных;

- моделирование  и др.

 

§3.1.Задача коммивояжера: сущность и применение на практике.

 

Задача  коммивояжера – задача математического программирования по определению оптимального маршрута движения коммивояжера, цель которого состоит в том, чтобы посетить все объекты, записанные в задании, за кратчайший срок и с наименьшими затратами. В теории графов – это поиск пути, связывающего два или более узла, с использованием критерия оптимальности. 
 
Задача коммивояжера является типичной задачей оптимизации, которая широко применяется при разработке программного обеспечения. Задача о коммивояжере является упрощенной моделью для многих других задач дискретной оптимизации, а также часто является подзадачей. В своей области (оптимизации дискретных задач) она служит своеобразным катализатором, стимулирующим разработку наиболее эффективных методов, алгоритмов и способов их машинной реализации. 
 
Задача коммивояжера формулируется очень просто: на плоскости (в пространстве) расположены N городов, заданы расстояния между каждой парой городов. Требуется найти маршрут минимальной длины с посещением каждого города ровно один раз и с возвращением в исходную точку. 
 
В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода. 
 
Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения. В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из I в J. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства.  
 
На графах задача формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.  
 
Гамильтонов путь (или гамильтонова цепь) – путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.  
Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а ребра – соединяющие их дороги. 
 
Существует несколько частных случаев общей постановки задачи, в частности

-геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости);

-треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника);

-симметричная и асимметричная задачи коммивояжёра.

Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра. 
 
Общая постановка задачи и большинство её частных случаев, относится к классу NP-сложных задач. Поэтому алгоритмы решения этой задачи делятся на точные и приближенные. Все точные алгоритмы фактически представляют собой оптимизированный полный перебор вариантов. В некоторых случаях эти алгоритмы достаточно быстро находят решения, но в общем случае приходится перебирать все n! циклов.  
 
При постановке задачи коммивояжера для k коммивояжеров на множестве из n+1 городов строится k замкнутых маршрутов по следующим правилам:

-один из городов, называемый базой входит во все маршруты;

-каждый из городов, исключая базу входит в ровно один из маршрутов;

-суммарная длина всех маршрутов минимальна.

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

 

Задача  коммивояжера имеет ряд практических применений.  
 
Как правило, речь идет либо о простом перемещением по заданным точкам, либо с развозом груза небольшого формата или веса на транспортном средстве, вмещающем большое количество единиц, что создает предпосылки для применения задачи коммивояжера. Примером реализации задачи на практике является составление оптимального маршрута человека для доставки продуктов в магазины с оптового склада; доставки бутилированной воды; обновления программных продуктов автоматизированного учета на предприятии; пополнения банкоматов наличными деньгами; сбора сотрудников для доставки вахтовым методом; расклейки афиш; сбора наличных денежных средств их терминалов и др. В этом случае вершинами являются места установки терминалов (банкоматов и т.д.) и «базовый пункт». Стоимостью каждого ребра (отрезка маршрута) является время в пути между двумя точками (вершинами) на маршруте. 
 
Еще одно применение задачи коммивояжера – это задача о сверлильном станке. Данное применение задачи является сугубо специализированным приложением, которое заключается в оптимизации движений сверлильного станка ЧПУ для создания большого количества нерегулярно расположенных отверстий или сварочного робота. Сверлильный станок изготавливает металлические листы с некоторым количеством отверстий. Координаты отверстий известны. Необходимо найти кратчайший путь через все отверстия, а значит, и наименьшее время, затрачиваемое на изготовление одной детали. В данном случае, если такой станок делает миллион деталей в год, то даже миллиметровая выгода может сэкономить приличные средства. Этим объясняется стремление развитых стран затрачивать огромные финансовые ресурсы на инвестиции в информационные технологии.  
 
Внимание исследователей к этой задаче привлекает благодаря: большому количеству практических задач, которые к ней сводятся; сосредоточению характерных математических, алгоритмических вычислительных сложностей; простоте и прозрачности формулирования. 

 

§3.2. Методы решения задачи коммивояжера 
Задачи коммивояжера решаются посредством различных методов, выведенных в результате теоретических исследований. Все эффективные методы (сокращающие полный перебор) — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение. 
 
Выделяют следующие группы методов решения задач коммивояжера, которые относят к простейшим:

• Полный перебор;

 
Полный перебор (или метод «грубой силы») — метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

• Случайный перебор;

 
Обычно выбор решения  можно представить последовательностью  выборов. Если делать эти выборы с  помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

• Жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения);

Жадный  алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. При решении задачи коммивояжера жадный алгоритм превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть (рис. 10), представляющую узкий ромб. Коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур. 
 
 
 

 

 

 

                        Рисунок 10.

 

 

 

 

 

 

 

 

 

 

 

§3.3. Задачи и их решения.

Задача№1.

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

 Задачу коммивояжера  можно решить методом перебора: составить все возможные маршруты, найти их длину и выбрать кратчайший маршрут. Например: на рис.11 представлена схема маршрутов, известны расстояния между городами

АВ=7, АС=5, АД=4, ВС=6, ВД=1, СД=8

Всего возможных  циклов шесть –АВСДА, АСВДА, АВДСА, АСДВА, АДВСА, АДСВА. Их длины, соответственно, равны 25, 16, 21, 21,16, 25. Кратчайшими являются маршруты АСВДА и АДВСА.

Задача №2

Задача кратчайшего  пути.

Дана сеть, каждое ребро которой помечено числом, равным его длине. Требуется найти кратчайший маршрут, ведущий от начального узла к конечному.

Алгоритм метода основан на том, что узлам приписывают  либо постоянные, либо временные метки. Начальному узлу приписывают постоянную нулевую метку. Затем определяют узлы, которые можно достигнуть из начального узла. Им приписывают временные метки, равные длине пути из исходного узла. Выбираем узел с кратчайшим путем и приписываем ему постоянную метку. Для этого необходимо следующее:

1.Рассмотрим  оставшиеся узлы с временной  меткой. Сравним значение каждой временной метки с суммой значения последней из постоянных меток и длины ветви, ведущей из соответствующего узла с постоянной меткой в рассматриваемый узел. Минимальное из двух сравниваемых значений определяет новую временную метку рассматриваемого узла. Если значение прежней временной метки меньше, то временная метка сохраняется.

2.Среди временных  меток выбираем ту, значение которой  минимально и объявляем ее  постоянной меткой. Если при этом  постоянную метку приписывают  конечному узлу, то задача решена. В противном случае переходим на шаг 1.

 

Пример. Найти кратчайший путь из узла 1 в узел 6 (рис. 12).

Алгоритм решения  оформим в виде таблицы и отметим шаги решения на рис. 13.

 

№ шага	Узел с постоянной меткой	Достигае-мый  из j узел	путь	Длина пути	Временная метка узла j	Характер метки
I	1	2 3 4	1-2 1-3 1-4	3 5 8	(3,1)-min (5,1) (8,1)	пост врем врем.
II	1   2	3 4 3 5 6	1-3 1-4 1-2-3 1-2-5 1-2-6	5 8 7 11 15	(5,1)- min (8,1) (7,2) (12,2) (15,2)	пост врем - врем врем
III	1 2   3	4 5 6 4 5	1-4 1-2-5 1-2-6 1-3-4 1-3-5	8 12 15 6 16	(8,1) (12,2) (15,2) (6,3)- min (16,3)	- врем врем пост -
IV	2   3 4	5 6 5 5 6	1-2-5 1-2-6 1-3-5 1-3-4-5 1-3-4-6	12 15 16 14 10	(12,2) (15,2) (16,3) (14,4) (10,4)	врем. - - - пост.