Глава 22, Потоки в сетях. typename Graph::adjIterator A(G, v);

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

{

typename Graph:: adjIterator A(G, v);

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

F.insert(e); }

int s = G.V(), t = G.V()+1; for (int i = 0; i < G.V(); i++) if (sd[i] > = 0)

F.insert(new EDGE(s, i, sd[i])*); else

F.insert(new EDGE(i, t, -sd[i])); MAXFLOW< Graph, Edge> (F, s, t); freeedges(F, s); freeedges(F, t); } };

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

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

Для краткости изложения будем далее называть эту за­дачу просто задачей двудольного сочетания (bipartite matching) за исключением случаев, в которых нужно отличить ее от других подобных задач. Она формализует задачу трудоуст­ройства, которая кратко рассматривалась в начале данной главы. Вершины соответствуют претендентам и работодате­лям, а ребра — отношению " взаимной заинтересованности в трудоустройстве". Решение задачи двудольного сочетания приводит к максимально возможному трудоустройству. На рис. 22.37 показан двудольный граф, моделирующий демон­страционную задачу, представленную на рис. 22.3.

РИСУНОК 22.37. ДВУДОЛЬНОЕ СОЧЕТАНИЕ

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

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

Это весьма поучительный пример, заставляющий задуматься над тем, как найти пря­мое решение задачи о двудольном сочетании без применения с этой целью модели, использующей графы. Например, эта задача сводится к следующей комбинаторной голо­воломке: " найти максимальное подмножество пар целых чисел (взятых из непересекаю­щихся множеств), обладающих тем свойством, что ни одна из пар не содержит одинако­вых целых чисел". Пример, приведенный на рис. 22.27, соответствует решению этой головоломки на парах 0-6, 0-7, 0-8, 1-6 и т.д. Эта задача, на первый взгляд, кажется про-

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

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

Доказательство: Для заданной задачи двудольного сочетания построим пример задачи о максималь­ном потоке за счет проведения всех ребер из од­ного множества в другое, с добавлением истока, из которого направлены ребра во все элементы одного множества, и стока, в который направле­ны ребра из элементов другого множества. Чтобы преобразовать полученный орграф в сеть, назна­чим каждому ребру пропускную способность, равную 1. Означенное построение показано на рис. 22.38.

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

РИСУНОК 22.38. СВЕДЕНИЕ ЗАДАЧИ О ДВУДОЛЬНОМ СОЧЕТАНИИ ЗАДАЧЕ О МАКСИМАЛЬНОМ ПОТОКЕ

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