Освоение теоремы о максимальном потоке и минимальном разрезе всесторонний и формальный подход

Max flow and min cut theorem comprehensive and formal approach

Исследование области сетей потоков и теоремы о максимальном потоке и минимальном разрезе

Фото от israel palacio на Unsplash

Введение

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

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

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

История

Теорема о максимальном потоке и минимальном разрезе была впервые представлена Фордом и Фалкерсоном в 1956 году в их фундаментальной статье «Максимальный поток через сеть», с участием других значимых математиков, таких как Клод Шеннон, ответственного за развитие теории информации. Теорема утверждает, что максимальный поток в сети равен минимальной пропускной способности разреза, где разрез – это разделение узлов сети на два непересекающихся множества, и его пропускная способность – это сумма пропускных способностей всех ребер, пересекающих разрез. С тех пор эта теорема стала основой теории сетей потоков.

Однако вместе с введением этой теоремы появились и другие ключевые научные вклады, такие как алгоритмы Эдмондса-Карпа, Форда-Фалкерсона и Диница, которые все выполняют общую задачу поиска максимального потока, который может пройти через сеть с источником и стоком. Аналогично, с помощью теоремы о максимальном потоке и минимальном разрезе, этое значение совпадает с минимальным разрезом, разделяющим сток и источник. Более того, мы можем использовать внутренние вычисления алгоритмов, чтобы определить набор ребер, составляющих минимальный разрез, о чем мы рассмотрим далее.

Сети потоков

Таким образом, чтобы упростить объяснение следующей теоремы, мы сначала ознакомимся с основами и неотъемлемыми концепциями о сетях потоков в графовой теории.

Пример сети потоков (Рис. от автора)

Как вы можете видеть в приведенном выше примере, сеть потоков – это взвешенный, направленный мультиграф, используемый для представления объекта или системы, структурированной в виде сети, в которой определенное количество ресурсов, измеряемое в том, что называется «потоком», должно быть передано или перемещено из одной или нескольких точек “источник” (представленных узлом S) в одну или несколько других узлов, называемых “сток” (узел T). Хотя этот конкретный пример не отображает свойство мультиграфа, поскольку между двумя узлами есть только одно ребро.

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

Помимо пропускной способности каждого ребра, важной метрикой, которая определяет скорость перемещения ресурсов через каждое ребро в единицу времени, является поток. Можно сравнить его с трафиком на дороге или объемом воды в трубопроводе. Поэтому, генерируемый в исходных узлах или суперисточнике если все источники сети подключены к главному генератору потока, и принимаемый в стоковых узлах или суперстоке если аналогичная конструкция присутствует в стоках, мы можем определить поток как функцию f:E→R, которая принимает ребро (u,v) из множества ребер графа E и выдает его текущий поток во времени f(u,v), который является положительным вещественным значением.

Изображение автора

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

Чтобы гарантировать прилипание потока к ограничениям сети, он должен удовлетворять двум основным свойствам:

  1. Ограничение пропускной способности: Поток, проходящий через любое ребро, не может превышать его пропускной способности. Формально, если пропускная способность ребра обозначается как “c(u, v)“, а поток через это ребро – “f(u, v)“, то должно выполняться условие 0 ≤ f(u, v) ≤ c(u, v) для всех ребер (u, v) в сети. Проще говоря, мы не можем пропустить больше потока через ребро, чем устанавливает его пропускная способность.
  2. Сохранение потока: В каждом узле (за исключением исходного и стокового узлов) общий входящий поток должен быть равен общему исходящему потоку.
Изображение автора

Это гарантирует непрерывность потока и его отсутствие накопления или рассеивания в сети, хотя вы можете разрешить накопление потока, если ваша система требует этого. Математически, для каждого узла “u” и его соседних узлов, представленных и сгруппированных суперузлами “v и w“, свойство сохранения потока выражается следующим образом:

Свойство сохранения потока (Изображение автора)

Наконец, заметим, что потоки могут компенсировать друг друга, поскольку если потоки f1(u,v) и f2(v,u) существуют между 2 узлами u и v, то уменьшение f1(u,v) эквивалентно увеличению f2(v,u), так как они имеют противоположные направления.

