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

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

Определение

Сеть для каждого ребра и без кратных дуг (т. е . представляет собой ориентированный граф $G = (V, E)$ с неотрицательной пропускной способности функцией $c$ ребер с одинаковыми исходными и целевыми узлами). Без ограничения общности мы можем предположить, что если $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? Объем потока между двумя узлами используется для представления чистого количества единиц, передаваемых с одного узла на другой.

Функция эксцесса $\mathbb {R}$ представляет чистый поток, входящий в данный узел $u$ (т.е. сумму потоков, входящих в $u$ ), и определяется выражением $x_{f}(u)=\sum _{w\in V}f(w,u).$ Узел $u$ называется активным , если $x f (u) > 0$ (т. е. узел $u$ потребляет поток), недостаточным , если $x f (u) < 0$ (т. е. узел $u$ производит поток), или сохраняющимся , если $x f (u) = 0$ . В проточных сетях источник $s$ недостаточен, а приемник $t$ активен.Псевдопотоки, допустимые потоки и предварительные потоки — все это примеры функций потока.

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

f

каждого ребра в сети, которая удовлетворяет следующим двум ограничениям для всех

u

и

v

:

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

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

v ∈ V \{ s

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

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

, Допустимый поток или просто поток , — это псевдопоток, который для всех

v ∈ V \{ s , t

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

Ограничение сохранения потока : общий чистый поток, входящий в узел $v,$ равен нулю для всех узлов в сети, кроме источника. $s$ и раковина $t$ , то есть: $x f (v) = 0$ для всех $v ∈ V \ { s , t }$ . Другими словами, для всех узлов сети, кроме источника $s$ и раковина $t$ , общая сумма входящего потока узла равна его исходящему потоку (т.е. $\sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)$ , для каждой вершины $v ∈ V \{ s , t }$ ).

Значение $| ж |$ допустимого потока $f$ для сети — это чистый поток в сток $t$ проточной сети, то есть: $| ж | знак равно Икс ж (т)$ . Отметим, что величина потока в сети также равна суммарному исходящему потоку источника $s$ , то есть: $| ж | = - Икс ж (s)$ . Кроме того, если мы определим $A$ как набор узлов в $G$ таких, что $s \in A$ и $t \notin A$ , значение потока будет равно общему чистому потоку, исходящему из A (т.е. $| f | = f вне (А) - ж в (А)$ ). ^[2] Значение потока в сети — это общий объем потока от $s$ до $t$ .

Концепции, полезные для решения проблем

Разложение потока

Разложение потока ^[3] — это процесс разбиения заданного потока на совокупность потоков путей и потоков циклов. Каждый поток через сеть можно разложить на один или несколько путей и соответствующих величин, так что каждое ребро в потоке равно сумме всех количеств путей, проходящих через него. Декомпозиция потока является мощным инструментом в задачах оптимизации, позволяющим максимизировать или минимизировать определенные параметры потока.

Добавление дуг и потоков

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

Для любых двух узлов $u$ и $v$ наличие двух дуг от $u$ до $v$ с пропускными способностями $c 1 (u,v)$ и $c 2 (u,v)$ соответственно эквивалентно рассмотрению только одной дуги от $u$ до $v$ с пропускной способностью, равной $c 1 (u,v)+c 2 (u,v)$ .
Для любых двух узлов $u$ и $v$ наличие двух дуг от $u$ до $v$ с псевдопотоками $f 1 (u,v)$ и $f 2 (u,v)$ соответственно эквивалентно рассмотрению только одной дуги от $u$ до $v$ с псевдопотоками -поток равен $f 1 (u,v)+f 2 (u,v)$ .

Наряду с другими ограничениями на этом этапе необходимо помнить об ограничении косой симметрии, чтобы сохранить направление исходной дуги псевдопотока. Добавление потока к дуге аналогично добавлению дуги с нулевой пропускной способностью. ^{[ нужна ссылка ]}

Остатки

Остаточная пропускная способность дуги $e$ по отношению к псевдопотоку $f$ обозначается $c f$ и представляет собой разницу между пропускной способностью дуги и ее потоком. То есть $c f (e) = c (e) - f (e)$ . этого мы можем построить остаточную сеть , обозначенную $Gf пропускной способности на (V, Ef Из)$ , с функцией пропускной способности $cf,$ которая моделирует количество доступной множестве дуг в $G = (V, E)$ . Более конкретно, функция пропускной способности $c f$ каждой дуги $(u, v)$ в остаточной сети представляет собой объем потока, который может быть передан от $u$ к $v$ с учетом текущего состояния потока внутри сети.

Эта концепция используется в алгоритме Форда – Фулкерсона , который вычисляет максимальный поток в проточной сети.

Обратите внимание, что в остаточной сети может существовать ненасыщенный путь (путь с доступной пропускной способностью) от $u$ до $v$ нет . $такого пути от u$ до $v$ , даже если в исходной сети ^{[ нужна ссылка ]} Поскольку потоки в противоположных направлениях компенсируются, уменьшение потока от $v$ к $u$ равносильно увеличению потока от $u$ к $v$ .

Расширение путей

Дополняющий путь — это путь $(u 1, u 2, ..., uk в)$ остаточной сети, где $u 1 = s$ , $uk для = t$ , и $всех u i, u i + 1 (c f (ты я, ты я + 1) > 0) (1 \leq я < k)$ . Проще говоря, увеличивающий путь — это доступный путь потока от источника к приемнику. Сеть имеет максимальный поток нет расширяющего пути $тогда и только тогда, когда в остаточной сети G f$ .

Узким местом является минимальная остаточная пропускная способность всех ребер на данном увеличивающем пути. ^[2] См. пример, описанный в разделе «Пример» этой статьи. Проточная сеть находится в максимальном потоке тогда и только тогда, когда в ней имеется узкое место со значением, равным нулю. Если существует какой-либо расширяющий путь, его вес узкого места будет больше 0. Другими словами, если существует значение узкого места больше 0, то существует расширяющий путь от источника к приемнику. Однако мы знаем, что если существует какой-либо расширяющий путь, то сеть не находится на максимальном потоке, что, в свою очередь, означает, что если значение узкого места больше 0, то сеть не находится на максимальном потоке.

Термин «увеличение потока» для расширяющего пути означает обновление потока $f$ каждой дуги в этом увеличивающем пути, чтобы он стал равным пропускной способности $c$ узкого места. Увеличение потока соответствует проталкиванию дополнительного потока по пути увеличения до тех пор, пока в узком месте не останется доступной остаточной мощности.

Множественные источники и/или стоки

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

Пример

На рисунке 1 вы видите потоковую сеть с источником, обозначенным $s$ , приемником $t$ и четырьмя дополнительными узлами. Расход и емкость обозначаются $f/c$ . Обратите внимание, как сеть поддерживает ограничение пропускной способности и ограничение сохранения потока. Общий объем потока от $s$ до $t$ равен 5, что легко увидеть из того факта, что общий исходящий поток от $s$ равен 5, что также является входящим потоком к $t$ . Согласно ограничению косой симметрии, путь от $c$ к $a$ равен -2, потому что поток от $a$ к $c$ равен 2.

На рисунке 2 вы видите остаточную сеть для того же потока. Обратите внимание, что на некоторых ребрах, где исходная емкость равна нулю на рисунке 1, имеется положительная остаточная емкость, например для ребра. $(d,c)$ . Эта сеть не находится на максимальном потоке . На путях имеются свободные мощности $(s,a,c,t)$ , $(s,a,b,d,t)$ и $(s,a,b,d,c,t)$ , которые тогда являются дополняющими путями.

Узкое место $(s,a,c,t)$ путь равен $\min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))$ $=\min(c_{f}(s,a),c_{f}(a,c),c_{f}(c,t))$ $=\min(5-3,3-2,2-1)$ $=\min(2,1,1)=1$ .

