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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

Свойства

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

${\displaystyle \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, равна нулю, а ${\displaystyle t\notin A}$. Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна сумме потоков из s. Следовательно, поток через разрез (A,B) равен сумме потоков из s, что и требовалось доказать.

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

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

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

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

Пример

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

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

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

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

Применение

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

В задаче о потоке минимальной стоимости, каждому ребру ${\displaystyle (u,v)}$ сопоставляется цена ${\displaystyle k(u,v)}$, цена пересылки потока ${\displaystyle f(u,v)}$ через ребро ${\displaystyle f(u,v)\cdot k(u,v)}$. Задача — послать заданное количество потока от ${\displaystyle s}$ к ${\displaystyle 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