1 Графы

1.1Основные характеристики графов

Граф G –это математический объект, состоящий из множествавершин X = {x₁,x₂,...,x_n} и множестваребер A={a₁,a₂,...,a_m}. Таким образом, граф полностью определяется совокупностью множествX,Aи обозначаетсяG(X, A).

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

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым. Граф G (X, A)–полный, если для любой пары вершинx_iиx_jсуществует ребро(x_i, x_j).

1.2 Пути и маршруты

Маршрутом илицепью в неориентированном графеG называется такая последовательность (конечная или бесконечная) реберa₁,a₂,...,a_n,…, что каждые соседние два ребраa_i иa_i+1имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a₁,a₂,...,a_n)имеется первое реброa₁и последнее реброa_n. Вершинаx₁, инцидентная ребруa₁, но не инцидентная ребруa₂, называется началом маршрута, а вершинаx_n, инцидентная ребруa_n, но не инцидентная ребру a_n-1, называется концом маршрута.

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

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

Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длинойпути.

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

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

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

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

2.1 Краткое описание алгоритма

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

Работа алгоритма продолжается до тех пор, пока удается находить данные пути.

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

Неформальное описание алгоритма:

• Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью;

• В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся;

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

• На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью ;

• Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему — уменьшаем на;

• Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его;

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

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

Более формально, мы имеем ориентированный граф G = (V; E), со множеством вершинVи множеством реберE. Во множествеVвыделены две вершины:s- источник иt- сток. При этом, у вершины s есть толькоходящие ребра, у вершиныtесть только входящие ребра.

Если ребро имеет максимальную пропускную способность x и потокy, то остаточной пропускной способностью ребра называется число xy. Смысл остаточной пропускной способности заключается в том, на сколько еще можно увеличить поток на данном ребре.

Рисунок 1 – Общая схема

Следующим этапом выполнения программы является нахождение маршрутов в графе. Поиск маршрутов реализуется с помощью алгоритма обхода графа в ширину. На рисунке 2 представлена блок-схема алгоритма обхода графа в ширину.

Алгоритм Форда-Фалекрсона работает пока можно найти хотя бы один путь из источника в сток, итеративно увеличивая поток на минимальную величину. На рисунке 3 представлена блок-схема алгоритма Форда-Фалкерсона.

Рисунок 2 – Блок-схема алгоритма поиска в ширину

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