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

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

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

ОпределенияПравить

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

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

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

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

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

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

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

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

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

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

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

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

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

СвойстваПравить

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

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

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

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

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

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

ПримерПравить

 

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

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

 

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

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

ПрименениеПравить

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

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