Транспортная сеть

В теории графов транспортная сеть — ориентированный граф $G=(V,E)$ , в котором каждое ребро $(u,v)\in E$ имеет неотрицательную пропускную способность $c(u,v)\geqslant 0$ и поток $f(u,v)$. Выделяются две вершины: источник $s$ и сток $t$ такие, что любая другая вершина сети лежит на пути из $s$ в $t$, при этом $s\neq t$. Транспортная сеть может быть использована для моделирования, например, дорожного трафика.

Целочисленная транспортная сеть — транспортная сеть, все пропускные способности рёбер которой — целые числа.

Определения

Транспортная сеть (flow network) — ориентированный граф $G(V,E),$ в котором

• каждое ребро$\ (u,v)\in E$ имеет неотрицательную пропускную способность, выражаемую функцией $c\colon V\times V\rightarrow \mathbb {R} _{+}$(в некоторых источниках также $c\colon E\rightarrow \mathbb {R} _{+}$), такую, что для любого $e\not \in E$ значение функции равно нулю.
• выделены две вершины: источник (source) $s$ и сток (sink) $t$, такие, что любая другая вершина сети лежит на пути из $s$ в $t$, при этом $s\neq t$.

Поток (flow) — функция $f\colon V\times V\rightarrow \mathbb {R} _{+}$ (в некоторых источниках также $f\colon E\rightarrow \mathbb {R} _{+}$) со следующими свойствами:

• Ограничение пропускной способности (capacity constraints). Величина потока для любого ребра $e\in E$ не может превысить его пропускную способность: $0\leqslant f(e)\leqslant c(e).$
• Кососимметричность (skew symmetry). Поток из $\ u$ в $\ v$ должен быть противоположным потоку из $\ v$ в $\ u$: $f(u,v)=-f(v,u).$
• Сохранение потока (flow conservation): $\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}}$ для всех $\ u\in V$.

Величина потока (value of flow) — сумма потоков из источника или сумма потоков в сток $|f|=\sum _{v\in V}f(s,v)=\sum _{v\in V}f(v,t)$.

Задача о максимальном потоке (maximum flow problem) — найти поток $f$ такой, что величина потока максимальна, т.е. не существует потока $f^{*}$ такого, что $|f^{*}|>|f|$.

Разрез (s-t cut) — пара непересекающихся множеств $(A,B)$ такая, что $V=A\ {\dot {\cup }}\ B$ и $s\in A$ и $t\in B$. Также встречается определение, где разрез — это подмножество ребер $\delta ^{+}(X)=\{(u,v)\in E\mid u\in X,\ v\notin X\}$, где $X$ - подмножество вершин такое, что $s\in X$ и $t\notin X$.

Пропускная способность разреза (the capacity of an s-t cut) — сумма пропускных способностей всех рёбер разреза: $\sum _{e\in \delta ^{+}(X)}c(e)$ или $\sum _{(u,v)\in E,u\in A,v\in B}c((u,v))$.

Величина потока разреза — сумма величин потока всех рёбер разреза $\sum _{e\in \delta ^{+}(X)}f(e)$ или $\sum _{(u,v)\in E,u\in A,v\in B}f((u,v))$. Она не превышает пропускную способность разреза, поскольку $f(e)\leqslant c(e)$ для всех $e\in E$.

Минимальный разрез — разрез с минимальной пропускной способностью.

Остаточная пропускная способность ребра (residual capacity) — $c_{f}((u,v))=c((u,v))-f((u,v))$. Она всегда неотрицательна из-за условия на ограничение пропускной способности.

Остаточная сеть (residual network) — граф $G_{f}=(V,E_{f})$, где $E_{f}$ — множество рёбер с положительной остаточной пропускной способностью. В остаточной сети может существовать путь из вершины $u$ в вершину $v$, даже если его нет в исходной сети. Это происходит, когда в исходной сети есть обратный путь $(v,u)$ и поток по нему положителен.

Увеличивающий (остаточный, дополняющий) путь (augmenting path) — это путь $(u_{1},u_{2},\dots ,u_{k})$ в остаточной сети, где $u_{1}=s,$ $u_{k}=t,$ и $c_{f}(u_{i},u_{i+1})>0.$ Ниже доказано, что поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.

Свойства

Поток через любой разрез равен сумме потоков из источника.
Доказательство: пускай есть разрез (A,B). Рассмотрим сумму всех потоков из всех вершин, принадлежащих А. Она равна

$\sum _{u\in A}\sum _{v\in A}f(u,v)+\sum _{u\in A}\sum _{v\in B}f(u,v)$

