Потоковые алгоритмы
Поток определяет способ пересылки некоторых объектов из одного пункта в другой. Потоки, например, возникают при транспортировке готовой продукции от завода до распределительного склада, при движении людей от мест проживания к местам работы или при доставке писем от отправителя к получателю, и т. д. Несмотря на разнообразие ситуаций, связанных с потоками, в них возникает целый ряд достаточно общих проблем. Примерами таких проблем могли бы служить: максимизация суммарного объёма перевозки в некоторой системе из одной точки в другую, минимизация стоимости пересылки через некоторую систему определённого количества предметов из одной точки в другую, минимизация времени перевозок в заданной системе.
Применительно к графам поток задаёт способ пересылки некоторых объектов из одной вершины графа в другую по его дугам.
Вершина, из которой начинается перемещение объектов, называется источником и обозначается буквой s.
Вершина, в которой заканчивается перемещение объектов, называется стоком и обозначается буквой t.
Объекты, которые перемещаются из источника в сток, будут называться единицами потока. Если количество единиц потока по дуге (x, y) ограничено, то говорят, что дуга
(x,y)
имеет ограниченную пропускную способность.
Максимальную величину пропускной
способности будем обозначать через
c(x,
y). Через a(x,
y) будем обозначать
стоимость перемещения единицы потока
по дуге (x, y).
Количество единиц потока, проходящих
по дуге (x, y),
называется потоком в данной дуге и
обозначается f(x,
y). Очевидно, что
.
Дуги графа можно отнести к трём различным категориям:
Дуги, в которых поток не может ни увеличиваться, ни уменьшаться. Множество таких дуг обозначается N.
Дуги, в которых поток может увеличиваться. Множество таких дуг обозначается I.
Дуги, в которых поток может уменьшаться. Множество таких дуг обозначается R.
Возможно существование дуг, которые могут принадлежать как множеству I, так и множеству R. Такие дуги называются промежуточными.
Обозначим через i(x, y) максимальную величину, на которую может быть увеличен поток в дуге (x, y). Соответственно, обозначим через r(x, y) максимальную величину, на которую может быть уменьшен поток в дуге (x, y). Очевидно, что:
.
Пусть необходимо переслать дополнительное количество единиц потока из источника в сток. Имеется несколько способов выполнения этой задачи:
1-ый способ мог бы быть реализован, если бы мы нашли путь из вершины s в вершину t, состоящий только из увеличивающих дуг.
Сколько в этом случае можно переслать единиц потока из вершины s в вершину t по найденному пути?
Поскольку i(x,
y) представляет
собой максимально возможное увеличение
потока в дуге (x, y),
то величина дополнительного потока из
вершины s в вершину t
составит самое большое
.
Пример:
Рис. 59
Т. е. максимально на единицу мы можем увеличить данный поток.
2-ой способ увеличения потока мог бы быть реализован, если бы мы нашли путь Р из вершины t в вершину s, состоящий только из уменьшающих дуг, при этом можно было уменьшить поток в каждой дуге (x, y), что привело бы к уменьшению потока из вершины t в вершину s и, следовательно, увеличению чистого потока из вершины s в вершину t.
На какую максимальную величину можно было бы уменьшить поток из вершины t в вершину s по указанному пути?
Поскольку каждой дуге (x,
y) пути Р поток
можно уменьшить самое большое на величину
r(x,
y), то максимальное
уменьшение потока вдоль пути Р
определяется величиной
.
Пример:
Рис. 60
Т. е. из вершины s в вершину s можем уменьшить поток максимально на 1, значит, по пути из вершины s в вершину s можно переслать на одну единицу потока больше.
Для увеличения чистого потока из вершины s в вершину t можно скомбинировать два способа, описанных выше. Это означает, что необходимо найти путь, соединяющий вершину s и вершину t, дуги которого удовлетворяют следующему условию:
Все прямые дуги-пути, т. е. дуги, имеющие направления от s к t, принадлежат множеству I;
Все обратные дуги-пути, имеющие направление от t к s, принадлежат множеству R.
На примере рассмотрим путь:
Рис. 61
Вдоль приведенного пути можно переслать дополнительный поток из вершины s в вершину t путём увеличения потока в прямых дугах, которые являются увеличивающими, и уменьшения потока в обратных дугах, которые являются уменьшающими.
Максимальная величина дополнительного потока, который можно переслать вдоль пути из вершины s в вершину t, определяется как минимум из следующих двух величин:
.
В данном примере:
Каждый путь из вершины s в вершину t любого из трёх рассмотренных типов, по которому могут быть дополнительно посланы единицы потока, называется увеличивающим путём.