1. Понятие увеличивающая дуга, цепь, разрез

Рассмотрим данные понятия на примере:

Разрезом L сети S(N, U) называется множество насыщенных дуг, отделяющих источник s от стока t.

Пусть задана сеть S=(N, U) с множеством вершин N и множеством дуг U.

Определение: дуга u є U, соединяющая вершины i є N, j є N сети S, называется допустимой дугой, если она обладает одним из следующих свойств:

1. направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше ее пропускной способности:

u=(i, j), (u)<c(u) (1)

2. направление дуги противоположного направлению потока, и величина потока отлична от нуля:

u=(j, i), (u)>0 (2)

Дуги, обладающие первым свойством, называют увеличивающими; дуги, обладающие вторым свойством, – уменьшающими.

Увеличивающей цепью, соединяющей вход и выход сети, называется простая цепь, все дуги которой являются допустимыми.

Пример 1: построим увеличивающую цепь для сети S=(N, U), представленной на рисунке 10.

Рисунок 10 – увеличивающая цепь

Над каждой дугой указана ее пропускная способность, в скобках – поток по этой дуге.

Цепь (s, 1, 2, 4, t) является увеличивающей, так как все дуги – допустимые:

• дуга (s, 1) – увеличивающая, так как она проходит по направлению потока, и поток по ней меньше ее пропускной способности:

5 < 10;

• дуга (1,2) – также увеличивающая дуга: 12 < 15;

• дуга (2,4) – уменьшающая, так как она проходит против потока и поток по ней 3 > 0;

• дуга (4, t) – увеличивающая: 1 < 4.

3. Алгоритм Флойда-Уоршелл

Алгоритм Флойда является одним из методов поиска кратчайших путей в графе. В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе.

Прежде чем представлять алгоритмы, необходимо ввести некоторые обозначения. Перенумеруем вершины исходного графа целыми числами от 1 до N. Обозначим через d_i,j^m длину кратчайшего пути из вершинм i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа. (Напомним, что промежуточной вершиной пути является любая принадлежащая ему вершина, не совпадающая с его начальной или конечной вершинами.) Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что d_i,j^m=∞. Из данного определения величин d_i,j^m следует, что величина d_i,j⁰, представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе). для любой вершины i положим d_i,i^m= 0. Отметим далее, что величина d_i,j^mпредставляет длину кратчайшего пути между вершинами i и j.

Обозначим через D^m матрицу размера NxN, элемент (i, j) которой совпадает с d_i,j^m. Если в исходном графе нам известна длина каждой дуги, то мы можем сформировать матрицу D⁰. Наша цель состоит в определении матрицы D^N, представляющей кратчайшие пути между всеми вершинами рассматриваемого графа.

В алгоритме Флойда в качестве исходной выступает матрица D⁰. Вначале из этой матрицы вычисляется матрица D¹. Затем по матрице D¹ вычисляется матрицав D² и т. д. Процесс повторяется до тех пор, пока по матрице D^N-1 не будет вычислена матрица D^N.

Рассмотрим основную идею, лежащую в основе алгоритма Флойда. Суть алгоритма Флойда заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если он будет проходить через некоторую промежуточную вершину m. Предположим, что нам известны:

1. кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;

2. кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;

3. кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин.

Поскольку по предположению исходный граф не может содержать контуров отрицательной длины, один из двух путей — путь, совпадающий с представленным в пункте 3, или путь, являющийся объединением путей из пунктов 1 и 2 — должен быть кратчайшим путем из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых m вершин. Таким образом,

d_i,j^m=min{ d_i,m^m-1+ d_m,j^m-1; d_i,j^m-1}, (3)

где d_i,j^m – элемент матрицы D^m, d_i,j^m-1 – элементы матрицы D^m-1 найденой на предыдущем шаге алгоритма.

Из соотношения видно, что для вычисления элементов матрицы D^m необходимо располагать лишь элементами матрицы D^m-1. Более того, соответствующие вычисления могут быть проведены без обращения к исходному графу. Теперь мм в состоянии датьформальное описание алгоритма Флойда для нахождения на графе кратчайших путей между всеми парами вершин.

Алгоритм:

1. перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D⁰, каждый элемент d_i,j  которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ∞. Кроме того, положить значения диагонального элемента d_i,iравным 0;

2. для целого m, последовательно принимающего значения 1...N определить по элементам матрицы D^m-1элементы D^m;

3. алгоритм заканчивается получением матрицы всех кратчайших путей D^N, N – число вершин графа. Для определения по известным элементам матрицы D^m-1 элементов матрицы D^m в алгоритме Флойда применяется рекурсивное соотношение указанное в формуле (3).