Алгоритм Форда – построения максимального потока в сети.

Начальный. Выбираем некоторый поток в сети G (V,U) (например x_{i j}= 0 для всех дуг (i,j)Î U).

Общая итерация 1. Применяем алгоритм нахождения увеличивающего пути из источника s в сток t. Если такого пути нет, то построенный поток яв­ляется максимальным. Алгоритм заканчивает работу. Если увеличивающий путь найден, то переходим к 2.

2. В найденном увеличивающем пути обозначим через P⁺ множество прямых, а P ^- - множество обратных дуг пути и вычисляем величину ₁ = (d_ij – x_ij) > 0 и _{2 =} . Полагаем q = min ( ₁, ₂). Увеличиваем поток вдоль пути P на величину , полагая

x_ij^’ = x_ij+ , если (i,j) Î P⁺

x_ij^’ = x_ij – , если (i, j) Î P^- (23)

x_ij^’ = x_ij для остальных дуг пути.

Переходим к 1.

Рассмотрим пример. На рис.1. изображена сеть. Первое число в скобках указывает пропускную способность дуги, второе – дуговой поток.

Рис.1.

Найдем увеличивающий путь.

Общая итерация: Шаг 1. Источник s получает пометку (s⁺).

Шаг 2. Так как = 1< = 2, то вершина 1 получает метку (s⁺). Вер­шина 2 получает метку (s^-), т.к. x₂₁ = 1 > 0. Вершина 5 не может быть помечена, т.к. (дуга (s, 5) – насыщенная).

Шаг 3. Соседними вершинами с вновь помеченными являются вершины 3 и 4. Вершина 3 помечена не может быть, так как x₁₃ = d₁₃.. Вершина 4 получает пометку (2^-), т.к. х₄₂ = 1 > 0.

Шаг 4. Соседними с помеченной вершиной 4 являются вершины t и 5. Вершина t помечена не может быть, т.к. х_t4 = 0. Вершина 5 получает пометку (4 ^-), т.к. x₅₄=1>0.

Шаг 5. Помечаем вершину t с меткой (5 ⁺), x₅₁=1 < d₅₁=3.

Увеличивающий путь: s – 2 – 4 – 5 - t, причем на этом пути дуга (5, t) является прямой, а дуги (2, s); (4, 2); (5, 4) обратными.

Увеличим поток вдоль этого пути по формулам (23).

Находим

e ₁

e ₂ =

т.е. e = min(e ₁,e ₂) = 1.

Полагаем

_2S = x_2S – 1 = 0, ₄₂ = x₄₂ –1 =0, ₅₄ = x₅₄ – 1 = 0, _5t = x_{5 t}+1 = 2.

Величина суммарного потока в сети равна 3.

Общая итерация 1. Для нового потока ищем увеличивающий путь мето­дом расстановки пометок. Пометить удается только вершины s и 1. Следова­тельно, увеличивающего пути нет, и построенный поток является максималь­ным. Минимальный разрез (R,, , где R = {1; 2}, = {2; 3; 4; 5; t} состоит из дуг (R, ) = {(1, 3); (s, 5); (s,2); (1,2)} и обладает пропускной способностью

C (R, ) = d₁₃ + d_S5 = 3.

На рис.2 минимальный разрез показан пунктирной линией

Рис. 2

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 6. Сеть задана матрицей пропускных способ­ностей дуг (d_ij = 0 означает, что в сети отсутствует дуга, ведущая из вершины 1 в вершину j). Требуется по матрице D построить сеть и найти в ней максимальный поток из вершины 1 в вершину 10, опреде­лив при этом минимальный разрез.

Вариант 1	Вариант 2
Вариант 3	Вариант 4
Вариант 5	Вариант 6

Вариант 7	Вариант 8
Вариант 9	Вариант 10

Дата добавления: 2017-02-01