Задача максимального расхода

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

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

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

История [ править ]

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

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

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

В их книге потоков в сети , ^[5] в 1962 году, Ford и Фулкерсон писал:

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

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

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

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

Определение [ править ]

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

Сначала введем обозначения:

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

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

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

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

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

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

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

|f|=\sum _{v:(s,v)\in E}f_{sv}.

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

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

Алгоритмы [ править ]

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

Методика	Сложность	Описание
Линейное программирование		Ограничения, заданные определением юридического потока . Смотрите линейную программу здесь.
Алгоритм Форда – Фулкерсона	$O(E\vert f_{max}\vert )$	Пока существует открытый путь через остаточный граф, отправьте минимум остаточных мощностей на пути. Алгоритм гарантированно завершится, только если все веса рациональны , и в этом случае сумма, добавляемая к потоку на каждом шаге, является, по крайней мере, наибольшим общим делителем весов. В противном случае возможно, что алгоритм не сойдется к максимальному значению. Однако, если алгоритм завершается, гарантируется нахождение максимального значения.
Алгоритм Эдмондса – Карпа	$O(VE^{2})$	Специализация Форда – Фулкерсона, поиск дополнительных путей с помощью поиска в ширину .
Алгоритм диника	$O(V^{2}E)$	На каждом этапе алгоритмы строят многоуровневый граф с поиском в ширину на остаточном графе . Максимальный расход на многоуровневом графике можно рассчитать по времени, а максимальное количество фаз равно . В сетях с единичной мощностью алгоритм Диника завершается во времени. ^[^{необходима цитата}^] $O(VE)$ $V-1$ $O(\min\{V^{2/3},E^{1/2}\}E)$
Алгоритм MKM (Малхотра, Кумар, Махешвари) ^[10]	$O(V^{3})$	Работает только в ациклических сетях. Обратитесь к исходной бумаге .
Алгоритм Динича с динамическими деревьями	$O(VE\log V)$	Структура данных динамических деревьев ускоряет вычисление максимального потока в многоуровневом графе до . $O(VE\log V)$
Общий алгоритм push – relabel ^[11]	$O(V^{2}E)$	Алгоритм push relabel поддерживает предварительный поток, то есть функцию потока с возможностью избытка в вершинах. Алгоритм выполняется, пока есть вершина с положительным избытком, т.е. активная вершина в графе. Операция проталкивания увеличивает поток на остаточном ребре, а функция высоты на вершинах управляет тем, через какие остаточные ребра могут протекать потоки. Функция высоты изменяется операцией переназначения. Правильное определение этих операций гарантирует, что результирующая функция потока будет максимальным потоком.
Алгоритм push – reabel с правилом выбора вершин FIFO ^[11]	$O(V^{3})$	Вариант алгоритма push-relabel, который всегда выбирает самую последнюю активную вершину и выполняет операции push, пока избыток положительный и есть допустимые остаточные ребра из этой вершины.
Алгоритм push-relabel с динамическими деревьями ^[11]	$O\left(VE\log {\frac {V^{2}}{E}}\right)$	Алгоритм строит деревья ограниченного размера на остаточном графе относительно функции высоты. Эти деревья обеспечивают многоуровневые операции проталкивания, т. Е. Проталкивание по всей траектории насыщения вместо одного края.
Алгоритм KRT (King, Rao, Tarjan) ^[12]	$O\left(VE\log _{\frac {E}{V\log V}}V\right)$
Алгоритм двоичного блокирующего потока ^[13]	$O\left(E\cdot \min\{V^{2/3},E^{1/2}\}\cdot \log {\frac {V^{2}}{E}}\cdot \log U\right)$	Значение U соответствует максимальной пропускной способности сети.
Алгоритм Джеймса Б. Орлина + KRT (Кинг, Рао, Тарджан) ^[9]	$O(VE)$	Алгоритм Орлина решает максимальный поток за время, пока KRT решает его за . $O(VE)$ $E\leq O(V^{{\frac {16}{15}}-\epsilon })$ $O(VE)$ $E>V^{1+\epsilon }$

Более подробный список см. В Goldberg & Tarjan (1988) .

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

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

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

Заявление [ править ]

