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

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

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

Сеть представляет собой график $G = (V, E)$ , где $V$ представляет собой множество вершин и $Е$ представляет собой набор $V$ ребер «s - подмножество $V \times V$ - вместе с неотрицательной функцией $с : V \times V \to ℝ \infty$ , называемая функцией емкости . Без ограничения общности можно считать, что если $(u, v) \in E,$ то $(v, u)$ также является членом $E$ , так как если $(v, u) \notin E,$ то мы можем добавить $(v, u)$ к E, а затем установить $c (v, u) = 0$ .

Если выделяются два узла в $G$ , источник $s$ и приемник $t$ , то $(G, c, s, t)$ называется потоковой сетью . ^[1]

Потоки [ править ]

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

Псевдо-поток является функция

F : V \times V \to ℝ

, что удовлетворяет следующие два ограничения для всех узлов

¯u

и

V

:

Косая симметрия : кодируйте только чистый поток единиц между парой узлов $u$ и $v$ (см. Интуицию ниже), то есть: $f (u, v) = - f (v, u)$ .
Ограничение пропускной способности : поток дуги не может превышать его пропускную способность, то есть: $f (u, v) \leq c (u, v)$ .

Учитывая псевдопоток $f$ в сети потоков, часто полезно рассматривать чистый поток, входящий в данный узел $v$ , то есть сумму потоков, входящих в $v$ . Избыточная функция $х F : V \to ℝ$ определяются $й F (U) = Σ v \in V F (V, U)$ . Узел $u$ называется активным, если $x f (u)> 0$ , и дефектным, если $x f (u) <0$ или сохраняющий, если $x f (u) = 0$ .

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

Предварительный потоком является псевдо-поток , что для всех

V ∈ V \ { х

}, удовлетворяет дополнительное ограничение:

Недостаточные потоки : чистый поток, входящий в узел $v$ , неотрицателен, за исключением источника, который «производит» поток. То есть: $x f (v) \geq 0$ для всех $v ∈ V \ { s$ }.

Выполнимо поток , или просто поток , является псевдо-поток , что для всех

об ∈ V \ { х , т

}, удовлетворяет дополнительное ограничение:

Сохранение потока : чистый поток, входящий в узел $v,$ равен 0, за исключением источника, который «производит» поток, и стока, который «потребляет» поток. То есть: $x f (v) = 0$ для всех $v ∈ V \ { s , t$ }.

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

Интуиция [ править ]

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

Для любых двух узлов $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 \times V \to ℝ \infty$ , которая не допускает нескольких дуг, начинающихся и заканчивающихся в одних и тех же узлах, достаточна для анализа потока. Кроме того , достаточно наложить перекос симметрии ограничения на функции потока , чтобы обеспечить поток между двумя вершинами кодируются одним числом (указать величину), и знак (для указания направления) - зная поток между $U$ и $V$ вы неявно, через косую симметрию, знаете поток между $v$ и $u$ . Эти упрощения модели не всегда интуитивно понятны, но они удобны, когда приходит время анализировать потоки.

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

Понятия, полезные для решения проблем [ править ]

Остатки [ править ]