Остаточные сети и дополняющие пути

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

Первое из них – это разница между пропускной способностью ребра и его потоком в определенный момент времени, называемая остаточной пропускной способностью и обозначаемая:

Изображение автора

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

Пример сети с потоко-остаточной сетью (изображение автора)

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

Здесь поток, достигнутый через сеть, можно вычислить с помощью формул источника или стока, как видно ранее, что в данном случае составляет 7 единиц потока, распределенных в 4+3 исходящих единицах от S или, равным образом, 4+1+2 входящих единиц в T. Однако, если мы рассмотрим ребро (v5, v1) в обратном направлении (или двустороннее), есть возможность отправить еще 2 единицы потока вдоль пути S-V1-V5-V4-V3-T, что увеличило бы общий объем потока и стало наибольшим доступным для данной сети. Впоследствии, после получения остаточных сетей, существует возможность того, что в одном или нескольких путях, соединяющих источник с стоком, все ребра имеют остаточную пропускную способность, большую чем 0. Другими словами, есть пути, по которым мы можем перемещать поток из источника в сток, в случае, если источников или стоков несколько.

Иллюстрация увеличивающегося пути (изображение автора)

В этом контексте такие пути лежат в основе алгоритмов, используемых для решения задач максимизации потока или минимизации стоимости, и называются увеличивающими путями. Чтобы понять почему, в приведенной выше сети мы видим, как установленный поток приводит к существованию увеличивающегося пути, по которому может быть передано 2 единицы потока от S к T. Следовательно, фактическая функция потока по сети не обеспечивает максимально-транспортируемый поток через нее, что является одной из проблем, с которыми сталкивается теорема Maxflow Mincut, о которой мы поговорим позже.

Изображение автора

В результате, если мы увеличим поток по отображенному пути, мы сможем обеспечить, что полученный поток будет максимальным со значением 9 единиц, поскольку не будет других путей для увеличения потока в сети. Наконец, перед тем как представить теорему, важно иметь в виду, что для нахождения максимального потока в сети алгоритмы, такие как Форд-Фалкерсон, используют интуитивную процедуру (жадную), которая начинается с остаточной сети без потока и продолжает находить увеличивающиеся пути (с помощью остаточных ребер или потоков в обратном направлении), увеличивая поток в соответствии с этими путями. Таким образом, после того, как больше не остается путей, которые можно обнаружить, увеличивающие поток, можно утверждать, что достигнутый поток является максимальным, то есть нет более быстрого способа перемещения ресурсов от S к T из-за недостатка пропускной способности на некоторых ребрах или даже недостатка ребер в сети.

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

Узкое место (изображение автора)

Например, рассмотрим верхнюю простую сеть потока (остаточную) с только одним доступным улучшающим путем, мы можем ясно определить узкое место компонента ребра (v2, v3), которое устанавливает максимальный поток всего пути (и в данном случае сети) равный 3. После увеличения потока на 3 единицы, как предлагает путь, больше нет улучшающих путей для дальнейшего увеличения потока, поэтому максимальный поток считается достигнутым. Однако, другой способ обеспечить проверку результирующего потока – сосредоточиться на узким местам внутри сети; если каждый путь между S и T имеет нулевое значение узкого места, то есть его максимальная остаточная пропускная способность равна 0, что эквивалентно отсутствию улучшающих путей, больше потока добавить нельзя и текущий поток будет считаться максимальным, как показано выше.

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

Срезы сети потока

Последняя часть, которую мы рассмотрим, касающаяся основ сетей потока, будут срезы, фундаментальный компонент теоремы Maxflow Mincut и ключевая концепция для понимания предыдущих разделов из-за, например, связи между узкими местами и разбиениями сети потока.

Прежде всего, давайте начнем с его определения; срез – это разделение узлов сети, где исходный узел S находится в множестве A, и сток T находится в другом множестве B, непересекающемся с предыдущим.

Изображение от автора

Ни множество A, ни множество B не могут быть пустыми, так как они должны содержать источник(и) и сток(и) соответственно. Поэтому, если сеть связана, будет ребра, выполняющие функцию соединения между узлами A и B в обоих направлениях. Кроме того, эти ребра содержатся в другом множестве, называемом срез-множеством, хотя учитываются только те ребра, исход которых – узел в A, а конец – в B, то есть ребра, способные переносить поток в правильном направлении.