Проблема максимального потока с несколькими источниками и несколькими стоками [ править ]

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

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

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

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

$V_{\textrm {out}}=\{v_{\textrm {out}}\mid v\in V\land v{\text{ has positive out-degree}}\}$
$V_{\textrm {in}}=\{v_{\textrm {in}}\mid v\in V\land v{\text{ has positive in-degree}}\}$
$E'=\{(u_{\textrm {out}},v_{\textrm {in}})\in V_{out}\times V_{in}\mid (u,v)\in E\}$ .

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

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

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

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

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

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

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

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

Тогда значение максимального потока в равно размеру максимального совпадения в . $N$ $G$

Максимальный поток с вместимостью вершин [ править ]

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

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

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

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

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

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

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

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

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

Проблема закрытия [ править ]

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

Приложения реального мира [ править ]

Ликвидация бейсбола [ править ]

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

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

Пусть G = ( V , E ) - сеть, где s , t ∈ V - источник и сток соответственно. Один добавляет игровой узел { 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 будет набором всех команд, участвующих в лиге, и пусть . В этом методе утверждается, что команда k не удаляется тогда и только тогда, когда в сети существует значение потока размера r ( S - { k }). $\scriptstyle r(S-\{k\})=\sum _{i,j\in \{S-\{k\}\},i<j}r_{ij}$ G . В указанной статье доказано, что это значение расхода является максимальным значением расхода от s до t .

Расписание авиакомпаний [ править ]

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

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

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

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

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

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

Проблема обращения – спроса [ править ]

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

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

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

Максимальное значение расхода (G)

.

=\sum _{i\in v}d_{i}

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

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

Сегментация изображения [ править ]

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

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

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

q(A,B)=\sum _{i\in A}a_{i}+\sum _{i\in B}b_{i}-\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}

,

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

q'(A,B)=\sum _{i\in A}b_{i}+\sum _{i\in B}a_{i}+\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}

потому что

q(A,B)=\sum _{i\in A}a_{i}+\sum _{i\in 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-трудной, когда потоки должны быть целыми. ^[20]

Ссылки [ править ]

^ a b c Schrijver, A. (2002). «Об истории перевозки и проблемах максимального расхода». Математическое программирование . 91 (3): 437–445. CiteSeerX 10.1.1.23.5134 . DOI : 10.1007 / s101070100259 . S2CID 10210675 .
↑ Gass, Saul I .; Асад, Арджанг А. (2005). «Математические, алгоритмические и профессиональные разработки исследования операций с 1951 по 1956 год». Аннотированный график исследования операций . Международная серия исследований операций и управления. 75 . С. 79–110. DOI : 10.1007 / 0-387-25837-X_5 . ISBN 978-1-4020-8116-3.
^ а б Харрис, TE ; Росс, Ф.С. (1955). «Основы метода оценки чистой пропускной способности железных дорог» (PDF) . Меморандум об исследовании .
^ a b Ford, LR ; Фулкерсон, Д.Р. (1956). «Максимальный поток через сеть». Канадский математический журнал . 8 : 399–404. DOI : 10,4153 / CJM-1956-045-5 .
^ a b Ford, LR, Jr .; Фулкерсон, Д. Р., Потоки в сетях , Издательство Принстонского университета (1962).
^ Шерман, Иона (2013). «Почти максимальные потоки за почти линейное время». Материалы 54-го ежегодного симпозиума IEEE по основам информатики . С. 263–269. arXiv : 1304.2077 . DOI : 10.1109 / FOCS.2013.36 . ISBN 978-0-7695-5135-7. S2CID 14681906 .
^ Kelner, JA; Ли, Ю.Т .; Orecchia, L .; Сидфорд, А. (2014). «Алгоритм почти линейного времени для приближенного максимального потока в неориентированных графах и его многокомпонентные обобщения» (PDF) . Материалы двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 217. arXiv : 1304.2338 . DOI : 10.1137 / 1.9781611973402.16 . ISBN 978-1-61197-338-9. S2CID 10733914 . Архивировано из оригинального (PDF) 03 марта 2016 года.
↑ Knight, Helen (7 января 2014 г.). «Новый алгоритм может значительно упростить решение проблемы« максимального потока »» . MIT News . Проверено 8 января 2014 года .
^ a b Орлин, Джеймс Б. (2013). «Макс течет за время O (нм) или лучше». Материалы 45-го ежегодного симпозиума ACM по теории вычислений - STOC '13 . STOC '13 Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . С. 765–774. CiteSeerX 10.1.1.259.5759 . DOI : 10.1145 / 2488608.2488705 . ISBN 9781450320290. S2CID 207205207 .
^ Мальхотра, ВМ; Кумар, М. Прамодх; Махешвари, С. Н. (1978). « Алгоритм поиска максимальных потоков в сетях» (PDF) . Письма об обработке информации . 7 (6): 277–278. DOI : 10.1016 / 0020-0190 (78) 90016-9 . O ( | V | 3 ) {\displaystyle O(|V|^{3})}
^ а б в Гольдберг, А. В .; Tarjan, RE (1988). «Новый подход к проблеме максимального расхода» . Журнал ACM . 35 (4): 921. DOI : 10.1145 / 48014.61051 . S2CID 52152408 .
^ King, V .; Rao, S .; Тарьян, Р. (1994). «Более быстрый детерминированный алгоритм максимального потока». Журнал алгоритмов . 17 (3): 447–474. DOI : 10.1006 / jagm.1994.1044 . S2CID 15493 .
^ Голдберг, А.В .; Рао, С. (1998). «За барьером разложения потока». Журнал ACM . 45 (5): 783. DOI : 10.1145 / 290179.290181 . S2CID 96030 .
^ Итаи, А .; Perl, Y .; Шилоач Ю. (1982). «Сложность поиска максимальных непересекающихся путей с ограничениями длины». Сети . 12 (3): 277–286. DOI : 10.1002 / нетто.3230120306 . ISSN 1097-0037 .
^ Шварц, BL (1966). «Возможные победители частично завершенных турниров». SIAM Обзор . 8 (3): 302–308. DOI : 10.1137 / 1008062 . JSTOR 2028206 .
^ a b Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2001). «26. Максимальный расход». Введение в алгоритмы, второе издание . MIT Press и McGraw-Hill. С. 643–668. ISBN 978-0-262-03293-3.CS1 maint: multiple names: authors list (link)
^ Карл Кингсфорд. «Удлинители максимального расхода: циркуляции с потребностями» (PDF) .
^ «Проект imagesegmentationwithmaxflow, содержащий исходный код для создания этих иллюстраций» . GitLab . Архивировано из оригинала на 2019-12-22 . Проверено 22 декабря 2019 .
^ «Дизайн алгоритмов» . www.pearson.com . Проверено 21 декабря 2019 .
^ Шауэр, Иоахим; Пферши, Ульрих (2013-07-01). «Задача о максимальном потоке с дизъюнктивными ограничениями». Журнал комбинаторной оптимизации . 26 (1): 109–119. CiteSeerX 10.1.1.414.4496 . DOI : 10.1007 / s10878-011-9438-7 . ISSN 1382-6905 . S2CID 6598669 .

Дальнейшее чтение [ править ]

