Обзор алгоритмов на графах

Построим граф G: каждой работе соответствует определенная вершина графа, а ребро () существует в графе тогда и только тогда, когда для выполнения i-й и j-й работ требуется хотя бы один общий ресурс, т. е. когда Si∩Sj≠Ø. Это означает, что i-я и j-я работы не могут выполняться одновременно. Раскраска графа G определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цвета, выполняются одновременно. Наилучшее использование ресурсов (т. е. выполнение всех n работ за наименьшее время) достигается при оптимальной раскраске вершин графа G.

 

Естественно, что круг применения не ограничен приведенными примерами.

 

 

Нахождение кратчайших путей

В последнее  время активно развивается теория о нахождении кратчайших путей.

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

Существуют  три наиболее эффективных алгоритма  нахождения кратчайшего пути: алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами), алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин) и алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами)

Алгоритм Дейкстры

Идея основывается на следующем очевидном утверждении.

Пусть построен минимальный путь из вершины A в вершину B. И пусть вершина B связана с  некоторым количеством вершин i. Обозначим через Ci – цену пути из вершины B в вершину i. Выберем из Ci минимальную величину. Тогда минимальное продолжение пути из точки B пойдёт через выбранную величину.

И из него вытекает следствие. Пусть есть множество  вершин через которые уже проходят минимальные пути. Такое множество гарантированно есть, это вершина 1. Утверждение сформулированное выше даёт возможность добавлять к уже существующему множеству вершин (будем далее называть их выделенными) еще одну вершину, а так как в графе количество вершин конечно, то за конечное количество  шагов все вершины графа окажутся выделенными, а это и будет решением.

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

1. Строим множество вершин инцидентных выделенным и находим среди их вершину с наименьшей ценой. Найденная вершина добавляется в множество выделенных.
2. Строим множество вершин инцидентных выделенным и определяем для них новые цены. Новая цена вершины это минимальная цена пути от множества выделенных вершин до данной вершины. Строится новая цена так:

1. Для невыделенной вершины во множестве выделенных определяется подмножество вершин инцидентных данной.
2. Для каждой вершины выделенной подмножества определяется цена пути до данной.
3. Определяется минимальная цена. Эта цена и становится ценой вершины.

Схема алгоритма:

1. Множество выделенных вершин = исходная вершина
2. Пока есть невыделенные вершины выполнять

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

2. Среди множества вершин, для которых определена предварительная цена, найти вершину с минимальным значением предварительной цены.
3. Найденную вершину занести во множество выделенных вершин.

Алгоритм Флойда

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

Построим матрицу  размерности |V| x |V|, элементы которой (обозначим из v) определяются по правилу:

= 0;

=  Вес (, ), где i<>j, если в графе существует ребро (дуга) (, );

=  бесконечность , где i<>j, если нет ребра (дуги) (, ).

 

Схема алгоритма:

 

1. Выполнять цикл, завершение которого наступает по выполнению одного из двух условий: либо количество шагов цикла равно V, либо был обнаружен цикл отрицательной длины. Шаги цикла нумеруются с нуля. Шаг цикла будем обозначать переменной m.

1. Строится матрица с индексом равным номеру шага, обозначим его через m, в которой элементы определяются через элементы матрицы предыдущего шага по следующим формулам:

+1=min{, + },

где i<>j; =0.

2. Если + < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину ;

 

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

 

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

Нахождение  кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.

 

 

Эйлеровы графы

Решение Эйлером задачи о  Кёнигсбергских мостах привела к  первой опубликованной работе по теории графов. Задачу об обходе мостов можно  обобщить и получить следующую задачу теории графов: можно ли найти в  данном графе G цикл, содержащий все  вершины и все рёбра? Граф, в  котором это возможно, называется эйлеровым. Таким образом, эйлеров граф имеет эйлеров цикл – замкнутую цепь, содержащую все вершины и все рёбра.

 

Алгоритм  нахождения эйлерова цикла

Пусть G(X, E) — связный неорентированный граф, не имеющий вершин нечетной степени. Назовем мостом такое ребро, удаление которого из связного графа разбивает этот граф на две компоненты связности, имеющие хотя бы по одному ребру.

 

   1)  Пусть a — произвольная вершина графа G. Возьмем любое ребро e₁=(a,

         x₁) , инцидентное вершине a, и положим m = {e₁}.

   2)  Рассмотрим подграф G₁(X, E\m₁). Возьмем в качестве e₂ ребро, инци-

        дентное вершине x₁ и неинцидентное вершине a, которое также не

        является мостом в подграфе G₁ (если такое ребро e₂ существует).

        Получим простую цепь m₂ = {e₁, e₂}.

   3) Пусть e₂ = (x₁, x₂), x ¹ a. Рассмотрим подграф G₂(X, E\m₂) и удалим из

        него все изолированные вершины. В полученном подграфе выберем

        ребро e₃ÎE\m₂, инцидентное вершине a, которое не является мостом в

        подграфе (если такое ребро e₃ существует!). Получим простую цепь

        m₃ = {e₁, e₂, e₃}.

 

Продолжая указанный процесс, мы через  конечное число шагов получим  эйлеров цикл m = {e1, e2, …, en}, где n — число ребер графа G(X, E).

 

Практическое применение алгоритма  решения задачи

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

 

Задача о наибольшем потоке

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

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

Два наиболее популярных алгоритма — алгоритм Форда-Фалкерсона и алгоритм "проталкивания предпотока".

Алгоритм Форда-Фалкерсона

Идея алгоритма  заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Схема алгоритма:

1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:

1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью .
2. Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему - уменьшаем на .
3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

4. Возвращаемся на шаг 2.

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

Применение алгоритма решения  задачи

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

 

ЗАКЛЮЧЕНИЕ

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