Сеть потоков

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

Определение

Сеть — это направленный граф $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? Величина потока между двумя узлами используется для представления чистого количества единиц, передаваемых из одного узла в другой.

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

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

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

Значение $|$ $f$ $|$ допустимого потока $f$ для сети — это чистый поток в сток $t$ сети потоков, то есть: | $f$ $|$ $=$ $x$ $f$ $($ $t$ $)$ . Обратите внимание, что значение потока в сети также равно общему исходящему потоку источника $s$ , то есть: $|$ $f$ $| = -$ $x$ $f$ $($ $s$ $)$ . Кроме того, если мы определим $A$ как набор узлов в $G,$ таких что $s$ $\in$ $A$ и $t$ $\notin$ $A$ , значение потока равно общему чистому потоку, исходящему из A (то есть $|$ $f$ $| =$ $f$ $out$ $($ $A$ $) -$ $f$ $in$ $($ $A$ $)$ ). ^[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)$ . Из этого мы можем построить остаточную сеть , обозначенную $G f (V, E f)$ , с функцией емкости $c f ,$ которая моделирует объем доступной емкости на множестве дуг в $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 , и для всех ui ,$ $ui$ $+$ $1$ $($ c $f (u i$ , $ui + 1$ ) $>$ $0) (1 \leq i < k) . Проще говоря, увеличивающий путь —$ это доступный путь потока от источника к приемнику. Сеть находится на максимальном потоке тогда и только тогда, когда в остаточной сети $G f$ нет увеличивающего пути .

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

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

Несколько источников и/или приемников

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

Пример

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

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

Узкое место пути равно . $(с,а,к,т)$ $\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$

Приложения

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

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

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

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

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

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

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

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

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

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

Смотрите также

Ссылки

^ А. В. Голдберг, Э. Тардос и Р. Э. Тарьян, Алгоритмы сетевых потоков, Технический отчет STAN-CS-89-1252, Стэнфордский университет, кафедра вычислительной техники, 1989
^ Аб Кляйнберг, Джон (2011). Алгоритм проектирования. Ева Тардос (2-е изд.). Бостон, Массачусетс: Аддисон-Уэсли. стр. 342, 346. ISBN. 978-0-13-213108-7. OCLC 796210667.
^ Ахуджа, Равиндра К.; Магнанти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Энглвуд Клиффс (Нью-Джерси): Prentice Hall. ISBN 978-0-13-617549-0.
^ В этой статье использованы материалы, находящиеся в открытом доступе, от Пола Э. Блэка. "Supersource". Словарь алгоритмов и структур данных . NIST .
^ В этой статье использованы материалы, находящиеся в открытом доступе, от Пола Э. Блэка. "Supersink". Словарь алгоритмов и структур данных . NIST .
^ Malhotra, VM; Kumar, M.Pramodh; Maheshwari, SN (1978). "Алгоритм O ( | V | 3 ) {\displaystyle O(|V|^{3})} для поиска максимальных потоков в сетях" (PDF) . Information Processing Letters . 7 (6): 277–278. doi :10.1016/0020-0190(78)90016-9. Архивировано (PDF) из оригинала 2021-04-18 . Получено 2019-07-11 .
^ Орлин, Джеймс Б. (2013-06-01). "Max flow in O(nm) time, or better". Труды сорок пятого ежегодного симпозиума ACM по теории вычислений . STOC '13. Пало-Альто, Калифорния, США: Ассоциация вычислительной техники. стр. 765–774. doi :10.1145/2488608.2488705. hdl : 1721.1/88020 . ISBN 978-1-4503-2029-0. S2CID 207205207.
^ Pinto, PC; Thiran, P.; Vetterli, M. (2012). "Locating the source of diffusion in large-scale networks" (PDF) . Physical Review Letters . 109 (6): 068702. arXiv : 1208.2534 . Bibcode :2012PhRvL.109f8702P. doi :10.1103/PhysRevLett.109.068702. PMID 23006310. S2CID 14526887. Архивировано (PDF) из оригинала 2012-10-22 . Получено 2012-08-14 .

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

Джордж Т. Хайнеман; Гэри Поллис; Стэнли Селков (2008). "Глава 8: Алгоритмы сетевого потока". Алгоритмы в двух словах . Oreilly Media . стр. 226–250. ISBN 978-0-596-51624-6.
Равиндра К. Ахуджа ; Томас Л. Магнанти ; Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения . Prentice Hall. ISBN 0-13-617549-X.
Боллобаш, Бела (1979). Теория графов: вводный курс . Гейдельберг: Springer-Verlag. ISBN 3-540-90399-2.
Chartrand, Gary ; Oellermann, Ortrud R. (1993). Прикладная и алгоритмическая теория графов . Нью-Йорк: McGraw-Hill. ISBN 0-07-557101-3.
Even, Shimon (1979). Графовые алгоритмы . Роквилл, Мэриленд: Computer Science Press. ISBN 0-914894-21-8.
Гиббонс, Алан (1985). Алгоритмическая теория графов . Кембридж: Cambridge University Press. ISBN 0-521-28881-9.
Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein (2001) [1990]. "26". Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 696–697. ISBN 0-262-03293-7.

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

На Викискладе есть медиафайлы по теме «Сети Flow».

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