Глава 22. Потоки в сетях. Свойство 22.22.Задача о допустимом потоке минимальной стоимости и задача о мак­симальном потоке с минимальной стоимостью эквивалентны.

Свойство 22.22. Задача о допустимом потоке минимальной стоимости и задача о мак­симальном потоке с минимальной стоимостью эквивалентны.

Доказательство: Непосредственно следует из соответствия, использованного при до­казательстве свойства 22.18 (см. также упражнение 22.76). ■

Как следствие этой эквивалентности и в силу того, что задача о допустимом потоке с минимальной стоимостью непосредственно моделирует задачи о распределении товаров и многие другие приложения, мы употребляем термин поток минимальной стоимости (minicost flow) для обозначения обеих задач в контексте, в котором мы будем ссылаться на любую из них. Сведения к другим задачам мы рассмотрим в разделе 22.7.

Чтобы иметь возможность использовать стоимости ребер в транспортных сетях, вве­дем целочисленный элемент данных pcost в класс EDGE из раздела 22.1 и функцию-эле­мент cost(), возвращающую значение стоимости клиенту. Программа 22.8 представляет собой клиентскую функцию, которая вычисляет стоимость потока в графе, в котором построены указатели на такие ребра. Как и в случаях, когда мы работаем с максималь­ными потоками, целесообразно реализовать функцию, проверяющую, что величины при­токов и истечений соответствуют в каждой вершине, а структуры данных непротиворе­чивы (см. упражнение 22.12).

Программа 22.8. Вычисление стоимости потока________________________________

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

static int cost(Graph & G) { int x = 0;

for (int v = O; v < G.V(); v++) {

typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) if (e-> from(v) & & e-> costRto(e-> w()) < C)

x += e-> flow()*e-> costRto(e-> w()); }

return x; }

Первый шаг в разработке алгоритмов решения задачи выявления потока с минималь­ной стоимостью состоит в таком расширении определения остаточных сетей, чтобы они включали стоимость ребер.

Определение 22.9. Пусть задан поток в транспортной сети со стоимостями ребер, ос­таточная сеть (residual network) для этого потока содержит те же вершины, что и ис­ходная сеть, и одно или два ребра этой остаточной сети соответствуют каждом ребру в исходной сети и определяются следующим образом: пусть для каждого ребра u-v в исход­ной сети f есть поток, с есть пропускная способность и х — стоимость. Если f положи­телен, ребро u-v включается в остаточную сеть, при этом ему присваивается пропускная способностью f, и стоимость -х; если {меньше, чем с, ребро u-v включается в остаточ­ную сеть с пропускной способностью c-f, со стоимостью -х.

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