Теория графов 2 (стр. 4 из 5)
Величиной потока
в транспортной сети D называется величина 
, равная сумме потоков по всем дугам, заходящим в 
, или, что то же самое – величина, равная сумме потоков по всем дугам, исходящим из 
Пусть
- допустимый поток в транспортной сети D. Дуга 
называется насыщенной, если поток по ней равен её пропускной способности, т.е. если 
. Поток называется полным, если любой путь в D из 
содержит, по крайней мере, одну насыщенную дугу.Поток
называется максимальным, если его величина 
принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.Очевидно, что максимальный поток
обязательно является полным (т.к. в противном случае в D существует некоторая простая цепь 
из V1 в Vn, не содержащая насыщенных дуг, а следовательно, можно увеличить на единицу потоки по всем дугам из и тем самым увеличить на единицу , что противоречит условию максимальности потока). Обратная же, вообще говоря, неверно. Существуют полные потоки, не являющиеся максимальными. Тем на менее полный поток можно рассматривать как некоторое приближение к максимальному потоку.Введем для заданной транспортной сети D и допустимого потока
в этой сети орграф приращений 
, имеющий те же вершины, что и сеть D. Каждой дуге 
транспортной сети D в орграфе приращений 
соответствует две дуги: 
и 
- дуга, противоположная по направлению дуге . Припишем дугам 
орграфа приращений длину 
: 
т.е. орграф
является нагруженным. При этом очевидно, что длина любого пути из 
в 
в орграфе равна либо 0, либо бесконечности.Важным следствием теоремы Форда-Фалкерсона является Алгоритм построения максимального потока в транспортной сети.
Алгоритм:
Шаг 1. Полагаем i=0. Пусть
- любой допустимый поток в транспортной сети D (например, полный, можно начинать с нулевого потока: 
).Шаг 2. По сети D и потоку
строим орграф приращений 
.Шаг 3. Находим простую цепь
, являющуюся минимальным путем из 
в в нагруженном орграфе 
. Если длина этой цепи равна бесконечности, то поток максимален, и работа алгоритма закончена. В противном случае увеличиваем поток ввдоль цепи на максимально допустимую величину 
, такую, что при этом сохраняется условие 1 допустимого потока (для любой дуги величина 
, называемая потоком по дуге х, удовлетворяет условию 
). В силу 
, используя 
и 
, получаем, что указанная величина 
существует. В результате меняется поток в транспортной сети D, т.е. от потока мы перешли к потоку 
, и при этом 
. Присваеваем 
и переходим к шагу 2.2 Практическая часть
2.1 Задача о нефтепроводе максимальной пропускной способности.
На практике часто возникают задачи определения максимального количества нефти, которое может быть доставлено по трубопроводу за какое-то время. Аналогичными являются задачи определения максимальной пропускной способности системы автомагистралей или энергосети. Формально эти проблемы сводятся к задачи построения максимального потока в сети. Мы же конкретней остановимся на задачи определения максимальной пропускной способности нефтепровода.
Пусть требуется построить увеличивающую цепь для сети S= (N,U), представленной на рисунке 8.
Рисунок 8 – Построение увеличивающей сети
Над каждой дугой указана ее пропускная способность и в скобках - величина потока по этой дуге.
Цепь (s,1,2,3,4,t) является увеличивающей, так как все ее дуги – допустимые:
1) дуга (s,1) – увеличивающая, так как она проходит по направлению потока и поток по ней меньше ее пропускной способности: 6<9;
2) дуга (1,2) – также увеличивающая дуга: 3<6;
3) дуга (2,4) – уменьшающая, так как она проходит против движения потока и поток по ней 2>0;
4) дуга (4,t) – увеличивающая: 4<7;
Построим увеличивающую цепь для сети, представленной на рисунке 9.
Рисунок 9 – Построение увеличивающей сети
Цепь (s,3,2,t) – увеличивающая, так как все ее дуги являются допустимыми увеличивающими дугами.
Определение максимального потока основано на увеличении вдоль увеличивающей цепи на величину
.Алгоритм построения максимального потока включает в себя следующую последовательность: