Задача максимального расхода - Maximum flow problem

Потоковая сеть для проблемы: каждый человек (r i ) желает усыновить кошку (w i 1) и / или собаку (w i 2). Однако каждое домашнее животное (p i ) отдает предпочтение только подгруппе людей. Найдите любое соответствие домашних животных людям так, чтобы максимальное количество домашних животных было принято одним из предпочитаемых им людей.

В теории оптимизации , максимальные задачи потока вовлекают найти посильную поток через сеть потока , который получает максимально возможную скорость потока.

Задачу максимального потока можно рассматривать как частный случай более сложных проблем сетевого потока, таких как проблема циркуляции . Максимальное значение st-потока (т. Е. Потока от источника s к приемнику t) равно минимальной пропускной способности st-отрезка (т. Е. Отрезка s от t) в сети, как указано в max-flow min- теорема сокращения .

История

Задача о максимальном потоке была впервые сформулирована в 1954 году Т.Е. Харрисом и Ф.С. Россом как упрощенная модель советского железнодорожного движения.

В 1955 году Лестер Р. Форд-младший и Делберт Р. Фулкерсон создали первый известный алгоритм - алгоритм Форда – Фулкерсона . В своей статье 1955 года Форд и Фулкерсон написали, что проблема Харриса и Росса формулируется следующим образом (см. Стр. 5):

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

В своей книге « Потоки в сети» в 1962 году Форд и Фулкерсон писали:

Она была поставлена ​​авторам весной 1955 года Т.Е. Харрисом, который вместе с генералом Ф.С. Россом (в отставке) сформулировал упрощенную модель движения железнодорожного транспорта и определил эту конкретную проблему как центральную, предложенную Правительством США. модель [11].

где [11] относится к секретному отчету Харриса и Росса « Основы метода оценки пропускной способности железных дорог» 1955 года (см. стр. 5).

За прошедшие годы были обнаружены различные улучшенные решения проблемы максимального потока, в частности алгоритм кратчайшего увеличивающегося пути Эдмондса и Карпа и независимо Диница; алгоритм блокировки потока Диница; нажимной алгоритм повторной расстановки меток из Голдберг и Tarjan ; и алгоритм двоичного блокирующего потока Голдберга и Рао. Алгоритмы Шермана и Келнера, Ли, Ореккья и Сидфорда соответственно находят приблизительно оптимальный максимальный поток, но работают только в неориентированных графах.

В 2013 году Джеймс Б. Орлин опубликовал статью с описанием алгоритма. ${\ Displaystyle O (| V || E |)}$

Определение

Поточная сеть с источником s и стоком t . Цифры рядом с краем - это вместимость.

Сначала введем некоторые обозначения:

• Позвольте быть сетью, являющейся источником и приемником соответственно.${\ Displaystyle N = (V, E)}$${\ displaystyle s, t \ in V}$${\ displaystyle N}$
• Если есть функция на краях, то ее значение на обозначается символом или${\ displaystyle g}$${\ displaystyle N}$${\ displaystyle (u, v) \ in E}$${\ displaystyle g_ {uv}}$${\ displaystyle g (u, v).}$

Определение. Емкость ребра максимального количество потоков , которые могут проходить через край. Формально это карта${\ displaystyle c: E \ to \ mathbb {R} ^ {+}.}$

Определение. Поток представляет собой карту , которая удовлетворяет следующему: ${\ displaystyle f: E \ to \ mathbb {R}}$

• Ограничение емкости . Другими словами, поток ребра не может превышать его пропускную способность: для всех${\ displaystyle f_ {uv} \ leq c_ {uv}}$${\ displaystyle (u, v) \ in E.}$
• Сохранение потоков. Сумма потоков, входящих в узел, должна равняться сумме потоков, выходящих из этого узла, за исключением источника и приемника. Или:

${\ Displaystyle \ forall v \ in V \ setminus \ {s, t \}: \ quad \ sum _ {u: (u, v) \ in E} f_ {uv} = \ sum _ {u: (v, u) \ in E} f_ {vu}.}$

Замечание . Потоки кососимметричны: для всех${\ displaystyle f_ {uv} = - f_ {vu}}$${\ displaystyle (u, v) \ in E.}$

Определение. Величина потока является количеством проходящего от источника к раковине потока. Формально для потока это: ${\ displaystyle f: E \ to \ mathbb {R} ^ {+}}$

${\ Displaystyle | е | = \ сумма _ {v: (s, v) \ in E} f_ {sv}.}$

Определение. Задача максимального потока состоит в том, чтобы направить как можно больше потока из источника в сток, другими словами, найти поток с максимальным значением. ${\ displaystyle f _ {\ textrm {max}}}$

Обратите внимание, что может существовать несколько максимальных потоков, и если разрешены произвольные действительные (или даже произвольные рациональные) значения потока (а не только целые числа), существует либо ровно один максимальный поток, либо бесконечно много, поскольку существует бесконечно много линейных комбинаций базовые максимальные потоки. Другими словами, если мы отправляем единицы потока на краю в одном максимальном потоке и единицы потока на другом максимальном потоке, то для каждого мы можем отправить блоки и направить поток по оставшимся краям соответственно, чтобы получить другой максимальный поток. Если значения расхода могут быть любыми действительными или рациональными числами, то таких значений для каждой пары бесконечно много . ${\ displaystyle x}$${\ displaystyle u}$${\ displaystyle y> x}$${\ displaystyle u}$${\ displaystyle \ Delta \ in [0, yx]}$${\ displaystyle x + \ Delta}$${\ displaystyle u}$${\ displaystyle \ Delta}$${\ displaystyle x, y}$

Алгоритмы

В следующей таблице перечислены алгоритмы решения задачи максимального расхода.

