Поточная сеть

редактировать

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

Содержание

  • 1 Определение
  • 2 Потоки
  • 3 Интуиция
  • 4 Концепции, полезные для задач потоков
    • 4.1 Остаточные остатки
    • 4.2 Расширение путей
    • 4.3 Множественные источники и / или приемники
  • 5 Пример
  • 6 Приложения
  • 7 Классификация проблем потока
  • 8 См. Также
  • 9 Ссылки
  • 10 Дополнительная литература
  • 11 Внешние ссылки

Определение

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? Простейший пример функции потока известен как псевдопоток.

A псевдопоток - это функция f: V × V → ℝ, которая удовлетворяет следующим двум ограничениям для всех узлов u и v:
  • Асимметрия: кодировать только чистый поток единиц между пара узлов u и v (см. интуицию ниже), то есть: f (u, v) = −f (v, u).
  • Ограничение пропускной способности: поток дуги не может превышать его пропускная способность, то есть: f (u, v) ≤ c (u, v).

. Учитывая псевдопоток 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.

Эти окончательные определения приводят к двум усилениям определения псевдопотока:

A pre- flow - это псевдопоток, который для всех v ∈ V \ {s} удовлетворяет дополнительному ограничению:
  • Недефицитные потоки: чистый поток, входящий в узел v, неотрицателен, за исключением для источника, который «производит» поток. То есть: x f (v) ≥ 0 для всех v ∈ V \ {s}.
A допустимый поток, или просто поток, является псевдо- поток, который для всех v ∈ V \ {s, t} удовлетворяет дополнительному ограничению:
  • Сохранение потока: чистый поток, входящий в узел v, равен 0, за исключением источника, который «производит» поток, и раковина, которая «потребляет» поток. То есть: x f (v) = 0 для всех v ∈ V \ {s, t}.

. значение допустимого потока f, обозначенное | f |, - чистый поток в сток t сети потоков. То есть | f | = х f (т).

Интуиция

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

  • Для любых двух узлов u и v, если есть две дуги от u до v с мощностью 5 и 3 соответственно, это эквивалентно рассмотрению только одна дуга между u и v с емкостью 8 - полезно знать только то, что 8 единиц могут быть перенесены из u в v, а не то, как они могут быть перенесены.
  • Опять же, учитывая два узла u и v, если существует поток из 5 единиц от u до v и другой поток из 3 единиц от v до u, это эквивалентно чистому потоку в 2 единицы от u до v или чистому потоку −2 единицы от v до u (знак указывает направление) - полезно знать только то, что чистый поток из 2 единиц будет течь между u и v, и направление, в котором они будут течь, а не то, как этот чистый поток достигается.

Для этого По этой причине функция пропускной способности 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, и четырьмя дополнительными узлами. Расход и пропускная способность обозначены f / c {\ displaystyle f / c}f / c . Обратите внимание, как сеть поддерживает асимметрию, ограничения пропускной способности и сохранение потока. Общий поток от s до t равен 5, что легко увидеть из того факта, что общий исходящий поток от s равен 5, что также является входящим потоком к t. Мы знаем, что ни в одном из других узлов поток не появляется и не исчезает.

Остаточная сеть для вышеупомянутой сети потоков, показывающая остаточные мощности.

Ниже вы видите остаточную сеть для данного потока. Обратите внимание на положительную остаточную пропускную способность на некоторых ребрах, где исходная пропускная способность равна нулю, например, для ребра (d, c) {\ displaystyle (d, c)}( d, c) . Этот поток не является максимальным потоком . На путях имеется доступная емкость (s, a, c, t) {\ displaystyle (s, a, c, t)}(s, a, c, t) , (s, a, b, d, t) {\ displaystyle ( s, a, b, d, t)}(s, a, b, d, t) и (s, a, b, d, c, t) {\ displaystyle (s, a, b, d, c, t) }(s, a, b, d, c, t) , которые затем являются дополнительными путями. Остаточная емкость первого пути min (c (s, a) - f (s, a), c (a, c) - f (a, c), c (c, t) - f ( с, t)) {\ Displaystyle \ мин (с (s, а) -f (s, а), с (а, с) -f (а, с), с (с, т) -f (с, t))}\ min (c (s, a) -f (s, a), c (a, c) -f ( a, c), c (c, t) -f (c, t)) = min (5 - 3, 3 - 2, 2 - 1) = min (2, 1, 1) = 1 {\ displaystyle = \ min (5-3,3-2,2- 1) = \ min (2,1,1) = 1}= \ min (5-3,3-2,2-1) = \ min (2,1, 1) = 1 . Обратите внимание, что пока существует некоторый путь с положительной остаточной пропускной способностью, поток не будет максимальным. Остаточная пропускная способность для некоторого пути - это минимальная остаточная пропускная способность всех ребер в этом пути.

Приложения

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

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

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

Классификация проблем потока

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

Хорошо известные алгоритмы для задачи о максимальном потоке
Inventor(s)ГодВремя. сложность. (с n узлами. и m дугами)
алгоритм Динича 1969O (mn)
алгоритм Эдмондса – Карпа 1972O (mn)
MPM (Malhotra, Pramodh- Кумар и Махешвари). алгоритм1978O (n)
Джеймс Б. Орлин 2013O (mn)

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

В задаче потока минимальных затрат каждое ребро u, v {\ displaystyle u, v}u, v имеет заданную стоимость k (u, v) {\ displaystyle k (u, v)}k (u, v) , и стоимость отправки потока f (u, v) {\ displaystyle f (u, v)}f (u, v) по краю находится f (u, v) ⋅ k (u, v) {\ displaystyle f (u, v) \ cdot k (u, v)}f (u, v) \ cdot k (u, v) . Цель состоит в том, чтобы направить заданное количество потока из источника в сток по минимально возможной цене.

В проблеме обращения у вас есть нижняя граница ℓ (u, v) {\ displaystyle \ ell (u, v)}{\ displaystyle \ ell (u, v)} на ребра, помимо верхней границы c (u, v) {\ displaystyle c (u, v)}c (u, v) . У каждого ребра также есть стоимость. Часто сохранение потока выполняется для всех узлов в проблеме циркуляции, и существует обратная связь от стока к источнику. Таким образом, вы можете указать общий поток с помощью ℓ (t, s) {\ displaystyle \ ell (t, s)}{\ displaystyle \ ell (t, s)} и c (t, s) {\ displaystyle c (t, s)}c (t, s) . Поток циркулирует по сети, отсюда и название проблемы.

В сети с коэффициентами усиления или обобщенной сети каждое ребро имеет коэффициент усиления, действительное число (не ноль) такой, что, если на ребре есть усиление g, и величина x течет в край на его хвосте, то величина gx течет в головке.

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

См. Также

Ссылки

Дополнительная литература

Внешняя ссылка s

На Викискладе есть материалы, относящиеся к Потоковым сетям.
Последняя правка сделана 2021-05-20 09:22:03
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте