Материал: Граф и его элементы
Введение
Теория графов представляет собой раздел математики, имеющий широкие практические приложения. Теория графов -- область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Во многих случаях жизни в частности, в проектной практике нам приходится рисовать на бумаге точки, изображающие города, отдельные объекты, железнодорожные узлы и т.п., и соединять эти точки линиями или стрелками, обозначающими некоторые связи или отношения. Такие схемы под различными названиями встречаются всюду, электрические цепи, в физике - радиосхемы; в экономике - диаграммы организации работ и т.д. В основном все схемы рассматриваются в абстрактной форме как самостоятельные математические объекты, названные графами. Такой подход к изучаемым объектам дает возможность теории графов иметь самые разнообразные и многочисленные приложения, в том числе и в области градостроительного проектирования и научных исследований. Первая работа по теории графов, принадлежавшая Эйлеру, появилась в 1736 году и была связана c решением задачи о Кёнигсбергских мостах. Однако, эта работа Эйлера была единственной в течение почти ста лет. Вначале теория графов казалась незначительным разделом математики, так как имела дело лишь c математическими развлечениями и головоломками, например, в схемотехнике, топология межсоединений элементов на печатной плате или микросхеме, задача o перевозках, задача o кругосветном путешествии и др. Развитие математики и ее приложении послужило сильным толчком к развитию теории графов. Уже в середине Х века графы использовались при построении эхем электрических цепей и молекулярных схем. Впервые термин «граф» ввел в 1936г. венгерский математик Денеш Кёниг. B его работе теория графов была представлена как отдельная математическая дисциплина, находящая в настоящее время широкое применение в автоматике, телемеханике, кибернетике, электронике, физике, экономике, психологии, биологии и других областях науки.
Граф и его элементы
1.1 Основные понятия
Граф - это множество точек, называемых вершинами, и множество линий, называемых ребрами, которые соединяют пары вершин (или вершину саму с собой).
Геометрически граф можно представить как набор вершин (точек), определенные пары которых соединены линиями.
Например: сеть дорог, соединяющая города 1, 2, 3, 4, 5 можно представить в виде графа следующим образом: города обозначим точками (вершинами), а дороги неориентированными линиями (рисунок 1). Неориентированные линии означают наличие двустороннего движения между соответствующей парой городов. Пересечения линией не считаются вершинами.
Рисунок 1 - Граф сети дорог
Рассмотрим другой пример, ориентированный граф (рисунок 2).
Рисунок 2 - Граф
Таким образом, математически граф можно рассматривать как множество кружков и множество соединяющих их линий. Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок -ребрами. В зависимости от наличия или отсутствия ориентации у пар элементов из множества V различают графы:
а) ориентированные,
б) неориентированные (реберные),
в) смешанные.
1.2 Ориентированный граф
Граф называется ориентированным или орграфом, если некоторые ребра имеют направление (рисунок 3). Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет.
Рисунок 3 - Ориентированный граф
1.3 Неориентированный граф
В неориентированном графе отношения симметричны, то есть (u, v) = (v, u). В неориентированном графе нет дуг, связи называют ребрами.
Рисунок 4 - Неориентированный граф
1.4 Смежность
задача коммивояжер транспортный приложение
Пусть D1, D2- вершины, е = (D1, D2) - соединяющее их ребро (рисунок 5). Тогда вершина D1 и ребро е инцидентны, вершина D2 и ребро е также инцидентны.
Рисунок 5 - Смежные вершины
Две вершины называются смежными, если они соединены ребром/дугой (рисунок 5).
Два ребра называются смежными, если они соединены вершиной/узлом (рисунок 6).
Рисунок 6 - Смежные ребра
Смежные вершины - две вершины, инцидентные одному ребру.
Смежные ребра - два ребра, инцидентные одной вершине.
Множество вершин, смежных с вершиной V, называется множеством смежности вершины V и обозначается Г+(V) (рисунок 7).
Рисунок 7 - Множество смежности
1.5 Маршруты и пути
Одно из наиболее простых свойств, которым может обладать граф это свойство быть связным. В данном разделе рассматриваются основные структурные свойства связных и несвязных графов.
Маршрут в графе - чередующаяся последовательность вершин и ребер.
Эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним (рисунок 8).
Рисунок 8 Граф для иллюстрации маршрутов
Указанный маршрут соединяет вершины Do и Dn, и его можно обозначить Do,D1,D2,...,Dn (наличие ребер подразумевается). Эта последовательность иногда называется (Do-Dn) - маршрутом. Маршрут замкнут, если D = Dn, и открыт в противном случае.
Цепь - маршрут с различными ребрами.
Простая цепь-маршрут с различными вершинами (а значит, и ребрами).
Цикл- замкнутая цепь.
В помеченном графе J на рисунке 8 D1 D2 D3 D4 - маршрут, который не является цепью, а D1 D2 D4 D3 D2 - цепь, где D1 D2 D4 D3 - простая цепь и D2 D4 D3 D2 - простой цикл.
Обозначим через Jn граф состоящий из одного простого цикла с n вершинами, и через Pn простую цепь с n вершинами. Jn часто называют треугольником.
Постановка задачи коммивояжера и алгоритмы решения
Задача коммивояжера
Задача коммивояжера - задача математического программирования по определению оптимального маршрута движения коммивояжера, цель которого состоит в том, чтобы посетить все объекты, записанные в задании, за кратчайший срок и с наименьшими затратами. В теории графов - это поиск пути, связывающего два или более узла, с использованием критерия оптимальности.
Задача коммивояжера является типичной задачей оптимизации, которая широко применяется при разработке программного обеспечения. Задача о коммивояжере является упрощенной моделью для многих других задач дискретной оптимизации, а также часто является подзадачей. В своей области (оптимизации дискретных задач) она служит своеобразным катализатором, стимулирующим разработку наиболее эффективных методов, алгоритмов и способов их машинной реализации.
Задача коммивояжера формулируется очень просто: на плоскости (в пространстве) расположены N городов, заданы расстояния между каждой парой городов. Требуется найти маршрут минимальной длины с посещением каждого города ровно один раз и с возвращением в исходную точку.
В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода.
Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения. В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из I в J. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства.
На графах задача формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.
Методы решения задачи коммивояжера
Задачи коммивояжера решаются посредством различных методов, выведенных в результате теоретических исследований. Все эффективные методы (сокращающие полный перебор) -- методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение.
Выделяют следующие группы методов решения задач коммивояжера, которые относят к простейшим:
а) Полный перебор.
Полный перебор (или метод «грубой силы») -- метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
б) Случайный перебор.
Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.
в) Жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения).
Жадный алгоритм - алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. При решении задачи коммивояжера жадный алгоритм превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть (рисунок 9), представляющую узкий ромб. Коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.
Рисунок 9 - граф для примера