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

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

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

Определения

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

• каждому ребру $\ (u,v) \in E$ приписана неотрицательная пропускная способность $\ c(u,v) \ge 0$. Если $\ (u, v) \not \in E$, то $\ c(u, v) = 0$.
• выделены две вершины: источник (source) $s$ и сток (sink) $t$, такие, что любая другая вершина сети лежит на пути из $s$ в $t$.

Поток (flow) — функция $\ f:V \times V \rightarrow \mathbb{R}$ со следующими свойствами для любых вершин $\ u$ и $\ v$:

• Ограничение пропускной способности (capacity constraints). Поток не может превысить пропускную способность: $\ f(u,v) \le c(u,v).$
• Антисимметричность (skew symmetry). Поток из $\ u$ в $\ v$ должен быть противоположным потоку из $\ v$ в $\ u$: $\ f(u,v) = - f(v,u).$
• Сохранение потока (flow conservation): $\ \sum_{w \in V} f(u,w) = 0$ для всех $\ u \in V$, кроме источника и стока.

Величина потока (value of flow) — сумма потоков из источника $\scriptstyle |f| = \sum_{v \in V} f(s,v)$. В дальнейшем мы докажем, что она равна сумме потоков в сток $\ \sum_{w \in V} f(w,t)$.

Задача о максимальном потоке (maximum flow problem): найти поток f такой, что величина потока максимальна.

Разрез (s-t cut) — разбиение множества всех вершин V на два подмножества, A и B, таких что $s\in A$, $t\in B$.

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

Поток через разрез (A,B) — сумма всех потоков из A в B $\sum_{u\in A}\sum_{v\in B}f(u,v)$. Он не превышает пропускную способность разреза, поскольку $f(u,v)\le c(u,v)$.

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

Остаточная пропускная способность (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. Мы увеличили суммарный поток из источника на s, следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток 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) равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. С другой стороны, пропускная способность любого разреза не меньше пропускной способности минимального разреза. Комбинируя эти три утверждения, получаем, что максимальный поток не меньше пропускной способности минимального разреза. Теорема доказана.

Пример

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

Здесь изображена транспортная сеть с источником $\ 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