![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22, Потоки в сетях. typename Graph::adjIterator A(G, 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. Алгоритмы на графах
стой, однако, как показал пример задачи поиска гамильтонова пути, которую мы исследовали в разделе 17.7 (и многих других задач), наивный подход выбора пар каким-либо систематическим способом до тех пор, пока не возникнет противоречие, требует для своего выполнения экспоненциальных затрат времени. То есть, существует слишком большое подмножеств пар, чтобы можно было проверить все возможности; решение этой задачи должно быть достаточно разумным, чтобы мы использовали лишь немногими из них. Решение специальных головоломок сочетания, подобных описанной выше, или разработка алгоритмов, которые способны эффективно решать любую такую головоломку, суть нетривиальные случаи, позволяющие продемонстрировать большие возможности и применимость модели потоков в сети, которая также позволяет найти разумный способ построения двудольного сочетания. Свойство 22.19. Задача о двудольном сочетании сводится к задаче о максимальном потоке. Доказательство: Для заданной задачи двудольного сочетания построим пример задачи о максимальном потоке за счет проведения всех ребер из одного множества в другое, с добавлением истока, из которого направлены ребра во все элементы одного множества, и стока, в который направлены ребра из элементов другого множества. Чтобы преобразовать полученный орграф в сеть, назначим каждому ребру пропускную способность, равную 1. Означенное построение показано на рис. 22.38. Теперь любое решение задачи о максимальном потоке применительно к этой сети дает решение соответствующей задачи о двудольном сочетании. Сочетание в точности соответствует тем ребрам, соединяющим вершины обоих множеств, которые заполнены до пропускной способности алгоритмом вычисления максимального потока. Во-пер- РИСУНОК 22.38. СВЕДЕНИЕ ЗАДАЧИ О ДВУДОЛЬНОМ СОЧЕТАНИИ ЗАДАЧЕ О МАКСИМАЛЬНОМ ПОТОКЕ Чтобы найти максимальное сочетание в двудольном графе (сверху) мы строим st-сеть (внизу), направляя все ребра из верхнего ряда в нижний ряд, добавляя новый исток, из которого ребра ведут в каждую вершину верхнего ряда, добавляя новый сток, в который ведут ребра из каждой вершины нижнего ряда, и назначая всем ребрам пропускную способность, равную 1. При любом потоке может быть заполнено, самое большее, одно ребро из всех ребер, исходящих из каждой вершины верхнего ряда, а также может быть заполнено, самое большее, одно входящее в ребро из всех ребер, входящих в каждую вершину нижнего ряда, так что решение задачи о максимальном потоке для этой сети дает максимальное сочетание для двудольных графов.
|