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

же пропускной способностью и чтобы вершины и и и* входили в одно и то же мно­жество для всех и, так что в соответствии с изложенным в предыдущем абзаце, мы получаем сечение в исходной сети, что и завершит наше доказательство. Во-первых, если и содержится в 5* a t содержится в Г*, то u-u* должно быть пересекающим реб­ром, что приводит к противоречию: u-u* не может быть никаким минимальным сече­нием, поскольку сечение, состоящий из всех ребер, соответствующих ребрам исход­ного графа, имеет меньшую стоимость. Во-вторых, если и содержится в Г*, а и* содержится в S*, то s-u должно находиться в этом сечении, поскольку оно является единственным ребром, соединяющим s и и. Но мы можем построить сечение той же сто­имости путем подстановки всех ребер, направленных из и, на s-u, перемещая и в S*.

Если в преобразованной сети задан какой-либо поток величины с + X, то мы просто мы назначаем каждому соответствующему ребру в исходной сети поток величины с. Преобразование сечения, описанное в предыдущем абзаце, не затрагивает это назна­чение, поскольку оно манипулирует ребрами, в которых поток равен 0. ■

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

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

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

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

также верно: если в неориентированной сети через ребро u-v протекает поток f, через ребро v-u проте­кает поток g, то мы можем поместить поток f- g в ребро u-v ориентированной сети, если f> g; в про­тивном случае это будет поток g—f в ребре v-u. Сле­довательно, любой максимальный поток в ориенти­рованной сети есть максимальный поток в неориентированной сети: это построение дает по­ток, и любой поток в ориентированной сети большей величины будет соответствовать некоторому потоку большей величины в неориентированной сети; однако такого потока не существует. ■

Это доказательство не утверждает, что задача о мак­симальном потоке в неориентированной сети эквива­лентна стандартной задаче. Иначе говоря, вполне может случиться, что вычисление максимальных потоков в неориентированных сетях легче, чем вычисление макси­мальных потоков в стандартных сетях (см. упражнение 22.81).

В целом мы можем применять к сетям со многими стоками и истоками, неориентированным сетям, к се­тям с ограничениями на пропускные способности вер­шин и многим другим типам сетей (см., например, уп­ражнение 22.79) алгоритмы вычисления максимального потока для st-сетей, рассмотренные в двух предыдущих разделах. Фактически свойство 22.16 утверждает, что мы можем решить все эти задачи даже при помощи алго­ритма, который работает только на ациклических сетях.

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

РИСУНОК 22.34. СВЕДЕНИЕ ЗАДАЧИ О ПОТОКАХ В