7.8. Максимальные потоки в сетях общего вида с ограниченными пропускными способностями дуг

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

Однако, если первоначальный допустимый поток не известен, то возникают трудности. Очевидно, что в этом случае (при поток, тождественно равный нулю, не является допустимым.

Для нахождения начального допустимого потока сформулируем вспомогательную задачу на вспомогательной сети (см. [5] библ. к гл. 1). Сеть

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

Каждой дуге в множестве А соответствуют три дуги

Этим дугам приписываются следующие пропускные способности:

Заметим, что для дуг, у которых построение дуг и является излишним, так как для них На практике эти дуги опускаются. В теории, однако, удобно считать, что все три дуги и всегда существуют.

Кроме названных дуг в добавляется еще одна конечная дуга имеющая следующие характеристики:

где К — целое число, большее чем величина любого возможного допустимого потока в первоначальной сети На рис. 7.10 приведен пример, иллюстрирующий вспомогательную сеть для заданной сети

Замечание. Вспомогательная сеть полностью определяется сетью и ее функциями ограничений Если -сложная сеть, то явное построение оказывается в лучшем случае трудным делом. Однако для построения вспомогательной сети и реализации вычислительного алгоритма можно с успехом использовать электронные цифровые вычислительные машины.

Упражнение 7.9. (см. скан)

Вспомогательная сеть представляет интерес по двум причинам. Во-первых, транспортная сеть, а для

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

Рис. 7.10,

Отсутствие допустимого потока также легко устанавливается по характеристикам потока

Допустимый поток в сети называется насыщающим потоком, если для каждой дуги идущей из Такой поток (если он существует) с необходимостью является максимальным в (почему?). Эквивалентным условием насыщающего потока является равенство для каждой дуги, оканчивающейся в Если — насыщающий поток в то рассмотрим следующую функцию определенную на дугах сети Для определенной таким образом доказывается следующая

Теорема 7.6. Если — насыщающий поток в сети определено так, как показано выше, то есть допустимый поток из сети Более того, величина равна

Упражнение 7.10. (см. скан)

Таким образом, если, максимизируя поток в сети мы получим насыщающий поток, то из него легко можно получить допустимый поток в сети С другой стороны, если максимальный поток в не является насыщающим, то, как утверждается теоремой 7.7, допустимого потока в сети не существует.

Теорема 7.7. Если максимальный, но не насыщенный поток в сети из то в сети не существует допустимого потока из

Доказательство. Обозначим через множество вершин, отличных от но достижимых из путями конечной длины в графе И пусть обозначает вершины, не достижимые из и отличные от Так как ненасыщающий поток, оба множества непусты. (Проверьте это.) Пропускная способность (т. е. сумма верхних границ потока) разреза определенного разбиением V на задается выражением

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

Так как ненасыщающий поток, имеем

Сопоставляя два последних выражения, находим, что

Отсюда следует, что для любого допустимого потока в сети мы должны иметь

С другой стороны, если обе принадлежат

или то любой поток из должен удовлетворять соотношению

Если же и то должен удовлетворять соотношению

где через обозначена величина потока Отсюда мы заключаем, что в сети не существует допустимого потока из в исключая, возможно, не рассмотренный здесь случай, когда и Но этот случай никогда не возникает, так как если мы можем достигнуть через ненасыщенный путь в сети то мы можем так же достичь так как дуга никогда не бывает насыщенной. Теорема доказана.

Упражнение 7.11. (см. скан)

Краткие выводы. Итак, мы получили следующие основные результаты. Мы можем найти максимальный в транспортной сети, принимая в качестве начального поток, тождественно равный нулю, и добавляя к нему последовательность простых потоков по цепям источника к стоку. Текущее значение потока максимально, когда в графе приращений не оказывается путей конечной длины, соединяющих с Каждый промежуточный поток, найденный в процессе выполнения процедуры, является допустимым, так что фактически мы получаем потоки, реализующие все допустимые значения, Более того, мы можем ускорить процедуру поиска, выбирая подходящий множитель для каждого потока по цепи. Для сетей общего вида с ограниченными пропускными способностями, в которых для нескольких или всех дуг, необходимо сначала построить соответствующую вспомогательную транспортную сеть и максимизировать поток от с помошью указанного выше алгоритма. Найденный максимальный поток легко преобразуется в допустимый поток

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