Остаточная емкость дуги по отношению к псевдо-потоку $F$ , обозначаемому $с F$ , представляет собой разность между мощностью дуги и ее потоком. То есть $c f (e) = c (e) - f (e)$ . Отсюда мы можем построить остаточную сеть , обозначенную $G f (V, E f)$ , которая моделирует количество доступной мощности на множестве дуг в $G = (V, E)$ . Более формально, для данной потоковой сети $G$ , остаточная сеть $G f$ имеет множество узлов $V$ , множество дуг $E f = {e \in V \times 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 = т$ , и $с ф (у я, у я + 1)> 0$ . Сеть имеет максимальный поток тогда и только тогда, когда в остаточной сети $G f$ нет увеличивающего пути .

Множественные источники и / или поглотители [ править ]

Иногда при моделировании сети с более чем одним источником в граф вводится суперисточник . ^[2] Он состоит из вершины, соединенной с каждым из источников ребрами бесконечной емкости, чтобы действовать как глобальный источник. Подобная конструкция для раковин называется надстройкой . ^[3]

Пример [ править ]

Сеть потоков, показывающая поток и пропускную способность

Слева вы видите потоковую сеть с источником, обозначенным $s$ , стоком $t$ , и четырьмя дополнительными узлами. Обозначается расход и производительность . Обратите внимание, как сеть поддерживает асимметрию, ограничения пропускной способности и сохранение потока. Общий поток от $s$ до $t$ равен 5, что легко увидеть из того факта, что общий исходящий поток от $s$ равен 5, что также является входящим потоком к $t$ . Мы знаем, что ни в одном из других узлов поток не появляется и не исчезает. ${\ displaystyle f / c}$

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

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

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

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

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

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

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

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

Известные алгоритмы задачи о максимальном потоке
Изобретатель (и)	Год	Временная сложность (с $n$ узлами и $m$ дугами)
Алгоритм диника	1969 г.	$O (мин 2)$
Алгоритм Эдмондса – Карпа	1972 г.	$O (м 2 н)$
Алгоритм MPM (Малхотра, Прамод-Кумар и Махешвари) ^[4]	1978 г.	$О (п 3)$
Джеймс Б. Орлин ^[5]	2013	$O (мин)$

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

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

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

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

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

См. Также [ править ]

Парадокс Браесса
Центральность
Алгоритм Форда – Фулкерсона
Алгоритм диника
Flow (компьютерные сети)
Граф потока (значения)
Теорема о максимальном расходе и минимальном разрезе
Ориентированный матроид
Задача кратчайшего пути
Нигде-нулевой поток

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

^ А. В. Гольдберг, Э. Тардос и Р. Е. Тарьян, Алгоритмы сетевого потока, Tech. Отчет STAN-CS-89-1252, кафедра CS Стэнфордского университета, 1989 г.
^ Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Black, Paul E. "Supersource" . Словарь алгоритмов и структур данных .
^ Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Black, Paul E. "Supersink" . Словарь алгоритмов и структур данных .
^ Мальхотра, ВМ; Кумар, М.Прамодх; Махешвари, С. Н. (1978). « Алгоритм поиска максимальных потоков в сетях» (PDF) . Письма об обработке информации . 7 (6): 277–278. DOI : 10.1016 / 0020-0190 (78) 90016-9 . О ( | V | 3 ) {\ Displaystyle O (| V | ^ {3})}
^ Орлин, JB (2013). «Максимальный расход за время O (нм) или лучше» (PDF) . Труды симпозиума по теории вычислений 2013 г .: 765–774. Архивировано в
^ Пинто, ПК; Thiran, P .; Веттерли, М. (2012). «Определение источника распространения в крупномасштабных сетях» (PDF) . Письма с физическим обзором . 109 (6): 068702. arXiv : 1208.2534 . Bibcode : 2012PhRvL.109f8702P . DOI : 10.1103 / PhysRevLett.109.068702 . PMID 23006310 . S2CID 14526887 .

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

Джордж Т. Хейнеман; Гэри Поллис; Стэнли Селкоу (2008). «Глава 8: Алгоритмы сетевого потока». Об алгоритмах в двух словах . Oreilly Media . С. 226–250. ISBN 978-0-596-51624-6.
Равиндра К. Ахуджа , Томас Л. Маньянти и Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения . Прентис Холл. ISBN 0-13-617549-X.CS1 maint: несколько имен: список авторов ( ссылка )
Боллобаш, Бела (1979). Теория графов: вводный курс . Гейдельберг: Springer-Verlag. ISBN 3-540-90399-2.
Чартран, Гэри и Оеллерманн, Ортруд Р. (1993). Прикладная и алгоритмическая теория графов . Нью-Йорк: Макгроу-Хилл. ISBN 0-07-557101-3.CS1 maint: несколько имен: список авторов ( ссылка )
Эвен, Шимон (1979). Графические алгоритмы . Роквилл, Мэриленд: Computer Science Press. ISBN 0-914894-21-8.
Гиббонс, Алан (1985). Алгоритмическая теория графов . Кембридж: Издательство Кембриджского университета. ISBN 0-521-28881-9.
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2001) [1990]. «26». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 696–697. ISBN 0-262-03293-7.CS1 maint: несколько имен: список авторов ( ссылка )

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме поточных сетей .

Проблема максимального расхода
Реальные экземпляры графа
Библиотека Lemon C ++ с несколькими алгоритмами обращения с максимальным потоком и минимальной стоимостью
QuickGraph , графические структуры данных и алгоритмы для .Net

[1] А. В. Гольдберг, Э. Тардос и Р. Е. Тарьян, Алгоритмы сетевого потока, Tech. Отчет STAN-CS-89-1252, кафедра CS Стэнфордского университета, 1989 г.

[2] Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Black, Paul E. "Supersource" . Словарь алгоритмов и структур данных .

[3] Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Black, Paul E. "Supersink" . Словарь алгоритмов и структур данных .

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

[5] Орлин, JB (2013). «Максимальный расход за время O (нм) или лучше» (PDF) . Труды симпозиума по теории вычислений 2013 г .: 765–774. Архивировано в

[6] Пинто, ПК; Thiran, P .; Веттерли, М. (2012). «Определение источника распространения в крупномасштабных сетях» (PDF) . Письма с физическим обзором . 109 (6): 068702. arXiv : 1208.2534 . Bibcode : 2012PhRvL.109f8702P . DOI : 10.1103 / PhysRevLett.109.068702 . PMID 23006310 . S2CID 14526887 .

[1]