Модификация алгоритма Флойда
Шаг
0. Пусть N =
{1, 2, …n}- множество узлов сети. На j-й
итерации работы алгоритма будем строить
матрицу длин
,
элемент которой
равен длине «узкого» места (i, j) – цепи,
промежуточными узлами в которой могут
быть лишь узлы из множества {1, 2,…, p}; и
справочную матрицу
,
каждый элемент
которой
указывает первый после узла i узел в
такой сети.
Алгоритм
начинает работу с матрицей
,
где
,
если меняется дуга из i в j (в противном
случае
),
и с матрицей
После построения матриц
и
для каждого p=1, 2, …, n, используя для
вычислений элементы матриц, полученных
на предыдущих итерациях, необходимо
выполнить следующую процедуру:
Шаг
1. Пусть
матрицы
и
найдены. Выделим элементы p-й строки и
p-го столбца матрицы
.
Назовем эти множества элементов базовой
строкой и базовым столбцом соответственно.
Шаг 2. Построим матрицы и , исходя из следующего правила: для
Если
,
то
и
.
Если , то и .
Шаг
3. Элемент
матрицы
равен «узкому» месту в цепи из узла i
в узел j.
Элемент
есть узел, стоящий после узла i в этой
цепи.
1.4 Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона
Определение Ориентированный граф G = (V, E) называется сетью, если в нем отмечены (выделены) некоторые вершины, называемые полюсами; при этом, множество полюсов разбито на два подмножества: вершины первого подмножества являются источниками, а второго — стоками. Остальные вершины называются внутренними.
В данном разделе рассматриваются только сети, где имеется один источник s (sourse) и один сток t (target).
Для
каждой вершины
выделим
два множества дуг:
E+(
ν) = {( ν, u)
E} выходящих
из ν,
и
E-( ν) = {( u, ν) E} входящих в ν
Пусть f: E R – некоторая функция на дугах.
Дивергенцией f в вершине ν называется число
Функция f: E R называется потоком в сети, если во всех внутренних вершинах выполнено равенство div f (ν) = 0.
Данное условие называется условием неразрывности. Оно означает (если интерпретировать f(e) как количество жидкости, протекающей по дуге в единицу времени), что для любой внутренней вершины ν количество жидкости, втекающей в эту вершину, равно количеству жидкости, вытекающей из нее.
Пример. Пусть задан граф G=(V, E), в котором пропущен допустимый поток f (рис.1.16).
Рис. 1.16
Числа c(x, y), f(x, y), стоящие над дугой (x, y) графа, показывают соответственно пропускную способность и пропущенный поток в этой дуге.
Очевидно, что, например, во внутренних вершинах сети a и b дивергенция равна нулю, т.е. выполняется условие неразрывности, или, по-другому, в сети задан поток.
Определение Мощностью потока называется число
M(f) = div f(s) = - div f(t).
M(f) интерпретируется как количество жидкости «создаваемое» источником и, соответственно, равное (в силу неразрывности) количеству жидкости «потребляемому» стоком. В приведенном примере мощность потока равна 4.
Пусть каждой дуге поставлено в соответствие некоторое число c(e) >=0, называемое пропускной способностью дуги. Поток f является допустимым, если выполняется условие:
0<= f(e)<= c(e) для любой дуги e E.
Т.к. в дуге (s, a) (рис. 4.1) пропускная способность равна двум единицам, то в ней задан допустимый поток, который также равен двум единицам.
Постановка задачи. Задана сеть с фиксированными пропускными способностями дуг. Найти среди допустимых потоков поток максимальной мощности.
В связи с излагаемым ниже алгоритмом решения этой задачи, потребуется рассмотреть еще ряд объектов, ассоциированных с сетями и потоками.
Пусть
—
некоторое подмножество вершин,
удовлетворяющих условию
Пара
(X, X*),
где X* = V \ X
называется разрезом, отделяющим вершину
s
от вершины
t.
Для разреза (X, X*) введем множество
E+(X, X*) = {e(u, ν) E: u X, ν X*}
дуг, идущих из X в X*.
Определение Пропускной способностью разреза (X, X*) называется число
В приведенном выше примере, рассмотрим, например, разрез (X, X*) с множествами X={s, a} и X*={b, t}. Видим, что его мощность равна
C(X, X*) = c(s, b)+c(a, b) +с(a, t)=3+1+4=8.
Теорема (Ford-Fulkerson). (Необходимое условие максимального потока). Если f – допустимый поток максимальной мощности, то существует разрез (X, X*), такой что
M(f)=C(X, X*).
Пусть st – некоторый путь (без учета ориентации), т.е. последовательность вершин s = ν0, ν1,…, νk = t такая, что для любого i=0,…,k-1 либо (νi, νi+1) E либо (νi+1, νi) E. Если для рассматриваемого пути выполняется (νi, νi+1) E, то дуга (νi, νi+1) называется прямой дугой; если же (νi+1, νi) E, то дуга (νi+1, νi) называется обратной.
Например, на рис. 4.2 показаны, какие дуги являются прямыми, а какие обратными.
Дуги
(s, ν1), (ν3, ν4), (ν4, t) – прямые, а дуги (ν2,
ν1), и (ν3, ν2) - обратные. Пусть f – некоторый
допустимый поток. Тогда путь s
t является увеличивающим для f, если на
каждой прямой дуге e:f(e)<c(e), а на каждой
обратной дуге e:f(e)>c(e).Для такого пути
вычисляют для прямых дуг
по формуле:
,
а для обратных дуг —
:
.
Затем вычисляют
.
Очевидно,
что изменяя исходный поток f (вдоль пути
s
t) на прямых дугах на величину (+
)
и на обратных дугах на величину (-
)
получается новый допустимый поток f,
для которого
В заданной сети построен максимальный поток тогда и только тогда, когда не существует ни одного увеличивающего пути.