К задаче о максимальном потоке сводятся многие важные оптимизационные задачи, например: задача об оптимальном назначении; различные задачи организации снабжения; задачи строительства энергетических сетей, нефте- и газопроводов, железных и шоссейных дорог и много других прикладных задач. В таких задачах схема доставки груза, или схема сообщения, представляется в виде графа, по ребрам которого проходят заданные потоки. Основным в теории потоков является понятие сети.
Сеть — это взвешенный граф без циклов и петель, ориентированный в одном направлении от вершины, называемой источником, к вершине, называемой стоком.
На рис. 1.8 представлена сеть. Истоком I является вершина 1, стоком S –вершина 6. Представим, что по ребрам (i,j) сети направляется некоторое вещество (ресурс, информация и т.п.). В скобках указаны пропускные способности ребер. Первое число- это пропускная способность в прямом направлении (от вершины i к вершине j) и второе – в противоположном направлении.
Пропускная способность - максимальное количество вещества rBijB, которое можно пропустить по ребру (i,j). Количество xBij Bвещества, проходящего по ребру (i,j) в единицу времени, называется потоком по ребру. Считается, что если есть поток из вершины i в вершину j, то
xBijB = - xBji B (1.1)
Если поток по ребру (i,j) меньше его пропускной способности, т.е. xBij B< rBijB, то ребро называют ненасыщенным, если xBij B= rBijB, - насыщенным. Совокупность X = {xBijB} потоков по всем ребрам называют потоком по сети или просто потоком.
Поток по ребру не может превысить его пропускной способности, т.е.
(1.2)
где n – количество вершин сети.
Приведем основное положение в теории потоков, которое называют условием сохранения потока: для любой вершины, кроме истока I и стока S, количество поступающего вещества в эту вершину, равно количеству вещества, вытекающего из нее. В промежуточных вершинах потоки не создаются и не исчезают.
Математическая запись этого ограничения с учетом формулы (1.1) следующая:
(1.3)
Отсюда вытекает, что общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.
(1.4)
где j – конечные вершины ребер, исходящих из I;
i – начальные вершины ребер, входящих в S.
Линейную функцию f называют мощностью потока на сети. Сформулируем задачу о максимальном потоке: найти множество XP* P= {xBijPB*P} потоков xBijPB *P по всем ребрам (i,j) сети, которое удовлетворяет условиям (1.1) - (1.3) и доставляет линейной функции (1.4) максимальное значение.
Как видно из формулировки, это типичная задача линейного программирования.
Обратимся к рис. 1.8, где изображена сеть. Для этой сети пропускную способность представим в виде матрицы, используя цифры в скобках. Здесь n = 6 и числа образуют квадратную матрицу шестого порядка (табл. 1.1). Если вершины k и l не соединены, то rBkl B= rB lkB = 0. Сформировать матрицу чисел xBijB – это значит задать поток на сети, т.е. найти nP2 Pчисел, удовлетворяющих условиям (1.1) – (1.3). Рассмотрим полный путь 1 – 2 – 5 – 6.
Пропускная способность этого пути не больше 1 ед. и ограничивается ребром (2, 5), которое лежит на этом пути. Поток по этому пути мощностью в 1 ед. будет допустимым, и условии (1.1) – (1.3) должны выполняться для всех вершин и ребер этого пути.
Таблица 1.1
| i/j | ||||||
Рис. 1.8
Например, возьмем вершину 2 и проверим условие (1.3):
xB21B + xB25B = (-xB21B) + xB25B = (-1) + 1 = 0.
Разрез на сети
Представим некоторую сеть. Разобьем множество вершин сети на два непересекающихся подмножества A и B так, чтобы исток I попал в подмножество A, а сток S попал в подмножество B. В результате такого разбиения появляются ребра (i, j), конечные точки которых оказываются в разных подмножествах.
Совокупность ребер (i, j), начальные точки которых принадлежат подмножеству A, а конечные точки – подмножеству B, называют разрезом сети и обозначают A/B.
На рис. 1.9 изображена некоторая сеть. Стрелки указывают положительное направление потока. На сети произведено два разреза: I и II. При разрезе I образовалось два подмножества вершин сети: подмножество A = {1, 2} и B = {3, 4, 5}, а ребрами, образующим разрез, стали (1, 3), (1, 4), (2, 4). При разрезе II образовались подмножества A = {1, 2, 3, 4} и B = {5} с образующими разрез ребрами (3, 5) и (4, 5).
Рис. 1.9
Величина 
, представляющая сумму пропускных способностей всех ребер разреза, называется пропускной способностью разреза.
Если на сети задан поток X = {xBijB} и разрез (A/B), то величина 
, представляющая сумму потоков по всем ребрам разреза, называется потоком через разрез.
Для разреза I R(I) = rB13B + rB14 B+ rB24B = 6 + 2 + 1 = 9. X(I) = xB13B + xB14B + xB24B = 4 + 2 + 0 = 6. Для разреза II – R(II) = 9, X(II) = 6.
В общем случае, если на сети задан поток X = {xij} и произведен разрез (A/B), то хотя бы одно ребро любого полного пути, идущего из истока в сток, будет обязательно принадлежать разрезу (A/B). Напомним, что величина потока по любому полному пути не превышает пропускную способность каждого его ребра, а потому величина X суммарного потока, стремящегося из истока в сток, не может повысить пропускную способность любого разреза сети, т.е.
(1.5)
В теории потоков утверждается, что если удастся построить на сети поток XP* P= {xBijPB*P}, величина которого равна пропускной способности некоторого разреза (A/B), то этот поток будет максимальным, а разрез обладать минимальной пропускной способностью. Ниже приводится теорема о максимальном потоке, имеющая большое прикладное значение.
Теорема Форда - Фалкерсона. На любой сети сети максимльная величина потока из истока I в исток S равна максимальной пропускной способности разреза, отделяющего I от S.