Задача о максимальном потоке

Максимальный поток

Максимальный поток для моделирования очень большого класса задач. Их интерпретация соответствует циркуляции физических потоков в сети: распределение электроэнергии, сеть снабжения, маршрутизация пакетов в Интернете и т. д. Речь идет о транспортировке максимально возможного количества материала между источником с и пункт назначения ты.

Определение сети

Сеть — это график ориентированный N=(V,A) с положительным нормированием его дуг. Оценка c(x,y) дуги (x,y) называется пропускной способностью дуги. N имеет две определенные вершины: источник s и пункт назначения t. Остальные вершины называются промежуточными узлами.

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

Поток F в сети N — это положительная оценка дуг, которая проверяет следующие два свойства:

  1. Для любого лука а ∈ В, 0 ≤ Ф(а)что)
  2. Для любой промежуточной вершины ИксеВ \ { ул. }, ∑там F (у, х) = ∑там Ф(х,у)

Сумма F(Икс) =тамF (у, х) это приток наверху Икс
Сумма F+(Икс) =тамФ(х,у) это исходящий поток Саммит Икс
То ценность | Ф | наводнения Ф определяется как исходящий поток минус входящий поток в с : | Ф | = Ф+(с)Ф(с).

Задача о максимальном потоке

Классическая задача о максимальном потоке — это линейная задача. Предположим, что сеть имеет ребра между любой парой вершин. Если мощности нет, она фиксируется на 0. Целевая функция представляет собой сумму потоков, выходящих из источника или входящих в сток. Функция объектива может различаться в зависимости от объектива.

Основные ограничения идентичны независимо от целевой функции:

  • Ограничения пропускной способности: f(u,v) ≤ c(u,v)
  • Симметрия: f(u,v) = – f(v,u)
  • Сохранение потоков: сумма входящих потоков равна сумме выходящих потоков кроме истока и стока, назовем степенью d(u) разность между выходящим и входящим потоком вершины u: d( u)= 0, за исключением u=s и u=t.
  • другие

Многие проблемы восходят к задаче о максимальном потоке. А алгоритм наивно повторять следующий процесс, пока не застрянете. Найдите путь st, где каждое ребро af(e) <u(e) et augmenter le débit le long du chemin par le minimum de u(e)-f(e). Cette méthode ne donne pas une valeur optimale, nous devons être en mesure de revenir en arrière.

Уменьшение проблем

Проблема потока с несколькими источниками и несколькими скважинами : ко всем источникам подключен фиктивный источник, мощность ребер зависит от различных критериев (мощность вершин, ограничения входящего-исходящего потока). Скважины соединены с фиктивной скважиной. Этот тип проблемы обычно является проблемой сцепления.

Задача потока с пропускной способностью вершин : вершины дублируются как входящая вершина и исходящая вершина с дугой, соединяющей их. Мощность этой дуги равна мощности вершины.

Проблема кратчайший путь : источник — это начало пути и сток с d(s)=1 и d(t)=-1. Ограничений по мощности нет. Стоимость прохождения всех дуг равна 1. Ищем поток с минимальной стоимостью.

Участок сети и остаточная мощность

Разрезом (E,T) транспортной сети N=(V,A) называется разбиение V на E и T=VE такое, что s ∈E и t∈T. Определим пропускную способность c(E,T) разреза как сумму пропускных способностей дуг (u,v) с u в E и v в T. Для любого разреза (E,T) и любого потока f, |f | ограничен пропускной способностью разреза c(E,T).

Удалите набор ребер, чтобы отсоединить t от s. Найдите набор, минимизирующий сумму мощностей дуг. Минимальный разрез — это такое разбиение узлов (S, T), что s находится в S, а t — в T, где c(E,T) минимально. По определению, задача о минимальном разрезе имеет тот же результат, что и задача о максимальном потоке.

Для сети N=(V,A) и потока f из N мы называем остаточную пропускную способность cф (u,v) = c(u,v) – f(u,v). Более того, если емкость (v,u) равна нулю, cф (v,u) = f(u,v). Остаточная емкость всегда положительна или равна нулю.

Остаточный граф — это сеть N'=(V,A) с остаточными пропускными способностями для каждого ребра A. Возрастающий путь — это путь между s и t в остаточном графе.

Максимальный расход Проблема с максимальным расходом Минимальная резка остаточной пропускной способности Увеличение расхода

Из остаточного графа максимального потока можно найти решение задачи минимального разреза (и наоборот). На следующем графике, если вы ищете набор вершин, связанных с вершиной s, вы найдете набор {s,3,4,7}, который является набором S для задачи минимального разреза.

Максимальный расход Проблема с максимальным расходом Минимальная резка остаточной пропускной способности Увеличение расхода

Найдите возрастающий поток

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

Максимальный расход Проблема с максимальным расходом Минимальная резка остаточной пропускной способности Увеличение расхода

Делиться
ru_RURU