Потоки в сетях (Максимальный поток в транспортной сети)

Граф - упорядоченная пара G =<V;E>, где V - непустое конечное множество (элементы V- вершины графа); E- конечное мультимножество неупорядоченных пар элементов V необязательно различных) (элементы E- ребра).

Ориентированный граф - упорядоченная пара G = <V;A>, где V - непустое конечное множество - множество вершин; A- конечное мультимножество упорядоченных пар элементов V (необязательно различных) - мультимножество дуг.

Петля в орграфе - дуга вида (u; u). Пусть G = <V;A> - орграф без петель, имеющий единственный источник (будем обозначать его v1) и единственный сток (vn). Все остальные вершины графа будем называть промежуточными. Если каждой дуге графа a из A поставлено в соответствие неотрицательное целое число c(a) (пропускная способность дуги), то говорят, что задана транспортная сеть (или просто: сеть) <G; c>.

Функция  (определенная на мультимножество дуг орграфа и принимающая неотрицательные целые значения) называется потоком в сети <G; c>, если выполняются следующие условия:

1) для любой дуги a из A ;

2) для любой промежуточной вершины графа v .

Величину j(a) будем называть потоком по дуге a.

Таким образом,

- поток по каждой дуге не должен превышать ее пропускной способности;

- сумма потоков по дугам, заходящим в произвольную промежуточную вершину, равен сумме потоков по дугам, исходящим из этой вершины. Другими словами, поток не возникает и не накапливается в промежуточных вершинах.

Данная математическая модель описывает поведение газа или жидкости в трубопроводе, транспортные потоки в сети дорог, пересылку товаров на рынок по различным каналам и т.д.

Величиной потока W(') назовем сумму потоков по дугам, исходящим из источника:

Поток в транспортной сети, имеющий наибольшую возможную величину, называют максимальным потоком. В одной и той же сети может быть несколько максимальных потоков (их величины, разумеется, должны совпадать).

Пусть j - поток в сети <G; c>. Дуга a из A называется насыщенной, если поток по ней равен ее пропускной способности: j(a) = c(a): Поток j называется полным, если любой путь в орграфе G из v1 в vn содержит по меньшей мере одну насыщенную дугу. Очевидно, что всякий максимальный поток является полным.

В дальнейшем будем считать, что орграф G = <V;A> - антисимметрический, т.е. он не содержит кратных дуг и если (u; v) из A, то (v; u) не из A. Это предположение не является сильно ограничительным, поскольку подразбиением дуг (введением дополнительных фиктивных вершин) всегда можно по данной сети построить сеть с антисимметрическим орграфом и той же величиной потока. Максимальный поток можно найти с помощью следующего алгоритма.