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

Допустимый поток. Предположим, что веса присвоены каждой вершине транспорт­ной сети, и что вес можно рассматривать как запас (если он принимает положительное значение) или как спрос (если он принимает отрицательное значение), при этом сумма весов вершин сети равна нулю. Будем считать поток допустимым, если разность между притоком и истечением каждой вершины равна весу этой вершины (запас, если разность положительна, и спрос, если разность отрицательна). Пусть дана такая сеть, определить, существуют ли допустимые потоки. Рисунок 22.35 служит иллюстрацией задачи о допус­тимом потоке.

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

Свойство 22.18. Задача о допустимом потоке сводится к задаче о максимальном потоке.

Доказательство: Пусть поставлена задача о допустимом потоке, построить сеть с теми же вершинами и ребрами, но вершины при этом не имеют весов. Вместо этого добавь­те вершину истока s, из которой исходят ребра в каждую вершину, имеющую запас с весом, равным запасу соответствующей вершины, и вершину стока t, в которую ве­дет ребро из каждой вершины со спросом (так что вес такого ребра положителен). Решим задачу о максимальном потоке на этой сети. В исходной сети содержится до­пустимое ребро тогда и только тогда, когда все ребра, исходящие из истока, и все ребра, ведущие в сток, заполнены при таком потоке до пропускной способности. Ри­сунок 22.36 показывает пример такого сведения. ■

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

РИСУНОК 22.35. ДОПУСТИМЫЙ ПОТОК

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

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

запас или спрос в каждой вершине, так что построение стандартной сети без этих данных может оказаться оп­равданным. Использование указателей на ребра игра­ет здесь важную роль: если скопировать ребра сети, а затем вычислить максимальный поток, то что мы дол­жны делать с результатом? Перенос вычисленного по­тока (вес каждого ребра) из одной сети в другую, когда обе сети представлены в виде списков смежных вер­шин, - это отнюдь не тривиальное вычисление. Когда используются указатели на ребра, новая сеть содержит копии указателей, а не ребер, так что мы можем пере­давать установки потоков непосредственно в сеть кли­ента. Программа 22.6 представляет собой реализацию, которая может служить иллюстрацией некоторых из этих проблем, которые приходится преодолевать в классе при решении задач поиска подходящих потоков с использованием свойства 22.16.

Программа 22.6. Решение задачи о допустимых
потоках путем сведения ее к задаче о
максимальном потоке_________________________

Рассматриваемый класс решает задачу о допустимом потоке за счет сведения ее к задаче о максимальном потоке, используя построение, представленное на рис. 22.36. Конструктор принимает в качестве аргументов сеть и вектор sd, индексированный именами вершин, такой, что значение sd[i], будучи положительным, представляет запас в вершине i и, будучи отрицательным, - спрос в вершине i.

Как было показано на рис. 22.36, конструктор строит новый граф с теми же ребрами, но с двумя дополнительными вершинами s и t, при этом ребра из s ведут во все вершины с запасами, а из всех вершин со спросом ребра ведут в вершину t. Затем она находит максимальный поток и проверяет, заполнены ли все дополнительные ребра до их пропускных способностей.

РИСУНОК 22.36. СВЕДЕНИЕ ЗАДАЧИ О ДОПУСТИМОМ ПОТОКЕ ДО СТАНДАРТНОЙ ЗАДАЧИ

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

#include " MAXFLOW.cc"

template < class Graph, class Edge> class FEASIBLE

{ const Graph & G;

void freeedges (const Graph & F, int v) { typename Graph:: adjIterator A(F, v);

for (EDGE* e = A.beg();! A.end{); e = A.nxt())

delete e; } public:

FEASIBLE(const Graph & G, vector< int> sd): G(G) { Graph F(G.V()+2);