Глава 11. ПОТОКИ В СЕТЯХ
1. Введение
Одной из наиболее интересных и важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины 
графа (источника) к некоторой конечной вершине 
(стоку). При этом каждой дуге 
графа 
приписана некоторая пропускная способность 
и эта пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге. Эта задача и ее варианты могут возникать во многих практических приложениях, например при определении максимальной интенсивности транспортного потока между двумя пунктами на карте дорог, представляемой графом. В этом примере решение задачи о максимальном потоке укажет также ту часть сети дорог, которая «насыщена» и образует «узкое место» в отношении потока между двумя указанными концевыми пунктами.
Метод решения задачи о максимальном потоке (от 
) был предложен Фордом и Фалкерсоном [12], и их «техника пометок» составляет основу других алгоритмов решения многочисленных задач, являющихся простыми обобщениями или расширениями указанной задачи. Следующие возможные варианты задачи о максимальном потоке (от 
) встречаются в литературе.
(I) Допустим, что каждой дуге графа приписана не только пропускная способность 
дающая верхнюю границу потока через дугу 
но также «пропускная способность» 
дающая нижнюю границу потока через дугу. В таком случае далеко не очевидно, что существует допустимое множество потоков, удовлетворяющих требованиям о максимальной и минимальной пропускных способностях дуг. Однако если (в общем случае) существует много таких потоков и если в дополнение к пропускным способностям заданы также стоимости единицы потока, протекающего по дуге, то возникает задача нахождения допустимого потока минимальной стоимости (от вершины 
к вершине 
Рассмотрим случай, когда ищутся максимальные потоки между каждой парой вершин. Хотя такая задача может быть решена как 
«отдельных» (от 
) задач, но это очень трудоемкий процесс. При нахождении кратчайших цепей между каждой парой вершин графа было установлено, что нет необходимости решать каждую (от 
) задачу о кратчайшей цепи индивидуально
(см. гл. 8), и в настоящей задаче точно так же существует метод, который — для неориентированных графов — не предполагает обязательного решения задач о максимальных потоках для каждой пары вершин 
Если вместо одного источника и одного стока рассмотреть несколько заданных источников и стоков, причем между различными источниками и стоками протекают потоки различных продуктов, то задача максимизации суммы всех потоков между источниками и стоками называется задачей о многопродуктовом потоке. В этой задаче пропускная способность 
дуги 
является ограничением для суммы всех потоков всех видов продуктов через эту дугу.
(IV) Во всех рассмотренных выше случаях неявно допускалось, что поток на входе дуги такой же, как и на выходе. Если отказаться от этого допущения и рассмотреть граф, в котором выходной поток дуги равен ее входному потоку, умноженному на некоторое неотрицательное число, то задачу о максимальном потоке (от 
называют задачей о потоках с выигрышами. В такой задаче потоки могут и «порождаться», и «поглощаться» самим графом, так что поток, входящий в 
и поток, покидающий 
могут изменяться совершенно независимо.
Область теории графов, в которой рассматриваются вопросы о потоках в графах, интенсивно развивалась в большом числе работ. В настоящей главе дается обзор общих проблем, устанавливается связь между ними и приводится описание некоторых важных алгоритмов, используемых при решении задач о потоках. Последнее необходимо, во-первых, из-за собственной значимости этих алгоритмов, во-вторых, потому, что они позволяют вскрыть такие связи между задачами, которые не очевидны с других точек зрения, и, в-третьих, потому, что алгоритмы, которые будут описаны, могут быть использованы (непосредственно или как элементарные части более сложных алгоритмов) для анализа широкого круга других задач.
В зтой главе мы обсудим основную задачу о максимальном потоке (от 
и ее обобщения (I), (III) и (IV). Так как алгоритмы для многопродуктового потока имеют совсем другую природу и совсем не так эффективны, как метод пометок, обсуждаемый в зтой главе, то мы не будем заниматься здесь зтой задачей и отсылаем заинтересованного читателя к [18, 27, 26, 25, 24, 15].
