Материал: Граф и его элементы

Граф и его элементы

Содержание

Введение

. Граф и его элементы

.1 Основные понятия

.2 Ориентированный граф

.3 Неориентированный граф

.4 Смежность

.5 Маршруты и пути

. Постановка задачи коммивояжера и алгоритмы решения

.1 Задача коммивояжера

.2 Методы решения задачи коммивояжера

. Понятия транспортной сети

.1 Понятие увеличивающая дуга, цепь, разрез

. Алгоритм Флойда-Уоршелл

. Постановка задачи

. Решение задачи аналитическим методом

. Создание приложения для решения задачи

.1 Описание алгоритма

.3 Тестирование программы

.4 Руководство пользователя

Заключение

Список использованных источников

Приложение A. Расчет элементов для матриц

Введение

Теория графов представляет собой раздел математики, имеющий широкие практические приложения. Теория графов - область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Во многих случаях жизни в частности, в проектной практике нам приходится рисовать на бумаге точки, изображающие города, отдельные объекты, железнодорожные узлы и т.п., и соединять эти точки линиями или стрелками, обозначающими некоторые связи или отношения. Такие схемы под различными названиями встречаются всюду, электрические цепи, в физике - радиосхемы; в экономике - диаграммы организации работ и т.д. В основном все схемы рассматриваются в абстрактной форме как самостоятельные математические объекты, названные графами. Такой подход к изучаемым объектам дает возможность теории графов иметь самые разнообразные и многочисленные приложения, в том числе и в области градостроительного проектирования и научных исследований. Первая работа по теории графов, принадлежавшая Эйлеру, появилась в 1736 году и была связана c решением задачи о Кёнигсбергских мостах. Однако, эта работа Эйлера была единственной в течение почти ста лет. Вначале теория графов казалась незначительным разделом математики, так как имела дело лишь c математическими развлечениями и головоломками, например, в схемотехнике, топология межсоединений элементов на печатной плате или микросхеме, задача o перевозках, задача o кругосветном путешествии и др. Развитие математики и ее приложении послужило сильным толчком к развитию теории графов. Уже в середине Х века графы использовались при построении эхем электрических цепей и молекулярных схем. Впервые термин «граф» ввел в 1936г. венгерский математик Денеш Кёниг. B его работе теория графов была представлена как отдельная математическая дисциплина, находящая в настоящее время широкое применение в автоматике, телемеханике, кибернетике, электронике, физике, экономике, психологии, биологии и других областях науки.

1.  Граф и его элементы

1.1    Основные понятия

Граф - это множество точек, называемых вершинами, и множество линий, называемых ребрами, которые соединяют пары вершин (или вершину саму с собой).

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

Например: сеть дорог, соединяющая города 1, 2, 3, 4, 5 можно представить в виде графа следующим образом: города обозначим точками (вершинами), а дороги неориентированными линиями (рисунок 1). Неориентированные линии означают наличие двустороннего движения между соответствующей парой городов. Пересечения линией не считаются вершинами.

Рисунок 1 - Граф сети дорог

Рассмотрим другой пример, ориентированный граф (рисунок 2).

Рисунок 2 - Граф

Таким образом, математически граф можно рассматривать как множество кружков и множество соединяющих их линий. Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок -ребрами.
В зависимости от наличия или отсутствия ориентации у пар элементов из множества V различают графы:

а)      ориентированные <#"877790.files/image003.gif">

Рисунок 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 - Множество смежности

.5 Маршруты и пути

Одно из наиболее простых свойств, которым может обладать граф это свойство быть связным <#"877790.files/image008.gif">

Рисунок 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 часто называют треугольником.

2.  Постановка задачи коммивояжера и алгоритмы решения

2.1 Задача коммивояжера

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

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

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

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

Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения. В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из I в J. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства.

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

.2      Методы решения задачи коммивояжера

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

Выделяют следующие группы методов решения задач коммивояжера, которые относят к простейшим:

а)      Полный перебор.

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

б)      Случайный перебор.

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

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

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

Рисунок 9 - граф для примера

3.  Понятия транспортной сети

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(ei), называемое пропускной способностью дуги, и существует:

-       ровно одна вершина Vo = S, в которую не заходит ни одна дуга, называемая источником или началом сети;

-       ровно одна вершина Vn=t, из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)

Дуга e=(Vi,Vj) называется насыщенной потоком f, если f(Vi, Vj) = c(Vi, Vj)=c(e) (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)

3.1    Понятие увеличивающая дуга, цепь, разрез

Рассмотрим данные понятия на примере:

Разрезом L сети S(N, U) называется множество насыщенных дуг, отделяющих источник s от стока t.

Пусть задана сеть S=(N, U) с множеством вершин N и множеством дуг U.

Определение: дуга u є U, соединяющая вершины i є N, j є N сети S, называется допустимой дугой, если она обладает одним из следующих свойств:

а)      направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше ее пропускной способности:

u=(i, j), j(u)<c(u)       (1)

б)      направление дуги противоположного направлению потока, и величина потока отлична от нуля:

u=(j, i), j(u)>0           (2)

Дуги, обладающие первым свойством, называют увеличивающими; дуги, обладающие вторым свойством, - уменьшающими.

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

Пример 1: построим увеличивающую цепь для сети S=(N, U), представленной на рисунке 10.

Рисунок 10 - увеличивающая цепь

Над каждой дугой указана ее пропускная способность, в скобках - поток по этой дуге.

Цепь (s, 1, 2, 4, t) является увеличивающей, так как все дуги - допустимые:

-       дуга (s, 1) - увеличивающая, так как она проходит по направлению потока, и поток по ней меньше ее пропускной способности:

< 10;

-       дуга (1,2) - также увеличивающая дуга: 12 < 15;

-       дуга (2,4) - уменьшающая, так как она проходит против потока и поток по ней 3 > 0;

-       дуга (4, t) - увеличивающая: 1 < 4.

4. 
Алгоритм Флойда-Уоршелл

Алгоритм Флойда является одним из методов поиска кратчайших путей в графе. В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе.

Прежде чем представлять алгоритмы, необходимо ввести некоторые обозначения. Перенумеруем вершины исходного графа целыми числами от 1 до N. Обозначим через di,jm длину кратчайшего пути из вершинм i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа. (Напомним, что промежуточной вершиной пути является любая принадлежащая ему вершина, не совпадающая с его начальной или конечной вершинами.) Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что di,jm=∞. Из данного определения величин di,jm следует, что величина di,j0, представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе). для любой вершины i положим di,im= 0. Отметим далее, что величина di,jmпредставляет длину кратчайшего пути между вершинами i и j.

Обозначим через Dm матрицу размера NxN, элемент (i, j) которой совпадает с di,jm. Если в исходном графе нам известна длина каждой дуги, то мы можем сформировать матрицу D0. Наша цель состоит в определении матрицы DN, представляющей кратчайшие пути между всеми вершинами рассматриваемого графа.

В алгоритме Флойда в качестве исходной выступает матрица D0. Вначале из этой матрицы вычисляется матрица D1. Затем по матрице D1 вычисляется матрицав D2 и т. д. Процесс повторяется до тех пор, пока по матрице DN-1 не будет вычислена матрица DN.

Рассмотрим основную идею, лежащую в основе алгоритма Флойда. Суть алгоритма Флойда заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если он будет проходить через некоторую промежуточную вершину m. Предположим, что нам известны: