Сеть. Потоки на сетях. Задача нахождения потока максимальной мощности. Алгоритм Форда-Фалкерсона

Сеть – конечный граф без циклов и петель, ориентированный в одном общем направлении от вершины S (исток графа) к вершине T (сток графа).

Будем представлять, что по ребрам (i,j) из S в T направляется некоторое вещество (груз, информация и прочее).

Максимальное количество вещества С_ij, которое может пропустить ребро (i,j) называется его прорускной способностью. Еесли вершины не соединены, то пропускная способность =0. Поток по ребру (i,j) – количество вещества F_ij, проходящего через ребро (i,j) в единицу времени.

Если из i в j направляется поток F_ij, то величина обратного потока равна -F_ij.

Если С=1, то дуга называется насыщенной.

Свойства потоков по ребрам:

1. Поток по каждому ребру не превышает его пропускной способности.

2. Количество вещества, притекающего в вершину равно количеству вещества, вытекающего из нее.

Общее количество вещества, исходящего из истока S совпадает с общим количеством вещества, поступающего в сток T.

Пусть Х некоторое подмножество вершин удовлетворяющих условию S принадл Х, Т не принадл Х. Пара (Х, Х*), где Х* = v/X – разрез, отделяющий S под Т.

Пропускной способностью разреза С(Х,Х*) называется сумма пропускных способностей дуг, составляющих этот разрез.

Дуги, которые идут от S к T(прямые) составляют разрез. Дуги от T к S(обратные) в разрез не входят.

Х=(S,a)

X*=(t,b)

C(X,X*)=С(S,B)+C(A,B)+C(A,T)

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

Задана сеть с фиксированными пропускными способностями дуг. Найти среди всех потоков поток максимальной мощности.

Теорема Форда-Фалкерсона

Мощность максимального потока, пропущенного в сети, равна минимальной пропускной способности разреза.

Шаг 0. В процессе работы алгоритма каждая вершина относиться к одному из 3-х множеств: не помеченные вершины, помеченные не просмотренные, просмотренные (окрашенные).

Шаг 1. Пометим вершину S меткой (S⁺; бесконечность), остальные не помечены.

Шаг 2. Пусть V некоторая помеченная, но не просмотренная вершина. Рассмотрим все соседние с ней не помеченные вершины. Для каждой из таких вершин U возможны следующие ситуации:

а) существует прямая дуга (V,U), f(V,U)<c(V,U), тогда U вершина получает пометку U(V⁺;С(V,U)-f(V,U))

б) существует обратная дуга (U,V), f(u,v) > 0. Тогда U получает пометку U(V^-;f(u,v))

в) существует прямая дуга (V,U) или существует обратная и поток равен 0, тогда вершина U не помечается.

Когда все соседние с V вершины проанализированы, V переходит в множество просмотренных вершин.

Шаг 3. Повторяем шаг 2 до тех пор пока не возникнет одна из следующих ситуаций:

а) все вершины графа разбиты на 2 подмножества(просмотренные и непомеченные(включая Т). Тогда в сети построен макс поток мощности V и мин разрез Х,Х*,

б) если вершина Т получила пометку, то в сети существует увеличивающий путь из S вT, который можно определить идя из Т обратно к S. Для найденного пути определяют величину е(эпсилон) увеличения мощности потока. На прямых дугах пути ST изменяем F на +е на обратных на –е. Мощность равна V предыдущая +е.

Дата добавления: 2015-10-13