Приложения

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

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

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

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

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

Известные алгоритмы решения задачи максимального потока
Изобретатель(и)	Год	Время сложность (с $n$ узлами и $m$ дуг)
Алгоритм Динича	1970	$О (мин 2)$
Алгоритм Эдмондса – Карпа	1972	$О (м 2 п)$
MPM (Малхотра, Прамод-Кумар и Махешвари) алгоритм ^[6]	1978	$На 3)$
Алгоритм push-relabel ( Goldberg & Tarjan )	1988	$На 2 м)$
Джеймс Б. Орлин ^[7]	2013	$О (мин)$
Ли Чен, Расмус Кинг, Ян П. Лю, Ричард Пэн, Максимилиан Пробст Гутенберг,Сушант Сачдева	2022	$O(m^{1+o(1)})$

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

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

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

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

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

См. также

Ссылки

^ А.В. Гольдберг, Э. Тардос и Р.Э. Тарьян, Алгоритмы сетевых потоков, Tech. Отчет STAN-CS-89-1252, кафедра CS Стэнфордского университета, 1989 г.
^ Jump up to: ^а ^б Кляйнберг, Джон (2011). Алгоритм проектирования . Ева Тардос (2-е изд.). Бостон, Массачусетс: Аддисон-Уэсли. стр. 342, 346. ISBN. 978-0-13-213108-7 . OCLC 796210667 .
^ Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Энглвуд Клиффс (Нью-Джерси): Прентис Холл. ISBN 978-0-13-617549-0 .
^ В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Суперисточник» . Словарь алгоритмов и структур данных . НИСТ .
^ В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Суперсинк» . Словарь алгоритмов и структур данных . НИСТ .
^ Малхотра, В.М.; Кумар, М. Прамод; Махешвари, С.Н. (1978). «Ан $O(|V|^{3})$ алгоритм поиска максимальных потоков в сетях» (PDF) . Information Processing Letters . 7 (6): 277–278. doi : 10.1016/0020-0190(78)90016-9 . Архивировано (PDF) из оригинала 04.2021 г. -18 Проверено 11 июля 2019 г.
^ Орлин, Джеймс Б. (01 июня 2013 г.). «Максимальный поток протекает за время O(нм) или лучше» . Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . СТОК '13. Пало-Альто, Калифорния, США: Ассоциация вычислительной техники. стр. 765–774. дои : 10.1145/2488608.2488705 . hdl : 1721.1/88020 . ISBN 978-1-4503-2029-0 . S2CID 207205207 .
^ Пинто, ПК; Тиран, П.; Веттерли, М. (2012). «Обнаружение источника распространения в крупномасштабных сетях» (PDF) . Письма о физических отзывах . 109 (6): 068702. arXiv : 1208.2534 . Бибкод : 2012PhRvL.109f8702P . doi : 10.1103/PhysRevLett.109.068702 . ПМИД 23006310 . S2CID 14526887 . Архивировано (PDF) из оригинала 22 октября 2012 г. Проверено 14 августа 2012 г.

