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

ющему исходному значению плюс сумма пропускных способностей исходящих ребер. Для каждого ребра u-v исходной сети с пропускной способностью с в двудольную сеть включим вершину с величиной запаса или спроса -с (для ссылок на такую вершину мы воспользуемся обозначением [u-v]). Для каждого ребра u-v в исходной сети вклю­чим в двудольную сеть два ребра: одно из них обладает той же стоимостью и ведет из и в [u-v], другое, имея стоимость 0, ведет из v в [u-v].

Следующее соответствие один к одному сохраняет стоимости потоков в обеих сетях неизменными: ребро u-v исходной сети пропускает поток величины f тогда и только тогда, когда в ребре u-[u-v] двудольной сети протекает поток величины c-f (эти два потока должны давать в сумме значение с в силу ограничения на запас-спрос, действу­ющего в вершине [u-v]). Следовательно, любой поток минимальной стоимости в од­ной сети соответствует потоку минимальной стоимости в другой сети. ■

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

В этом контексте нам следует рассмотреть другую классическую задачу. Она обобща­ет задачу о двудольном сочетании, которая подробно изучалась в разделе 22.4. Подобно упомянутой задаче, простота данной задачи также обманчива.

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

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

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

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

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

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

Сведение этого варианта транспортной задачи к задаче вычисления минимального по­тока позволяет получить построение, по существу эквивалентное построению, кото­рое мы использовали для сведения задачи двудольного сочетания к задаче вычисле­ния максимального потока (см. упражнение 22.158). ■

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

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

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

РИСУНОК 22.52. ЗАДАЧА О ПОЧТАЛЬОНЕ Построение кратчайшего пути, который включает каждое ребро по меньшей мере один раз, представля­ет собой трудную задачу даже для такой простой сети, как эта, однако данная задача может быть эффективно решена за счет сведения к задаче о потоке минимальной стоимости.

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

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

Задача о почтальоне представляет собой задачу поиска эй­лерова пути, которую мы рассматривали в разделе 17.7: реше­ние упражнения 17.92 представляет собой простую проверку

Глава 22. Потоки в сетях

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

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

Доказательство: Дан вариант задачи о почтальоне (взвешенный орграф), определить распределительную сеть с теми же вершинами и ребрами, причем все значения запа­са и спроса в вершине равны 0, стоимость ребра устанавливается равной весу соот­ветствующего ребра, на пропускную способность ребер не накладываются никакие ограничения сверху, в то же время все пропускные способности ребер должны быть больше 1. Мы рассматриваем величину f потока в ребре u-v следующим образом: по­чтальон должен пройти по ребру u-v в сумме f раз.

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

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

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

Подобно тому, как мы поступали при изучении максимального потока, мы можем выяснить, как любую задачу о минимальном потоке представить в виде LP-задачи (см. рис. 22.53). Ее постановка есть простое расширение постановки задачи о максимальном потоке: мы добавляем уравнения, которые устанавливают значение фиктивной перемен-

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

ной равным стоимости потока, затем ставят цель мини­мизировать эту переменную. LP-модель позволяет доба­вить произвольные (линейные) ограничения. Некото­рые из этих ограничений могут привести к задачам, эквивалентным задачам о потоках минимальной сто­имости, другие - нет. Другими словами, многие зада­чи не сводятся к задачам о потоках минимальной сто­имости: в частности, линейное программирование охватывает намного более широкое множество задач. Задача о потоке минимальной стоимости представляет собой следующий шаг в направлении той обобщенной модели решения задачи, которая будет рассматривать­ся в части 8.

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