Изображение от автора

Например, выше вы можете увидеть самый простой срез, который мы можем применить к графу, что приводит к разделению множества вершин V как объединение множеств A={S} и B={V1,V2,V3,V4,V5,T}. Поскольку единственный исходный узел сети остается изолированным в одном множестве, мы можем более точно понять концепцию среза и его последующие свойства. Обычно срез представляется в виде линии, которая стремится ограничить одно из двух множеств A или B, неважно. Кроме того, разделяющая граница пересекает несколько ребер, являющихся частью срез-множества, в обоих направлениях. Эти ребра используются для определения потока и пропускной способности среза, которые являются важными компонентами при установлении отношения между произвольным срезом сети и потоком. Это критически важно для доказательства теоремы, представленной в данной статье.

С одной стороны, поток через любой заданный срез определяется как сумма всех ребер, переносящих поток в направлении A-B, минус поток ребер, идущих в противоположном направлении от множества B к A.

Изображение от автора

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

Изображение от автора

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

Изображение от автора

Сначала давайте рассмотрим вершины каждого набора, оставив A={S,V5,V4} и B={V1,V2,V3,T}. Поскольку сеть уже имеет назначенный поток, то поток разреза не будет равен нулю и будет определен суммой потоков на ребрах, связывающих множество A с множеством B.

Изображение от автора

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

Изображение от автора
Разрез (A={S,V2}, B={V1,V5,V3,V4,T}) (Изображение от автора)

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

Изображение от автора

Кроме того, этот пример особенно полезен для понимания связи между разрезами и потоком, предоставляя прочную основу перед рассмотрением теоремы. Сначала следует отметить, что согласно определению разреза, полученная сеть (после разреза) несвязна относительно s-t. Это означает, что пропускная способность такого разреза рассчитывается как сумма всех ребер, ведущих от сборки источника к стоку. В самом базовом случае изоляции единственного источника потока пропускная способность разреза будет превышать или равняться максимальному потоку сети. Однако из предыдущих примеров видно, что с добавлением большего количества узлов с исходящими ребрами пропускная способность разреза неизбежно увеличивается, поскольку ребер больше, чем строго необходимо для достижения максимального потока, то есть ребра источника определяют, в случае узких мест, поток, который впоследствии будет проходить по сети.

Утверждение теоремы

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

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

Изображение от автора

Первый способ заключается в доказательстве вышеуказанного равенства между потоком через любой заданный разрез и общим потоком в сети, который, в свою очередь, соответствует потоку, порождаемому источником. Для этого мы можем считать истинным начальное предположение, применяя метод математической индукции к множеству A любого разреза, с A={S} в качестве базового случая, а затем использовать ранее упомянутый принцип сохранения потока для узлов, отличных от S или T. Но так как это будет сложно объяснить, мы выберем более простой, хоть и очень похожий подход.

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

1- Определение потока: На первом шаге мы начинаем с общего значения потока для любой заданной функции потока f в сети и одного из ее возможных определений. Здесь, имея в качестве опоры узел-источник S, который является наименьшим возможным множеством A для любого разреза сети, мы сопоставляем значение потока потоку, порождаемому S за вычетом входящего потока в S, поскольку иногда может быть определенное количество потока, возвращающегося в S.

Изображение автора

2- Принцип сохранения потока: После рассмотрения сетевого потока как общего потока, порождаемого источником S, мы применяем принцип сохранения потока, согласно которому все узлы, кроме s-t, должны перенаправлять все полученный поток, что приводит к нулевому потоку, внесенному в |f| путем вычитания исходящего потока минус входящий поток. Теперь, если мы возьмем любой разрез (A,B), общий поток, внесенный узлами v в множество A, за исключением того, который порождает поток {S}, будет равен нулю, удовлетворяя ранее упомянутому равенству.

Изображение автора

