Глава 22, Потоки в сетях. как единого целого: мы покажем при доказательстве свойства 22.1, что объем нефти, по­ступающей в сток

как единого целого: мы покажем при доказательстве свойства 22.1, что объем нефти, по­ступающей в сток, равен объему нефти, вытекающей из истока (в некоторых публикациях используется термин источник — прим. перев.). Более того, как следует из рис. 22.6, на­стройки вентилей, установленных на пересечениях, при таких объемах потоков из исто­ка в сток оказывают нетривиальное влияние на поток через сеть. В свете указанных фак­тов мы заинтересованы в получении ответа на следующий вопрос: какие настройки вентилей обеспечат максимальный объем потоков нефти из истока в сток?

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

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

Модель потоков применяется непосредственно к сценарию распределения: мы интер­претируем размеры потоков как их интенсивность, так что транспортная сеть описыва­ет потоки товаров точно так же, как и потоки нефти. Например, мы можем интерпре­тировать поток, представленный на рис. 22.5, как факт, определяющий необходимость переправки двух элементов в единицу времени из вершины 0 в 1 и из 0 в 2, одного эле­мента в единицу времени из 0 в 2, одного элемента в единицу времени из 1 в 3 и из 1 в 4 и т.д.

Другая интерпретация модели потоков для сценария распределения заключается в том, что потоки интерпретируются как объемы поставляемых товаров с той характерной осо­бенностью, что сеть описывает только одноразовую поставку товара. Например, мы мо­жем интерпретировать поток, представленный на рис. 22.5, как поставку четырех единиц товара из вершины 0 в 5 в рамках следующего трехэтапного процесса: сначала пересы­лаются две единицы товара из 0 в 1 и две единицы из 0 в 2, так что в каждой из этих вер­шин оседают по две единицы товара. Далее производится пересылка по одной единице товара из 1 в 3, из 1 в 4, из 2 в 3 и из 2 в 4, при этом в каждой из вершин 3 и 4 остает­ся по две единицы товара. И, наконец, пересылка завершается доставкой двух единиц товара из вершины 3 в 5 и из 4 в 5.

Как и в случае использования расстояния в алгоритмах поиска кратчайшего пути, мы вполне можем, когда это удобно, отказаться от любой физической интерпретации, по­скольку все рассматриваемые нами определения, свойства и алгоритмы основаны исклю­чительно на абстрактной модели, которая не обязательно подчиняется физическим зако-

Часть 5. Алгоритмы на графах

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

Определение 22.1. Будем называть сеть с верши­ной s, выбранной в качестве истока, и с вершиной t, выбранной в качестве стока, st-сетью.

В этом определении мы используем понятие " выбранный", которое означает, что вершина s не обязательно должна быть истоком (вершина, у ко­торой отсутствуют входящие ребра), а вершина t — стоком (вершина, у которой отсутствуют исходя­щие ребра), но, тем не менее, они рассматривают­ся именно в этом качестве, поскольку в наших рас­суждениях (и в предлагаемых нами алгоритмах) игнорируются ребра, направленные в s, и ребра, исходящие из. Во избежание путаницы, в примерах мы будем рассматривать сети с одним истоком и стоком; ситуацию более общего характера мы рас­смотрим в разделе 22.4. Мы будем называть верши­ны s и /, соответственно, " истоком" и " стоком" st- сети, поскольку именно эти роли они исполняют в рассматриваемой сети. Остальные вершины сети мы будем называть внутренними вершинами.

Определение 22.2. Транспортная сеть (flow network) есть st-сеть с положительными весами ре­бер, которые мы будем называть пропускными способностями (capacities). Поток (flow) в транс­портной сети есть множество ребер с неотрица­тельными весами, в дальнейшем реберными пото­ками (edge flows), которые удовлетворяют требованию того, что ни один поток в ребре не может быть больше пропускной способности реб­ра и что суммарный поток, поступающий в каж­дую внутреннюю вершину, равен суммарному пото­ку, вытекающему из этой вершины.