Русская Википедия:Транспортная сеть
В теории графов транспортная сеть — ориентированный граф <math>G = (V, E)</math> , в котором каждое ребро <math>(u,v) \in E</math> имеет неотрицательную пропускную способность <math>c(u,v) \geqslant 0</math> и поток <math>f(u,v)</math>. Выделяются две вершины: источник <math>s</math> и сток <math>t</math> такие, что любая другая вершина сети лежит на пути из <math>s</math> в <math>t</math>, при этом <math>s \neq t</math>. Транспортная сеть может быть использована для моделирования, например, дорожного трафика.
Целочисленная транспортная сеть — транспортная сеть, все пропускные способности рёбер которой — целые числа.
Определения
Транспортная сеть (flow network) — ориентированный граф <math>G(V,E),</math> в котором
- каждое ребро<math>\ (u,v) \in E</math> имеет неотрицательную пропускную способность, выражаемую функцией <math>c \colon V \times V \rightarrow \mathbb{R}_+</math>(в некоторых источниках также <math>c \colon E \rightarrow \mathbb{R}_+</math>), такую, что для любого <math>e \not \in E</math> значение функции равно нулю.
- выделены две вершины: источник (source) <math>s</math> и сток (sink) <math>t</math>, такие, что любая другая вершина сети лежит на пути из <math>s</math> в <math>t</math>, при этом <math>s \neq t</math>.
Поток (flow) — функция <math>f \colon V \times V \rightarrow \mathbb{R}_+</math> (в некоторых источниках также <math>f \colon E \rightarrow \mathbb{R}_+</math>) со следующими свойствами:
- Ограничение пропускной способности (capacity constraints). Величина потока для любого ребра <math>e \in E</math> не может превысить его пропускную способность: <math>0 \leqslant f(e) \leqslant c(e).</math>
- Кососимметричность (skew symmetry). Поток из <math>\ u</math> в <math>\ v</math> должен быть противоположным потоку из <math>\ v</math> в <math>\ u</math>: <math>f(u,v) = - f(v,u).</math>
- Сохранение потока (flow conservation): <math>\sum_{u \in V} f(v, u)=
\begin{cases}
|f| &, v = s \\ -|f| &, v = t \\ 0 &, v \neq s \land v \neq t \\
\end{cases}</math> для всех <math>\ u \in V</math>.
Величина потока (value of flow) — сумма потоков из источника или сумма потоков в сток <math>|f| = \sum_{v \in V} f(s,v) = \sum_{v \in V} f(v,t)</math>.
Задача о максимальном потоке (maximum flow problem) — найти поток <math>f</math> такой, что величина потока максимальна, т.е. не существует потока <math>f^*</math> такого, что <math>|f^*| > |f|</math>.
Разрез (s-t cut) — пара непересекающихся множеств <math>(A, B)</math> такая, что <math>V = A \ \dot \cup \ B</math> и <math>s \in A</math> и <math>t \in B</math>. Также встречается определение, где разрез — это подмножество ребер <math>\delta^+(X) = \{ (u, v) \in E \mid u \in X, \ v \notin X \}</math>, где <math>X</math> - подмножество вершин такое, что <math>s \in X</math> и <math>t \notin X </math>.
Пропускная способность разреза (the capacity of an s-t cut) — сумма пропускных способностей всех рёбер разреза: <math>\sum_{e \in \delta^+(X)} c(e)</math> или <math>\sum_{(u, v) \in E, u \in A, v \in B} c((u, v))</math>.
Величина потока разреза — сумма величин потока всех рёбер разреза <math>\sum_{e \in \delta^+(X)} f(e)</math> или <math>\sum_{(u, v) \in E, u \in A, v \in B} f((u, v)) - \sum_{(u, v) \in E, u \in A, v \in B} f((v, u))</math>. Она не превышает пропускную способность разреза, поскольку <math>f(e) \leqslant c(e)</math> для всех <math>e \in E</math>.
Минимальный разрез — разрез с минимальной пропускной способностью.
Остаточная пропускная способность ребра (residual capacity) — <math>c_f((u,v)) = c((u,v)) - f((u,v)) + f((v, u))</math>. Она всегда неотрицательна из-за условия на ограничение пропускной способности.
Остаточная сеть (residual network) — граф <math>G_f=(V,E_f)</math>, где <math>E_f</math> — множество рёбер с положительной остаточной пропускной способностью. В остаточной сети может существовать путь из вершины <math>u</math> в вершину <math>v</math>, даже если его нет в исходной сети. Это происходит, когда в исходной сети есть обратный путь <math>(v,u)</math> и поток по нему положителен.
Увеличивающий (остаточный, дополняющий) путь (augmenting path) — это путь <math>(u_1,u_2,\dots,u_k)</math> в остаточной сети, где <math>u_1=s,</math> <math>u_k=t,</math> и <math>c_f(u_i, u_{i+1}) > 0.</math> Ниже доказано, что поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.
Свойства
Поток через любой разрез равен сумме потоков из источника.
Доказательство: пускай есть разрез (A,B). Рассмотрим сумму всех потоков из всех вершин, принадлежащих А. Она равна
- <math>\sum_{u\in A}\sum_{v\in A} f(u,v) + \sum_{u\in A}\sum_{v\in B} f(u,v)</math>
В первой из сумм для любой пары вершин (u, v) есть два слагаемых f(u, v) и f(v, u), равных по модулю и противоположных по знаку. Следовательно, эта сумма равна нулю. Вторая сумма есть поток через разрез (A,B). Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна потоку через разрез. С другой стороны, сумма потоков из любой вершины, кроме s и t, равна нулю, а <math>t\notin A</math>. Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна сумме потоков из s. Следовательно, поток через разрез (A,B) равен сумме потоков из s, что и требовалось доказать.
Сумма потоков из источника равна сумме потоков в сток.
Доказательство: рассмотрим разрез <math>(V\setminus\{t\}, \{t\})</math>. Поток через этот разрез равен сумме потоков в сток. С другой стороны, по только что доказанному, поток через этот (как и любой другой) разрез равен сумме потоков из источника. Теорема доказана.
Максимальный поток положителен тогда и только тогда, когда существует путь из источника в сток, проходящий по рёбрам с положительной пропускной способностью.
Доказательство: Пускай такой путь P существует. Пусть c — минимальная из пропускных способностей рёбер, принадлежащих P. Пускай поток равен c на всех рёбрах из P, и нулю на всех остальных рёбрах. Тогда суммарный поток из источника равен c, то есть положителен. Теперь допустим, что такого пути нет, то есть t недостижимо из s по рёбрам с положительной пропускной способностью. Пусть A — множество вершин, достижимых из s по таким рёбрам, B — недостижимых. Тогда, поскольку <math>s\in A</math>, <math>t \in B</math>, то (A,B) является разрезом. Кроме того, не существует ребра (a, b) с положительной пропускной способностью, такого что <math>a\in A</math>, <math>b \in B</math>, иначе b было бы достижимо из s. Следовательно, пропускная способность разреза (A,B) равна нулю, а значит и поток через него всегда равен нулю. Следовательно, сумма потоков из источника всегда равна нулю.
Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети. Доказательство: Пусть в остаточной сети существует увеличивающий путь <math>P</math>, а <math>c</math> — минимальная из остаточных пропускных способностей рёбер, принадлежащих <math>P</math>, в остаточной сети. Для всех пар <math>(u,v)\in P</math> увеличим <math>f(u, v)</math> на <math>c</math> и уменьшим <math>f(v, u)</math> на <math>c</math>. Мы увеличили суммарный поток из источника на <math>c</math>, следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток <math>f</math> в исходной сети обеспечивает максимальный суммарный поток из <math>s</math>. Пусть это не так, тогда есть поток <math>f'</math>, обеспечивающий больший суммарный поток из <math>s</math>. Легко убедиться, что <math>f'-f</math> — поток в остаточной сети, обеспечивающий в ней положительный суммарный поток из <math>s</math>. Следовательно, в остаточной сети есть путь из источника в сток, то есть увеличивающий путь. Мы получили противоречие.
Теорема Форда — Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.
Доказательство: сумма потоков из <math>s</math> равна потоку через любой разрез, в том числе минимальный, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть <math>A</math> — множество вершин, достижимых из источника в остаточной сети, <math>B</math> — недостижимых. Тогда, поскольку <math>s\in A</math>, <math>t \in B</math>, то <math>(A,B)</math> является разрезом. Кроме того, в остаточной сети не существует ребра <math>(a, b)</math> с положительной пропускной способностью, такого что <math>a\in A</math>, <math>b \in B</math>, иначе бы <math>b</math> было достижимо из <math>s</math>. Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез <math>(A, B)</math> равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. Значит, максимальный поток равен пропускной способности разреза <math>(A,B)</math>, которая не меньше пропускной способности минимального разреза. Теорема доказана.
Пример
Здесь изображена транспортная сеть с источником <math>\ s</math>, стоком <math>\ t</math> и четырьмя дополнительными узлами. Поток и пропускная способность обозначены соответственно <math>\ f/c</math>. Пропускная способность из источника к стоку равна 5, что легко видно, так как пропускная способность из <math>\ s</math> равна 5, что есть также в <math>\ t</math>.
Ниже показана остаточная сеть для данного выше потока. Обратите внимание, что существует ограничивающая пропускная способность для некоторых рёбер, тогда как в исходной сети она равна нулю. Например, ребро <math>\ (d,c)</math>. Этот поток не максимален. Есть увеличивающие пути <math>\ (s,a,c,t)</math>, <math>\ (s,a,b,d,t)</math> и <math>\ (s,a,b,d,c,t)</math>. Остаточная пропускная способность первого пути <math>\ 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</math>. Увеличивающего пути <math>\ (s,a,b,d,c,t)</math> не существует в исходной сети, но можно пропустить по нему правильный поток.
Применение
Самый частый пример использования транспортных сетей — нахождение максимального потока, который означает максимальный суммарный поток от <math> s</math> к <math> t.</math> Для нахождения максимального потока в сети может быть использован алгоритм Форда — Фалкерсона, алгоритм Эдмондса — Карпа и другие.
В задаче о потоке минимальной стоимости, каждому ребру <math>(u,v)</math> сопоставляется цена <math>k(u,v)</math>, цена пересылки потока <math>f(u,v)</math> через ребро <math>f(u,v) \cdot k(u,v)</math>. Задача — послать заданное количество потока от <math> s</math> к <math> t</math> с наименьшей ценой.
См. также
Литература
Ссылки (англ.)
- Maximum Flow Problem
- Maximum Flow
- Real graph instances
- Software, papers, test graphs, etc.
- Solutions for network flow problemsШаблон:Недоступная ссылка
- Software and papers for network flow problems
- Lemon C++ library with several maximum flow and minimum cost circulation algorithms