Джозеф Чериян и Курт Мельхорн (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.

[:0-1] Schrijver, A. (2002). «Об истории перевозки и проблемах максимального расхода». Математическое программирование . 91 (3): 437–445. CiteSeerX 10.1.1.23.5134 . DOI : 10.1007 / s101070100259 . S2CID 10210675 .

[2] Gass, Saul I .; Асад, Арджанг А. (2005). «Математические, алгоритмические и профессиональные разработки исследования операций с 1951 по 1956 год». Аннотированный график исследования операций . Международная серия исследований операций и управления. 75 . С. 79–110. DOI : 10.1007 / 0-387-25837-X_5 . ISBN 978-1-4020-8116-3.

[:2-3] а б Харрис, TE ; Росс, Ф.С. (1955). «Основы метода оценки чистой пропускной способности железных дорог» (PDF) . Меморандум об исследовании .

[:1-4] Ford, LR ; Фулкерсон, Д.Р. (1956). «Максимальный поток через сеть». Канадский математический журнал . 8 : 399–404. DOI : 10,4153 / CJM-1956-045-5 .

[:3-5] Ford, LR, Jr .; Фулкерсон, Д. Р., Потоки в сетях , Издательство Принстонского университета (1962).

[6] Шерман, Иона (2013). «Почти максимальные потоки за почти линейное время». Материалы 54-го ежегодного симпозиума IEEE по основам информатики . С. 263–269. arXiv : 1304.2077 . DOI : 10.1109 / FOCS.2013.36 . ISBN 978-0-7695-5135-7. S2CID 14681906 .

[7] Kelner, JA; Ли, Ю.Т .; Orecchia, L .; Сидфорд, А. (2014). «Алгоритм почти линейного времени для приближенного максимального потока в неориентированных графах и его многокомпонентные обобщения» (PDF) . Материалы двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 217. arXiv : 1304.2338 . DOI : 10.1137 / 1.9781611973402.16 . ISBN 978-1-61197-338-9. S2CID 10733914 . Архивировано из оригинального (PDF) 03 марта 2016 года.

[8] Knight, Helen (7 января 2014 г.). «Новый алгоритм может значительно упростить решение проблемы« максимального потока »» . MIT News . Проверено 8 января 2014 года .

[orlin-9] Орлин, Джеймс Б. (2013). «Макс течет за время O (нм) или лучше». Материалы 45-го ежегодного симпозиума ACM по теории вычислений - STOC '13 . STOC '13 Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . С. 765–774. CiteSeerX 10.1.1.259.5759 . DOI : 10.1145 / 2488608.2488705 . ISBN 9781450320290. S2CID 207205207 .

[10] Мальхотра, ВМ; Кумар, М. Прамодх; Махешвари, С. Н. (1978). « Алгоритм поиска максимальных потоков в сетях» (PDF) . Письма об обработке информации . 7 (6): 277–278. DOI : 10.1016 / 0020-0190 (78) 90016-9 . O ( | V | 3 ) {\displaystyle O(|V|^{3})}

[goldberg1988-11] а б в Гольдберг, А. В .; Tarjan, RE (1988). «Новый подход к проблеме максимального расхода» . Журнал ACM . 35 (4): 921. DOI : 10.1145 / 48014.61051 . S2CID 52152408 .

[12] King, V .; Rao, S .; Тарьян, Р. (1994). «Более быстрый детерминированный алгоритм максимального потока». Журнал алгоритмов . 17 (3): 447–474. DOI : 10.1006 / jagm.1994.1044 . S2CID 15493 .

[13] Голдберг, А.В .; Рао, С. (1998). «За барьером разложения потока». Журнал ACM . 45 (5): 783. DOI : 10.1145 / 290179.290181 . S2CID 96030 .

[14] Итаи, А .; Perl, Y .; Шилоач Ю. (1982). «Сложность поиска максимальных непересекающихся путей с ограничениями длины». Сети . 12 (3): 277–286. DOI : 10.1002 / нетто.3230120306 . ISSN 1097-0037 .

[15] Шварц, BL (1966). «Возможные победители частично завершенных турниров». SIAM Обзор . 8 (3): 302–308. DOI : 10.1137 / 1008062 . JSTOR 2028206 .

[ITA-16] Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2001). «26. Максимальный расход». Введение в алгоритмы, второе издание . MIT Press и McGraw-Hill. С. 643–668. ISBN 978-0-262-03293-3.CS1 maint: multiple names: authors list (link)

[17] Карл Кингсфорд. «Удлинители максимального расхода: циркуляции с потребностями» (PDF) .

[18] «Проект imagesegmentationwithmaxflow, содержащий исходный код для создания этих иллюстраций» . GitLab . Архивировано из оригинала на 2019-12-22 . Проверено 22 декабря 2019 .

[19] «Дизайн алгоритмов» . www.pearson.com . Проверено 21 декабря 2019 .

[20] Шауэр, Иоахим; Пферши, Ульрих (2013-07-01). «Задача о максимальном потоке с дизъюнктивными ограничениями». Журнал комбинаторной оптимизации . 26 (1): 109–119. CiteSeerX 10.1.1.414.4496 . DOI : 10.1007 / s10878-011-9438-7 . ISSN 1382-6905 . S2CID 6598669 .

[1]