В теории графов, потоковая сеть (также известная как транспортная сеть ) представляет собой ориентированный граф, в котором каждое ребро имеет пропускную способность, и каждое ребро принимает поток. Количество потока на кромке не может превышать пропускную способность кромки. Часто в исследовании операций ориентированный граф называется сетью, вершины называются узлами, а ребра называются дугами . Поток должен удовлетворять ограничению, согласно которому объем потока в узел равен количеству потока из него, если только это не источник, который имеет только исходящий поток, или приемник, который имеет только входящий поток. Сеть может использоваться для моделирования трафика в компьютерной сети, циркуляции с потребностями, жидкостей в трубах, токов в электрической цепи или чего-либо подобного, в котором что-то перемещается через сеть узлов.
A сеть - это граф G = (V, E), где V - множество вершин, а E - множество ребер V - подмножество V × V - вместе с неотрицательной функцией c: V × V → ℝ ∞, называется функцией емкости . Без ограничения общности, мы можем считать, что если (u, v) ∈ E, то (v, u) также является членом E, поскольку если (v, u) ∉ E, то мы можем добавить ( v, u) равным E, а затем установите c (v, u) = 0.
Если два узла в G различаются, источник s и приемник t, то (G, c, s, t) называется потоковой сетью .
Существуют различные понятия потоковой функции, которые могут быть определены в потоковом графе. Функции потока моделируют чистый поток единиц между парами узлов и полезны, когда задаются такие вопросы, как какое максимальное количество единиц может быть передано из исходного узла s в приемный узел t? Простейший пример функции потока известен как псевдопоток.
. Учитывая псевдопоток f в потоковой сети, часто бывает полезно рассмотреть чистый поток, входящий в данный узел v, что есть сумма потоков, входящих в v. Функция превышения x f : V → ℝ определяется как x f (u) = ∑ v ∈ V f (v, u). Узел u называется активным, если x f (u)>0, дефицитным, если x f (u) <0 или сохранение, если x f (u) = 0.
Эти окончательные определения приводят к двум усилениям определения псевдопотока:
. значение допустимого потока f, обозначенное | f |, - чистый поток в сток t сети потоков. То есть | f | = х f (т).
В контексте анализа потока интерес представляет только рассмотрение того, как единицы передаются между узлами в целостном смысле. Другими словами, нет необходимости различать несколько дуг между парой узлов:
Для этого По этой причине функция пропускной способности c: V × V → ℝ ∞, которая не допускает множественных дуг, начинающихся и заканчивающихся в одних и тех же узлах, достаточна для анализа потока. Точно так же достаточно наложить ограничение асимметрии на функции потока, чтобы гарантировать, что поток между двумя вершинами кодируется одним числом (для указания величины) и знаком (для указания направления) - зная поток между u и v. вы неявно, через косую симметрию, знаете поток между v и u. Эти упрощения модели не всегда интуитивно понятны, но они удобны, когда приходит время анализировать потоки.
Ограничение пропускной способности просто гарантирует, что поток на любой одной дуге в сети не может превышать пропускную способность этой дуги.
остаточная пропускная способность дуги относительно псевдопотока f, обозначенная c f - разница между мощностью дуги и ее потоком. То есть c f (e) = c (e) - f (e). Из этого мы можем построить остаточную сеть, обозначенную G f (V, E f), которая моделирует количество доступной мощности на множестве дуг в G = (V, E). Более формально, для данной потоковой сети G, остаточная сеть G f имеет множество узлов V, множество дуг E f = {e ∈ V × V: c f (e)>0} и функция пропускной способности c f.
Эта концепция используется в алгоритме Форда – Фулкерсона, который вычисляет максимальный поток в сети потоков.
Обратите внимание, что в остаточной сети может быть путь от u до v, даже если в исходной сети нет пути от u к v. Поскольку потоки в противоположных направлениях компенсируются, уменьшение потока от v к u аналогично увеличению потока от u к v.
Расширение пути - путь (u 1, u 2,..., u k) в остаточной сети, где u 1 = s, u k = t и c f(ui, u i + 1)>0. Сеть имеет максимальный поток тогда и только тогда, когда нет расширяющего пути в остаточной сети G f.
Иногда при моделировании сети с более чем один источник, на график вводится надисточник . Он состоит из вершины, соединенной с каждым из источников ребрами бесконечной емкости, чтобы действовать как глобальный источник. Аналогичная конструкция для стоков называется надводкой .
Слева вы видите потоковую сеть с источником, помеченным s, сток t, и четырьмя дополнительными узлами. Расход и пропускная способность обозначены . Обратите внимание, как сеть поддерживает асимметрию, ограничения пропускной способности и сохранение потока. Общий поток от s до t равен 5, что легко увидеть из того факта, что общий исходящий поток от s равен 5, что также является входящим потоком к t. Мы знаем, что ни в одном из других узлов поток не появляется и не исчезает.
Остаточная сеть для вышеупомянутой сети потоков, показывающая остаточные мощности.Ниже вы видите остаточную сеть для данного потока. Обратите внимание на положительную остаточную пропускную способность на некоторых ребрах, где исходная пропускная способность равна нулю, например, для ребра . Этот поток не является максимальным потоком . На путях имеется доступная емкость , и , которые затем являются дополнительными путями. Остаточная емкость первого пути . Обратите внимание, что пока существует некоторый путь с положительной остаточной пропускной способностью, поток не будет максимальным. Остаточная пропускная способность для некоторого пути - это минимальная остаточная пропускная способность всех ребер в этом пути.
Вообразите серию водопроводных труб, входящих в сеть. Каждая труба имеет определенный диаметр, поэтому она может поддерживать поток только определенного количества воды. Везде, где встречаются трубы, общее количество воды, поступающей в это соединение, должно быть равно количеству выходящей воды, иначе у нас быстро закончится вода, или у нас будет скопление воды. У нас есть вход для воды, который является источником, и выход - раковина. Тогда поток будет одним из возможных способов попадания воды из источника в сток, чтобы общее количество воды, выходящей из выпускного отверстия, было постоянным. Интуитивно понятно, что общий поток в сети - это скорость, с которой вода выходит из выпускного отверстия.
Потоки могут относиться к людям или материалам по транспортным сетям или к электричеству по системам распределения. Для любой такой физической сети поток, входящий в любой промежуточный узел, должен быть равен потоку, выходящему из этого узла. Это ограничение сохранения эквивалентно действующему закону Кирхгофа.
Поточные сети также находят применение в экологии : потоковые сети возникают естественным образом при рассмотрении потока питательных веществ и энергии между различными организмами в корме. Интернет. Математические проблемы, связанные с такими сетями, сильно отличаются от тех, которые возникают в сетях с жидкостями или потоками трафика. Область сетевого анализа экосистемы, разработанная Робертом Улановичем и другими, включает использование концепций из теории информации и термодинамики для изучения эволюции этих сетей во времени.
Самая простая и наиболее распространенная проблема с использованием потоковых сетей - найти так называемый максимальный поток, который обеспечивает максимально возможный общий поток из источника. в сток в данном графе. Есть много других проблем, которые могут быть решены с использованием алгоритмов максимального потока, если они соответствующим образом смоделированы как потоковые сети, такие как двустороннее сопоставление, проблема назначения и проблема транспортировки.. Проблемы максимального потока могут быть эффективно решены с помощью алгоритма переназначения на передний план. Теорема о максимальном потоке и минимальном отсечении утверждает, что нахождение максимального сетевого потока эквивалентно нахождению отсечки минимальной пропускной способности, разделяющей источник и приемник, где отрезок - это разделение таких вершин, что источник находится в одном подразделении, а сток - в другом.
Inventor(s) | Год | Время. сложность. (с n узлами. и m дугами) |
---|---|---|
алгоритм Динича | 1969 | O (mn) |
алгоритм Эдмондса – Карпа | 1972 | O (mn) |
MPM (Malhotra, Pramodh- Кумар и Махешвари). алгоритм | 1978 | O (n) |
Джеймс Б. Орлин | 2013 | O (mn) |
В проблема потоков нескольких товаров, у вас есть несколько источников и приемников, а также различные «товары», которые должны течь из заданного источника в заданный приемник. Это могут быть, например, различные товары, которые производятся на разных заводах и которые должны быть доставлены различным потребителям через одну и ту же транспортную сеть.
В задаче потока минимальных затрат каждое ребро имеет заданную стоимость , и стоимость отправки потока по краю находится . Цель состоит в том, чтобы направить заданное количество потока из источника в сток по минимально возможной цене.
В проблеме обращения у вас есть нижняя граница на ребра, помимо верхней границы . У каждого ребра также есть стоимость. Часто сохранение потока выполняется для всех узлов в проблеме циркуляции, и существует обратная связь от стока к источнику. Таким образом, вы можете указать общий поток с помощью и . Поток циркулирует по сети, отсюда и название проблемы.
В сети с коэффициентами усиления или обобщенной сети каждое ребро имеет коэффициент усиления, действительное число (не ноль) такой, что, если на ребре есть усиление g, и величина x течет в край на его хвосте, то величина gx течет в головке.
В задаче локализации источника алгоритм пытается идентифицировать наиболее вероятный узел источника распространения информации через частично наблюдаемую сеть. Это может быть сделано в линейном времени для деревьев и кубическом времени для произвольных сетей и имеет различные приложения: от отслеживания пользователей мобильных телефонов до определения источника вспышек заболеваний.
На Викискладе есть материалы, относящиеся к Потоковым сетям. |