Метод	Сложность	Описание
Линейное программирование		Ограничения, заданные определением юридического потока . Смотрите линейную программу здесь.
Алгоритм Форда – Фулкерсона	${\ Displaystyle О (Е \ верт f_ {макс} \ верт)}$	Пока существует открытый путь через остаточный граф, отправьте минимум остаточных мощностей на пути. Алгоритм гарантированно завершится, только если все веса рациональны , и в этом случае сумма, добавляемая к потоку на каждом шаге, является, по крайней мере, наибольшим общим делителем весов. В противном случае возможно, что алгоритм не сойдется к максимальному значению. Однако, если алгоритм завершается, гарантируется нахождение максимального значения.
Алгоритм Эдмондса – Карпа	${\ displaystyle O (VE ^ {2})}$	Специализация Форда – Фулкерсона, поиск дополнительных путей с помощью поиска в ширину .
Алгоритм диника	${\ displaystyle O (V ^ {2} E)}$	На каждом этапе алгоритмы строят многоуровневый граф с поиском в ширину на остаточном графе . Максимальный поток на многоуровневом графике можно рассчитать по времени, а максимальное количество фаз равно . В сетях с единичной мощностью алгоритм Диника завершается во времени. ${\ displaystyle O (VE)}$${\ Displaystyle V-1}$${\ Displaystyle О (\ мин \ {V ^ {2/3}, E ^ {1/2} \} E)}$
Алгоритм MKM (Малхотра, Кумар, Махешвари)	${\ displaystyle O (V ^ {3})}$	Модификация алгоритма Динича с другим подходом к построению блокирующих потоков. Обратитесь к исходной бумаге .
Алгоритм Динича с динамическими деревьями	${\ Displaystyle О (ВЕ \ журнал V)}$	Структура данных динамических деревьев ускоряет вычисление максимального потока в многоуровневом графе до . ${\ Displaystyle О (ВЕ \ журнал V)}$
Общий алгоритм push – relabel	${\ displaystyle O (V ^ {2} E)}$	Алгоритм push relabel поддерживает предварительный поток, то есть функцию потока с возможностью избытка в вершинах. Алгоритм выполняется, пока есть вершина с положительным избытком, т.е. активная вершина в графе. Операция проталкивания увеличивает поток на остаточном ребре, а функция высоты на вершинах управляет тем, через какие остаточные ребра могут протекать потоки. Функция высоты изменяется операцией переназначения. Правильное определение этих операций гарантирует, что результирующая функция потока будет максимальным потоком.
Алгоритм push – reabel с правилом выбора вершин FIFO	${\ displaystyle O (V ^ {3})}$	Вариант алгоритма push-relabel, который всегда выбирает самую последнюю активную вершину и выполняет операции push, пока избыток положительный и есть допустимые остаточные ребра из этой вершины.
Алгоритм push – relabel с правилом выбора вершин на максимальном расстоянии	${\ displaystyle O (V ^ {2} {\ sqrt {E}})}$	Вариант алгоритма push-reabel, который всегда выбирает самую удаленную вершину из или (т.е. вершину самой высокой метки), но в остальном действует как алгоритм FIFO. ${\ displaystyle s}$${\ displaystyle t}$
Алгоритм push-relabel с динамическими деревьями	${\ displaystyle O \ left (VE \ log {\ frac {V ^ {2}} {E}} \ right)}$	Алгоритм строит деревья ограниченного размера на остаточном графе относительно функции высоты. Эти деревья обеспечивают многоуровневые операции проталкивания, т. Е. Проталкивание по всей траектории насыщения вместо одного края.
Алгоритм KRT (King, Rao, Tarjan)	${\ displaystyle O \ left (VE \ log _ {\ frac {E} {V \ log V}} V \ right)}$
Алгоритм двоичного блокирующего потока	${\ displaystyle O \ left (E \ cdot \ min \ {V ^ {2/3}, E ^ {1/2} \} \ cdot \ log {\ frac {V ^ {2}} {E}} \ cdot \ log U \ right)}$	Значение U соответствует максимальной пропускной способности сети.
Алгоритм Джеймса Б. Орлина + KRT (Кинг, Рао, Тарджан)	${\ displaystyle O (VE)}$	Алгоритм Орлина решает максимальный поток за время, пока KRT решает его за . ${\ displaystyle O (VE)}$${\ Displaystyle E \ leq O (V ^ {{\ frac {16} {15}} - \ epsilon})}$${\ displaystyle O (VE)}$${\ displaystyle E> V ^ {1+ \ epsilon}}$
Алгоритм Катурии-Лю-Сидфорда	${\ Displaystyle E ^ {4/3 + о (1)} U ^ {1/3}}$	Методы внутренней точки и усиление ребер с использованием нормальных потоков. Основан на более раннем алгоритме Мадри, который обеспечивает время выполнения . ${\ displaystyle \ ell _ {p}}$${\ displaystyle {\ tilde {O}} (E ^ {10/7} U ^ {1/7})}$
Алгоритм BLNPSSSW / BLLSSSW	${\ Displaystyle {\ тильда {O}} ((E + V ^ {3/2}) \ log U)}$	Методы внутренней точки и динамическое поддержание электрических потоков с детандерными разложениями.
Алгоритм Гао-Лю-Пэна	${\ displaystyle {\ tilde {O}} (E ^ {{\ frac {3} {2}} - {\ frac {1} {328}}} \ log U)}$	Алгоритм Гао, Лю и Пэна вращается вокруг динамического поддержания дополнительных электрических потоков в основе алгоритма, основанного на методе внутренней точки из [Mądry JACM '16]. Это влечет за собой разработку структур данных, которые в ограниченных настройках возвращают ребра с большой электрической энергией в график, претерпевающий обновления сопротивления.

Дополнительные алгоритмы см. В Goldberg & Tarjan (1988) .

Теорема об интегральном потоке

Теорема об интегральном потоке утверждает, что

Если каждое ребро в потоковой сети имеет интегральную пропускную способность, то существует интегральный максимальный поток.

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

заявка

Проблема максимального расхода с несколькими источниками и несколькими стоками

Рис. 4.1.1. Преобразование задачи максимального потока с несколькими источниками и несколькими стоками в задачу о максимальном потоке с одним источником и одним стоком

Учитывая сеть с набором источников и набором приемников, а не только один источник и один приемник, мы должны найти максимальный поток через . Мы можем преобразовать несколько источников проблемы мульти-раковину в максимальные проблемы потока путем добавления консолидированного источника при подключении к каждой вершине в и сводной раковине , соединенный каждой вершина (также известной как supersource и supersink ) с бесконечной мощностью на каждое ребре ( См. Рис. 4.1.1.). ${\ Displaystyle N = (V, E)}$${\ Displaystyle S = \ {s_ {1}, \ ldots, s_ {n} \}}$${\ Displaystyle Т = \ {т_ {1}, \ ldots, т_ {м} \}}$${\ displaystyle N}$${\ displaystyle S}$${\ displaystyle T}$

Максимальное количество элементов при двудольном сопоставлении

Рис. 4.3.1. Преобразование задачи о максимальном двудольном согласовании в задачу о максимальном потоке

Учитывая двудольный граф , мы должны найти соответствие максимальной мощности в , то есть соответствие , которое содержит наибольшее возможное число ребер. Эту задачу можно преобразовать в задачу о максимальном потоке, построив сеть , где ${\ Displaystyle G = (Х \ чашка Y, E)}$${\ displaystyle G}$${\ Displaystyle N = (Икс \ чашка Y \ чашка \ {s, t \}, E ')}$

1. ${\ displaystyle E '}$содержит ребра, направленные от до .${\ displaystyle G}$${\ displaystyle X}$${\ displaystyle Y}$
2. ${\ displaystyle (s, x) \ in E '}$для каждого и для каждого .${\ displaystyle x \ in X}$${\ displaystyle (y, t) \ in E '}$${\ displaystyle y \ in Y}$
3. ${\ Displaystyle с (е) = 1}$для каждого (см. рис. 4.3.1).${\ displaystyle e \ in E '}$

Тогда значение максимального потока в равно размеру максимального сопоставления в , и сопоставление максимальной мощности можно найти, взяв те ребра, которые имеют поток в интегральном максимальном потоке. ${\ displaystyle N}$${\ displaystyle G}$${\ displaystyle 1}$

Минимальное покрытие пути в ориентированном ациклическом графе

Для ориентированного ациклического графа мы должны найти минимальное количество вершинно-непересекающихся путей, чтобы покрыть каждую вершину в . Мы можем построить двудольный граф из , где ${\ Displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle G '= (V _ {\ textrm {out}} \ cup V _ {\ textrm {in}}, E')}$${\ displaystyle G}$

1. ${\ displaystyle V _ {\ textrm {out}} = \ {v _ {\ textrm {out}} \ mid v \ in V \ land v {\ text {имеет исходящие края}} \}}$
2. ${\ displaystyle V _ {\ textrm {in}} = \ {v _ {\ textrm {in}} \ mid v \ in V \ land v {\ text {имеет входящие края}} \}}$
3. ${\ displaystyle E '= \ {(u _ {\ textrm {out}}, v _ {\ textrm {in}}) \ in V_ {out} \ times V_ {in} \ mid (u, v) \ in E \ }}$.

Тогда можно показать, что соответствие размера есть тогда и только тогда, когда оно имеет непересекающееся вершинно-непересекающееся покрытие пути, содержащее ребра и пути, где - количество вершин в . Следовательно, проблема может быть решена путем поиска соответствия максимальной мощности в . ${\ displaystyle G '}$${\ displaystyle M}$${\ displaystyle m}$${\ displaystyle G}$${\ displaystyle C}$${\ displaystyle m}$${\ displaystyle nm}$${\ displaystyle n}$${\ displaystyle G}$${\ displaystyle G '}$

Интуитивно понятно, что если две вершины совпадают , то ребро содержится в . Очевидно, что количество ребер в нем равно . Чтобы увидеть, что это вершина-непересекающаяся, рассмотрим следующее: ${\ displaystyle u _ {\ mathrm {out}}, v _ {\ mathrm {in}}}$${\ displaystyle M}$${\ Displaystyle (и, v)}$${\ displaystyle C}$${\ displaystyle C}$${\ displaystyle m}$${\ displaystyle C}$

1. Каждая вершина в можете быть либо без согласованного в , и в этом случае нет ребра , выходящего в ; или он может быть согласован , и в этом случае существует ровно один край оставляя в . В любом случае, не более одного края листьев любой вершины в .${\ displaystyle v _ {\ textrm {out}}}$${\ displaystyle G '}$${\ displaystyle M}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$
2. Точно так же для каждой вершины in - если она совпадает, есть одно входящее ребро в in ; в противном случае не имеет входящих ребер .${\ displaystyle v _ {\ textrm {in}}}$${\ displaystyle G '}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$

Таким образом, ни одна вершина не имеет двух входящих или двух исходящих ребер , что означает, что все пути в вершине не пересекаются. ${\ displaystyle C}$${\ displaystyle C}$

Чтобы показать, что у обложки есть размер , мы начинаем с пустой обложки и постепенно наращиваем ее. Чтобы добавить вершину к покрытию, мы можем либо добавить ее к существующему пути, либо создать новый путь нулевой длины, начинающийся с этой вершины. Первый случай применим, когда либо и некоторый путь в укрытии начинается в , или, а некоторый путь заканчивается в . Последний случай применим всегда. В первом случае общее количество ребер в крышке увеличивается на 1, а количество путей остается прежним; в последнем случае количество путей увеличивается, а количество ребер остается прежним. Теперь ясно, что после покрытия всех вершин сумма количества путей и ребер в покрытии равна . Следовательно, если количество ребер в покрытии равно , то количество путей равно . ${\ displaystyle C}$${\ displaystyle nm}$${\ displaystyle u}$${\ displaystyle (u, v) \ in E}$${\ displaystyle v}$${\ displaystyle (v, u) \ in E}$${\ displaystyle v}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle nm}$

Максимальный поток при вершинных возможностях

Рис. 4.4.1. Преобразование задачи о максимальном потоке с ограничением пропускной способности вершин в исходную задачу о максимальном потоке путем разбиения узлов

Пусть будет сеть. Предположим, что в каждом узле есть пропускная способность в дополнение к пропускной способности ребра, то есть такое отображение , что поток должен удовлетворять не только ограничению пропускной способности и сохранению потоков, но также ограничению пропускной способности вершин. ${\ Displaystyle N = (V, E)}$${\ displaystyle c: V \ to \ mathbb {R} ^ {+},}$${\ displaystyle f}$

${\ displaystyle \ sum _ {i \ in V} f_ {iv} \ leq c (v) \ qquad \ forall v \ in V \ backslash \ {s, t \}.}$

Другими словами, количество потока, проходящего через вершину, не может превышать ее пропускную способность. Чтобы найти максимальный поток , мы можем преобразовать задачу в задачу максимального потока в исходном смысле, расширив ее . Сначала каждый заменяется на и , где соединяется ребрами, входящими внутрь и соединяется с ребрами, выходящими из , затем присваивает емкость ребру, соединяющему и (см. Рис. 4.4.1). В этой расширенной сети снято ограничение на пропускную способность вершин, и поэтому проблему можно рассматривать как исходную задачу о максимальном потоке. ${\ displaystyle N}$${\ displaystyle N}$${\ displaystyle v \ in V}$${\ displaystyle v _ {\ text {in}}}$${\ displaystyle v _ {\ text {out}}}$${\ displaystyle v _ {\ text {in}}}$${\ displaystyle v}$${\ displaystyle v _ {\ text {out}}}$${\ displaystyle v}$${\ displaystyle c (v)}$${\ displaystyle v _ {\ text {in}}}$${\ displaystyle v _ {\ text {out}}}$

Максимальное количество путей от s до t

Для ориентированного графа и двух вершин и необходимо найти максимальное количество путей от до . У этой проблемы есть несколько вариантов: ${\ Displaystyle G = (V, E)}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle t}$

1. Пути не должны пересекаться по ребрам. Эту проблему можно преобразовать в задачу максимального потока, построив сеть из , с и, являясь источником и приемником соответственно, и присвоив каждому ребру пропускную способность . В этой сети максимальный поток равен тогда и только тогда, когда существуют пути, не пересекающиеся по ребрам. ${\ Displaystyle N = (V, E)}$${\ displaystyle G}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle N}$${\ displaystyle 1}$${\ displaystyle k}$${\ displaystyle k}$

2. Пути должны быть независимыми, т. Е. Вершинно-непересекающимися (кроме и ). Мы можем построить сеть из с емкостями вершин, где мощности всех вершин и всех ребер равны . Тогда значение максимального потока равно максимальному количеству независимых путей от до . ${\ displaystyle s}$${\ displaystyle t}$${\ Displaystyle N = (V, E)}$${\ displaystyle G}$${\ displaystyle 1}$${\ displaystyle s}$${\ displaystyle t}$

3. В дополнение к тому, что пути не пересекаются по ребрам и / или не пересекаются по вершинам, они также имеют ограничение на длину: мы считаем только пути, длина которых равна точной или максимальной длине . Большинство вариантов этой задачи являются NP-полными, за исключением небольших значений . ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

Проблема закрытия

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

Приложения реального мира

Ликвидация бейсбола

Построение сетевого потока для задачи исключения бейсбола

В задаче на выбывание по бейсболу в лиге соревнуются n команд. На определенном этапе сезона лиги w _i - это количество побед, r _i - количество игр, оставшихся до игры для команды i, а r _ij - количество игр, оставшихся против команды j . Команда выбывает, если у нее нет шансов закончить сезон на первом месте. Задача задачи выбывания бейсбола состоит в том, чтобы определить, какие команды выбывают в каждой точке в течение сезона. Шварц предложил метод, который сводит эту проблему к максимальному потоку в сети. В этом методе создается сеть, чтобы определить, исключена ли команда k .

Пусть G = ( V , E ) - сеть, где s , t ∈ V - источник и сток соответственно. Один добавляет игровой узел _ij, который представляет количество игр между этими двумя командами. Мы также добавляем командный узел для каждой команды и соединяем каждый игровой узел { i , j } с i < j с V , и соединяем каждый из них от s ребром с емкостью r _ij, которое представляет количество игр между этими двумя команды. Мы также добавляем командный узел для каждой команды и соединяем каждый игровой узел { i , j } с двумя командными узлами i и j, чтобы гарантировать победу одной из них. На этих краях нет необходимости ограничивать величину потока. Наконец, от узла команды i к узлу приемника t делаются ребра, а емкость w _k + r _k - w _i устанавливается так, чтобы не дать команде i выиграть больше, чем w _k + r _k . Пусть S будет набором всех команд, участвующих в лиге, и пусть

${\ displaystyle r (S - \ {k \}) = \ sum _ {i, j \ in \ {S - \ {k \} \} \ на вершине i <j} r_ {ij}}$.

В этом методе утверждается , команда к не устранена , если и только если значение потока размера г ( S - { K }) существует в сети G . В указанной статье доказано, что это значение расхода является максимальным значением расхода от s до t .

Расписание авиакомпаний

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

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

Пусть G = ( V , E ) - сеть с s , t ∈ V в качестве узлов источника и приемника. В качестве источника и пункта назначения каждого рейса i к V добавляются два узла : узел s _i как источник и узел d _i как узел назначения рейса i . Также к E добавляются следующие ребра :

1. Ребро с пропускной способностью [0, 1] между s и каждым s _i .
2. Ребро с емкостью [0, 1] между каждыми d _i и t .
3. Ребро с емкостью [1, 1] между каждой парой s _i и d _i .
4. Граница с пропускной способностью [0, 1] между каждыми d _i и s _j , если источник s _j достижим с разумным количеством времени и затрат из пункта назначения рейса i .
5. Ребро с пропускной способностью [0, ∞ ] между s и t .

В упомянутом методе заявлено и доказано, что нахождение значения потока k в G между s и t равносильно нахождению допустимого расписания для полетного набора F с не более чем k экипажами.

Другой вариант расписания авиакомпаний - поиск минимально необходимого экипажа для выполнения всех полетов. Для того , чтобы найти ответ на этот вопрос, двудольный граф G» = ( ∪ B , E ) создаются , где каждый полет имеет копию в множестве A и множество B . Если же плоскость может выполнять полет J после полета я , я ∈ A соединен с J ∈ B . Сопоставление в G ' индуцирует расписание для F, и, очевидно, максимальное двустороннее сопоставление в этом графе дает расписание авиакомпаний с минимальным количеством экипажей. Как упоминается в разделе «Приложение» этой статьи, двустороннее сопоставление с максимальной мощностью является приложением задачи о максимальном потоке.

Проблема обращения – спроса

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

1. Добавьте исходный узел s и добавьте ребра из него в каждый заводской узел f _i с мощностью p _i, где p _i - производительность завода f _i .
2. Добавьте приемный узел t и добавьте ребра из всех деревень v _i в t с пропускной способностью d _i, где d _i - уровень спроса деревни v _i .

Пусть G = ( V , E ) - эта новая сеть. Существует тираж, удовлетворяющий спрос тогда и только тогда, когда:

Максимальное значение расхода ( G ) .${\ Displaystyle = \ сумма _ {я \ in v} d_ {я}}$

Если существует циркуляция, рассмотрение решения с максимальным потоком даст ответ о том, сколько товаров должно быть отправлено по определенной дороге для удовлетворения потребностей.

Задачу можно расширить, добавив нижнюю границу потока на некоторых ребрах.

Сегментация изображения

Исходное изображение размером 8x8.

Сеть построена из растрового изображения. Источник слева, раковина справа. Чем темнее край, тем больше его емкость. a _i высокий, когда пиксель зеленый, b _i, когда пиксель не зеленый. Штрафы p _ij равны.

В своей книге Клейнберг и Тардос представляют алгоритм сегментации изображения. Они представляют собой алгоритм поиска фона и переднего плана на изображении. Точнее, алгоритм принимает растровое изображение в качестве входных данных, смоделированных следующим образом: a _i ≥ 0 - вероятность того, что пиксель i принадлежит переднему плану, b _i ≥ 0 - вероятность того, что пиксель i принадлежит фону, а p _ij - это вероятность того, что пиксель i принадлежит фону. штраф, если два соседних пикселя i и j размещаются один на переднем плане, а другой - на заднем. Цель состоит в том, чтобы найти раздел ( A , B ) набора пикселей, который максимизирует следующее количество

${\ displaystyle q (A, B) = \ sum _ {i \ in A} a_ {i} + \ sum _ {i \ in B} b_ {i} - \ sum _ {\ begin {matrix} i, j {\ text {смежный}} \\ | A \ cap \ {i, j \} | = 1 \ end {matrix}} p_ {ij}}$,

Действительно, для пикселей в A (рассматривается как на переднем плане), мы получаем в _I ; для всех пикселей в B (рассматриваемых как фон) мы получаем b _i . На границе между двумя соседними пикселями i и j мы теряем p _ij . Это эквивалентно минимизации количества

${\ displaystyle q '(A, B) = \ sum _ {i \ in A} b_ {i} + \ sum _ {i \ in B} a_ {i} + \ sum _ {\ begin {matrix} i, j {\ text {смежный}} \\ | A \ cap \ {i, j \} | = 1 \ end {matrix}} p_ {ij}}$

потому что

${\ displaystyle q (A, B) = \ sum _ {i \ in A \ cup B} a_ {i} + \ sum _ {i \ in A \ cup B} b_ {i} -q '(A, B ).}$

Минимальный разрез отображается в сети (треугольники VS круги).

Теперь мы строим сеть, узлами которой являются пиксель, а также источник и приемник, см. Рисунок справа. Подключаем источник к пикселю i ребром веса a _i . Подключаем пиксель i к раковине ребром веса b _i . Мы соединяем пиксель i с пикселем j с весом p _ij . Теперь осталось вычислить минимальный разрез в этой сети (или, что эквивалентно, максимальный поток). На последнем рисунке показан минимальный срез.

Расширения

1. В задаче потока с минимальными затратами каждое ребро ( u , v) также имеет коэффициент затрат a _uv в дополнение к своей пропускной способности. Если поток через край является F _уф , то общая стоимость _ув е _ув . Требуется найти поток заданного размера d с наименьшими затратами. В большинстве вариантов коэффициенты затрат могут быть как положительными, так и отрицательными. Для этой задачи существуют различные полиномиальные алгоритмы.

2. Задача о максимальном потоке может быть дополнена дизъюнктивными ограничениями : отрицательное дизъюнктивное ограничение говорит, что определенная пара ребер не может одновременно иметь ненулевой поток; а положительное дизъюнктивное ограничение говорит , что в некоторых парах ребер, по меньшей мере , один должна иметь ненулевой поток. При отрицательных ограничениях задача становится NP-трудной даже для простых сетей. При положительных ограничениях проблема является полиномиальной, если разрешены дробные потоки, но может быть сильно NP-трудной, когда потоки должны быть целыми.

использованная литература

дальнейшее чтение

• Джозеф Чериян и Курт Мельхорн (1999). «Анализ правила выбора наивысшего уровня в алгоритме preflow-push max-flow». Письма об обработке информации . 69 (5): 239–242. CiteSeerX  10.1.1.42.8563 . DOI : 10.1016 / S0020-0190 (99) 00019-8 .
• Дэниел Д. Слейтор и Роберт Э. Тарджан (1983). «Структура данных для динамических деревьев» (PDF) . Журнал компьютерных и системных наук . 26 (3): 362–391. DOI : 10.1016 / 0022-0000 (83) 90006-5 . ISSN  0022-0000 .
• Юджин Лоулер (2001). «4. Сетевые потоки». Комбинаторная оптимизация: сети и матроиды . Дувр. С. 109–177. ISBN 978-0-486-41453-9.