![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22, Потоки в сетях. Допустимый поток.Предположим, что веса присвоены каждой вершине транспортной сети, и что вес можно рассматривать как запас (если он принимает положительное
Вершины с запасом соответствуют складам в задаче о распределении запасов; вершины со спросом соответствуют розничным торговым точкам; ребра соответствуют дорогам на маршрутах грузовых машин. Задача о допустимых потоках отвечает на следующий основной вопрос: можно ли отыскать такой способ доставки товаров, при котором повсеместно обеспечивается соответствие запасов и спроса. Свойство 22.18. Задача о допустимом потоке сводится к задаче о максимальном потоке. Доказательство: Пусть поставлена задача о допустимом потоке, построить сеть с теми же вершинами и ребрами, но вершины при этом не имеют весов. Вместо этого добавьте вершину истока s, из которой исходят ребра в каждую вершину, имеющую запас с весом, равным запасу соответствующей вершины, и вершину стока t, в которую ведет ребро из каждой вершины со спросом (так что вес такого ребра положителен). Решим задачу о максимальном потоке на этой сети. В исходной сети содержится допустимое ребро тогда и только тогда, когда все ребра, исходящие из истока, и все ребра, ведущие в сток, заполнены при таком потоке до пропускной способности. Рисунок 22.36 показывает пример такого сведения. ■ Разработка классов, реализующих сведения рассмотренного типа, которые анализировались выше, может оказаться сложной задачей для программистов, главным образом в силу того обстоятельства, что объекты, которыми мы манипулируем, представлены сложными структурами данных. Должны ли мы строить новую сеть, чтобы свести еще одну задачу к стандартной задаче о максимальном потоке? Некоторые из задач требуют для своего решения дополнительных данных, таких как пропускная способность вершин, РИСУНОК 22.35. ДОПУСТИМЫЙ ПОТОК В рамках задачи о допустимом потоке мы задаем величины запаса и спроса в дополнение к значениям пропускной способности ребер. Мы ищем такой поток, при котором истечение равно запасам плюс притоку в вершинах с запасом, а приток равен истечению плюс спрос в вершинах со спросом. Три решения задачи о допустимых потоках, представленных на диаграмме слева, показаны на диаграммах справа. Часть 5. Алгоритмы на графах
Программа 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);
|