В первой из сумм для любой пары вершин (u, v) есть два слагаемых f(u, v) и f(v, u), равных по модулю и противоположных по знаку. Следовательно, эта сумма равна нулю. Вторая сумма есть поток через разрез (A,B). Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна потоку через разрез. С другой стороны, сумма потоков из любой вершины, кроме s и t, равна нулю, а $t\notin A$. Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна сумме потоков из s. Следовательно, поток через разрез (A,B) равен сумме потоков из s, что и требовалось доказать.

Сумма потоков из источника равна сумме потоков в сток.
Доказательство: рассмотрим разрез $(V\setminus \{t\},\{t\})$. Поток через этот разрез равен сумме потоков в сток. С другой стороны, по только что доказанному, поток через этот (как и любой другой) разрез равен сумме потоков из источника. Теорема доказана.

Максимальный поток положителен тогда и только тогда, когда существует путь из источника в сток, проходящий по рёбрам с положительной пропускной способностью.
Доказательство: Пускай такой путь P существует. Пусть c — минимальная из пропускных способностей рёбер, принадлежащих P. Пускай поток равен c на всех рёбрах из P, и нулю на всех остальных рёбрах. Тогда суммарный поток из источника равен c, то есть положителен. Теперь допустим, что такого пути нет, то есть t недостижимо из s по рёбрам с положительной пропускной способностью. Пусть A — множество вершин, достижимых из s по таким рёбрам, B — недостижимых. Тогда, поскольку $s\in A$, $t\in B$, то (A,B) является разрезом. Кроме того, не существует ребра (a, b) с положительной пропускной способностью, такого что $a\in A$, $b\in B$, иначе b было бы достижимо из s. Следовательно, пропускная способность разреза (A,B) равна нулю, а значит и поток через него всегда равен нулю. Следовательно, сумма потоков из источника всегда равна нулю.

Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети. Доказательство: Пусть в остаточной сети существует увеличивающий путь $P$, а $c$ — минимальная из остаточных пропускных способностей рёбер, принадлежащих $P$, в остаточной сети. Для всех пар $(u,v)\in P$ увеличим $f(u,v)$ на $c$ и уменьшим $f(v,u)$ на $c$. Мы увеличили суммарный поток из источника на $c$, следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток $f$ в исходной сети обеспечивает максимальный суммарный поток из $s$. Пусть это не так, тогда есть поток $f'$, обеспечивающий больший суммарный поток из $s$. Легко убедиться, что $f'-f$ — поток в остаточной сети, обеспечивающий в ней положительный суммарный поток из $s$. Следовательно, в остаточной сети есть путь из источника в сток, то есть увеличивающий путь. Мы получили противоречие.

Теорема Форда — Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.
Доказательство: сумма потоков из $s$ равна потоку через любой разрез, в том числе минимальный, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть $A$ — множество вершин, достижимых из источника в остаточной сети, $B$ — недостижимых. Тогда, поскольку $s\in A$, $t\in B$, то $(A,B)$ является разрезом. Кроме того, в остаточной сети не существует ребра $(a,b)$ с положительной пропускной способностью, такого что $a\in A$, $b\in B$, иначе бы $b$ было достижимо из $s$. Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез $(A,B)$ равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. Значит, максимальный поток равен пропускной способности разреза $(A,B)$, которая не меньше пропускной способности минимального разреза. Теорема доказана.

Пример

Транспортная сеть с указанием потока и пропускной способности.

Здесь изображена транспортная сеть с источником $\ s$, стоком $\ t$ и четырьмя дополнительными узлами. Поток и пропускная способность обозначены соответственно $\ f/c$. Пропускная способность из источника к стоку равна 5, что легко видно, так как пропускная способность из $\ s$ равна 5, что есть также в $\ t$.

Остаточная сеть для показанного сверху потока, показывающая остаточные пропускные способности.

Ниже показана остаточная сеть для данного выше потока. Обратите внимание, что существует ограничивающая пропускная способность для некоторых рёбер, тогда как в исходной сети она равна нулю. Например, ребро $\ (d,c)$. Этот поток не максимален. Есть увеличивающие пути $\ (s,a,c,t)$, $\ (s,a,b,d,t)$ и $\ (s,a,b,d,c,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$. Увеличивающего пути $\ (s,a,b,d,c,t)$ не существует в исходной сети, но можно пропустить по нему правильный поток.

Применение

Самый частый пример использования транспортных сетей — нахождение максимального потока, который означает максимальный суммарный поток от $s$ к $t.$ Для нахождения максимального потока в сети может быть использован алгоритм Форда — Фалкерсона, алгоритм Эдмондса — Карпа и другие.

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

См. также

• Задача о максимальном потоке
• Поток минимальной стоимости

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.

Ссылки (англ.)

• 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