3- Поток через разрез: Наконец, мы получаем выражение, в котором мы суммируем весь исходящий поток из узлов A, кроме S, во втором слагаемом, и собственный исходящий поток S в первом слагаемом, вычитая соответствующую входящую часть от всех предыдущих узлов. Это соответствует вышеупомянутому определению потока разреза, и, следовательно, мы можем заключить, что весь существующий поток через сеть обязательно будет соответствовать потоку через любой заданный разрез.

Изображение автора

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

Изображение автора

1- Альтернативное определение потока: Используя предыдущий результат относительно потока любого разреза, мы можем сравнить произвольный поток |f| с потоком через произвольный разрез (A,B).

2/3- Ограничение потока: На втором шаге мы устанавливаем неравенство, исключающее второй член, который моделирует входящий поток в множество A, оставляя только исходящий поток ребер, переносящих поток из A в B. После удаления такого члена результат всегда будет больше или равен предыдущему, поскольку если нет ребра, возвращающего поток из B в A, сумма оставшихся реберных потоков от A к B не уменьшится.

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

4- Слабая двойственность: Сопоставив сумму пропускных способностей всех исходящих ребер множества A с пропускной способностью разреза в соответствии с его определением, можно заключить, что для любого заданного потока и разреза в сети поток всегда будет меньше или равен пропускной способности разреза, что является отправной точкой доказываемой нами теоремы. Кроме того, если мы попытаемся максимизировать поток, мы дойдем до точки, которая может быть достигнута путем минимизации пропускной способности разреза, устанавливая слабую двойственную связь, при которой нет гарантии, что минимальная пропускная способность разреза, равная максимальному потоку, всегда будет существовать.

На данном этапе, после достижения слабой двойственности перед теоремой Maxflow Mincut, мы можем сформулировать утверждение, которое легче понять и проверить.

Изображение автора

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

Разрез (A={S,V1}, B={V2,V5,V3,V4,T}) (Изображение автора)

Перед тем, как продолжить его демонстрацию, мы должны подчеркнуть пример использования теоремы. Здесь максимальный поток имеет значение 7, что равно сумме пропускной способности каждого исходящего ребра разреза. Обратите внимание, что эти ребра переносят поток на своей максимальной пропускной способности, что в минимальном разрезе, как показано, вызывает узкое место, то есть сам набор разреза действует как узкое место глобального потока сети. Чтобы сжать объяснение этой идеи, вы найдете ниже ресурс, который поможет вам понять ее:

Какова интуитивная интерпретация теоремы максимального потока и минимального разреза?

Я собираюсь прочитать доказательство теоремы максимального потока и минимального разреза, которая помогает решить проблему максимального потока в сети. Могу…

math.stackexchange.com

Доказательство

Если мы хотим доказать, что максимальный поток в сети равен, во всех случаях, минимальной пропускной способности разреза в сети, мы будем использовать 3 утверждения, которые должны быть эквивалентными для справедливости теоремы.

Существует разрез (A, B), который удовлетворяет условию |f|= cap(A, B).

Значение потока |f| является максимальным.

В потоковой сети нет увеличивающего пути.

Для того чтобы показать, что все утверждения эквивалентны, мы продемонстрируем логические импликации 1⇒2⇒3⇒1. Это означает, что мы можем вывести любое утверждение из любого другого утверждения. В случае 1⇒2, это может быть легко проверено с использованием ранее показанной слабой двойственности. Затем, учитывая, что любой поток меньше разреза с наименьшей пропускной способностью, если мы предположим, что существует поток, равный пропускной способности произвольного разреза (1), слабая двойственность говорит нам, что эта пропускная способность является верхней границей для любого заданного потока и, следовательно, полученный поток, совпадающий с этой границей, является максимальным (2).

Продолжая с 2⇒3, самым простым способом его проверки является взятие контрапозиции ¬3⇒¬2. Затем достаточно взять произвольный поток |f| в качестве примера, в случае, если существовал увеличивающий путь s-t ¬(3), который мог бы переносить поток, |f| мог бы быть увеличен по соответствующему пути, что подразумевает, что |f| изначально не был максимальным потоком ¬(2).