Дальнейшее чтение

Джордж Т. Хайнеман; Гэри Поллис; Стэнли Селков (2008). «Глава 8: Алгоритмы сетевых потоков». Коротко об алгоритмах . Орейли Медиа . стр. 226–250. ISBN 978-0-596-51624-6 .
Равиндра К. Ахуджа ; Томас Л. Маньянти ; Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения . Прентис Холл. ISBN 0-13-617549-Х .
Боллобас, Бела (1979). Теория графов: вводный курс . Гейдельберг: Springer-Verlag. ISBN 3-540-90399-2 .
Шартран, Гэри ; Оллерманн, Ортруда Р. (1993). Прикладная и алгоритмическая теория графов . Нью-Йорк: МакГроу-Хилл. ISBN 0-07-557101-3 .
Эвен, Шимон (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 .

Внешние ссылки

Задача о максимальном потоке
Реальные экземпляры графа
Библиотека Lemon C++ с несколькими алгоритмами циркуляции максимального потока и минимальной стоимости.
QuickGraph. Архивировано 21 января 2018 г. на Wayback Machine , графические структуры данных и алгоритмы для .Net.

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

[:0-2] Jump up to: ^а ^б Кляйнберг, Джон (2011). Алгоритм проектирования . Ева Тардос (2-е изд.). Бостон, Массачусетс: Аддисон-Уэсли. стр. 342, 346. ISBN. 978-0-13-213108-7 . OCLC 796210667 .

[3] Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Энглвуд Клиффс (Нью-Джерси): Прентис Холл. ISBN 978-0-13-617549-0 .

[4] В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Суперисточник» . Словарь алгоритмов и структур данных . НИСТ .

[5] В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Суперсинк» . Словарь алгоритмов и структур данных . НИСТ .

[6] Малхотра, В.М.; Кумар, М. Прамод; Махешвари, С.Н. (1978). «Ан $O(|V|^{3})$ алгоритм поиска максимальных потоков в сетях» (PDF) . Information Processing Letters . 7 (6): 277–278. doi : 10.1016/0020-0190(78)90016-9 . Архивировано (PDF) из оригинала 04.2021 г. -18 Проверено 11 июля 2019 г.

[7] Орлин, Джеймс Б. (01 июня 2013 г.). «Максимальный поток протекает за время O(нм) или лучше» . Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . СТОК '13. Пало-Альто, Калифорния, США: Ассоциация вычислительной техники. стр. 765–774. дои : 10.1145/2488608.2488705 . hdl : 1721.1/88020 . ISBN 978-1-4503-2029-0 . S2CID 207205207 .

[8] Пинто, ПК; Тиран, П.; Веттерли, М. (2012). «Обнаружение источника распространения в крупномасштабных сетях» (PDF) . Письма о физических отзывах . 109 (6): 068702. arXiv : 1208.2534 . Бибкод : 2012PhRvL.109f8702P . doi : 10.1103/PhysRevLett.109.068702 . ПМИД 23006310 . S2CID 14526887 . Архивировано (PDF) из оригинала 22 октября 2012 г. Проверено 14 августа 2012 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]