Наконец, самый сложный шаг в этом доказательстве – 3⇒1. Сначала мы начинаем с предположения о потоке |f|, в котором в сети нет увеличивающих путей. Кроме того, мы определяем множество A, содержащее все вершины, достижимые из S в остаточной сети. То есть, A содержит все вершины, к которым существует путь из S в остаточной сети, и в то же время все остаточные ребра этого пути ненулевые. С помощью этих определений мы можем быть уверены, что S находится в A, так как он самодостижим, и так как нет увеличивающих путей, T не достижим в остаточной сети из S, поэтому мы знаем, что по крайней мере один узел (T) не находится в множестве A. Затем, если мы вставим T в другое множество B, то у нас есть пара (A, B), которая удовлетворяет всем критериям для являться допустимым разрезом в сети.

Образец (A={S,V1,V4}, B={T,V2,V3}) разрез (Изображение автора)

На данном этапе, нам нужно осознать две вещи о разрезе (A, B). С одной стороны, поток через разрез в направлении S-T должен быть равен его пропускной способности. Потому что, согласно предыдущим определениям и предположениям (3), единственная возможность, что они не равны, заключается в достижимости узлов B. Таким образом, если хотя бы один из них достижим из S в остаточной сети и вызывает ситуацию, когда поток на ребре разреза не достигает своей полной пропускной способности, то узел должен находиться внутри A вместо B, что является противоречием. С другой стороны, поток в другом направлении разреза оказывается равным нулю по той же причине, то есть, если бы он не был нулевым, в остаточной сети появилось бы ребро в направлении A-B (поток остаточного ребра представлен с отрицательным знаком), которое бы достигло узла в B и вызвало бы противоречие.

Изображение автора

Наконец, остается только сопоставить поток в сети с потоком через разрез, что было продемонстрировано ранее, убрать термин потока в разрезе, так как он нулевой, и использовать определение пропускной способности разреза, чтобы заключить, что поток |f| равен результату пропускной способности разреза (3⇒1).

Применения

Теорема о максимальном потоке и минимальном разрезе имеет многочисленные применения в различных областях. Однако, чтобы сделать это кратко, мы просто упомянем некоторые основные аспекты использования, а также более подробные ресурсы, чтобы помочь вам правильно их понять.

Алгоритмы Форда-Фалкерсона/Эдмондса–Карпа

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

Наиболее значимым из них, и о котором мы уже говорили, является алгоритм Форда-Фалкерсона, жадный подход, который увеличивает поток, ища пути увеличения от s до t. Однако, наиболее простая версия алгоритма не гарантирует завершение или сходимость к максимальному потоку в определенных ситуациях с очень специфичными входными данными (например, при работе с вещественными или иррациональными числами и их представлением) из-за способа выбора путей увеличения. Это также влияет на его временную сложность, которая составляет O(|E| |f|), что означает, что в худшем случае алгоритм должен пройти все ребра сети для каждой (как минимум одной) единицы потока, содержащейся в максимальном потоке.

Затем, с целью улучшения предыдущей версии, которая была первой, созданной для решения задач такого рода, был улучшен способ вычисления путей увеличения. Таким образом, в то время как версия Форда-Фалкерсона использовала поиск в глубину (DFS), который вычисляет случайные пути до T, улучшенная вариант Эдмондса-Карпа реализуется с использованием алгоритма поиска в ширину (BFS) для нахождения путей увеличения. Таким образом, с целью выбора на каждой итерации пути увеличения с наименьшим возможным количеством ребер, алгоритм имеет гарантию завершения по сравнению с предыдущим, а также изменение временной сложности в порядке O(V E²).

Тем не менее, с помощью таких и подобных алгоритмов можно вычислить не только максимальный поток в сети, но и минимальный разрез, пропускная способность которого равна его значению. Процедура довольно проста: после вычисления максимального потока во всех ребрах сети, согласно теореме о максимальном потоке и минимальном разрезе, узлы, доступные из S в соответствующей остаточной сети, образуют множество A искомого разреза, оставшиеся узлы являются B, что приводит к получению минимального разреза пропускной способности (A, B).

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

Практические примеры использования

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

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

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

Заключение

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

https://www.cs.upc.edu/~mjserna/docencia/grauA/P20/MaxFlow-fib.pdf

https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Introduction_to_Network_Flow.pdf