Транспортная сеть
В теории графов транспортная сеть — ориентированный граф [math]\displaystyle{ G = (V, E) }[/math] , в котором каждое ребро [math]\displaystyle{ (u,v) \in E }[/math] имеет неотрицательную пропускную способность [math]\displaystyle{ c(u,v) \geqslant 0 }[/math] и поток [math]\displaystyle{ f(u,v) }[/math]. Выделяются две вершины: источник [math]\displaystyle{ s }[/math] и сток [math]\displaystyle{ t }[/math] такие, что любая другая вершина сети лежит на пути из [math]\displaystyle{ s }[/math] в [math]\displaystyle{ t }[/math], при этом [math]\displaystyle{ s \neq t }[/math]. Транспортная сеть может быть использована для моделирования, например, дорожного трафика.
Целочисленная транспортная сеть — транспортная сеть, все пропускные способности рёбер которой — целые числа.
Определения
Транспортная сеть (flow network) — ориентированный граф [math]\displaystyle{ G(V,E), }[/math] в котором
- каждое ребро[math]\displaystyle{ \ (u,v) \in E }[/math] имеет неотрицательную пропускную способность, выражаемую функцией [math]\displaystyle{ c \colon V \times V \rightarrow \mathbb{R}_+ }[/math](в некоторых источниках также [math]\displaystyle{ c \colon E \rightarrow \mathbb{R}_+ }[/math]), такую, что для любого [math]\displaystyle{ e \not \in E }[/math] значение функции равно нулю.
- выделены две вершины: источник (source) [math]\displaystyle{ s }[/math] и сток (sink) [math]\displaystyle{ t }[/math], такие, что любая другая вершина сети лежит на пути из [math]\displaystyle{ s }[/math] в [math]\displaystyle{ t }[/math], при этом [math]\displaystyle{ s \neq t }[/math].
Поток (flow) — функция [math]\displaystyle{ f \colon V \times V \rightarrow \mathbb{R}_+ }[/math] (в некоторых источниках также [math]\displaystyle{ f \colon E \rightarrow \mathbb{R}_+ }[/math]) со следующими свойствами:
- Ограничение пропускной способности (capacity constraints). Величина потока для любого ребра [math]\displaystyle{ e \in E }[/math] не может превысить его пропускную способность: [math]\displaystyle{ 0 \leqslant f(e) \leqslant c(e). }[/math]
- Кососимметричность (skew symmetry). Поток из [math]\displaystyle{ \ u }[/math] в [math]\displaystyle{ \ v }[/math] должен быть противоположным потоку из [math]\displaystyle{ \ v }[/math] в [math]\displaystyle{ \ u }[/math]: [math]\displaystyle{ f(u,v) = - f(v,u). }[/math]
- Сохранение потока (flow conservation): [math]\displaystyle{ \sum_{v \in V} f((u, v)) - \sum_{w \in V} f((w, u)) = \begin{cases} |f| &, v = s \\ -|f| &, v = t \\ 0 &, v \neq s \land v \neq t \\ \end{cases} }[/math] для всех [math]\displaystyle{ \ u \in V }[/math].
Величина потока (value of flow) — сумма потоков из источника или сумма потоков в сток [math]\displaystyle{ |f| = \sum_{v \in V} f(s,v) = \sum_{v \in V} f(v,t) }[/math].
Задача о максимальном потоке (maximum flow problem) — найти поток [math]\displaystyle{ f }[/math] такой, что величина потока максимальна, т.е. не существует потока [math]\displaystyle{ f^* }[/math] такого, что [math]\displaystyle{ |f^*| \gt |f| }[/math].
Разрез (s-t cut) — пара непересекающихся множеств [math]\displaystyle{ (A, B) }[/math] такая, что [math]\displaystyle{ V = A \ \dot \cup \ B }[/math] и [math]\displaystyle{ s \in A }[/math] и [math]\displaystyle{ t \in B }[/math]. Также встречается определение, где разрез — это подмножество ребер [math]\displaystyle{ \delta^+(X) = \{ (u, v) \in E \mid u \in X, \ v \notin X \} }[/math], где [math]\displaystyle{ X }[/math] - подмножество вершин такое, что [math]\displaystyle{ s \in X }[/math] и [math]\displaystyle{ t \notin X }[/math].
Пропускная способность разреза (the capacity of an s-t cut) — сумма пропускных способностей всех рёбер разреза: [math]\displaystyle{ \sum_{e \in \delta^+(X)} c(e) }[/math] или [math]\displaystyle{ \sum_{(u, v) \in E, u \in A, v \in B} c((u, v)) }[/math].
Величина потока разреза — сумма величин потока всех рёбер разреза [math]\displaystyle{ \sum_{e \in \delta^+(X)} f(e) }[/math] или [math]\displaystyle{ \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]\displaystyle{ f(e) \leqslant c(e) }[/math] для всех [math]\displaystyle{ e \in E }[/math].
Минимальный разрез — разрез с минимальной пропускной способностью.
Остаточная пропускная способность ребра (residual capacity) — [math]\displaystyle{ c_f((u,v)) = c((u,v)) - f((u,v)) + f((v, u)) }[/math]. Она всегда неотрицательна из-за условия на ограничение пропускной способности.
Остаточная сеть (residual network) — граф [math]\displaystyle{ G_f=(V,E_f) }[/math], где [math]\displaystyle{ E_f }[/math] — множество рёбер с положительной остаточной пропускной способностью. В остаточной сети может существовать путь из вершины [math]\displaystyle{ u }[/math] в вершину [math]\displaystyle{ v }[/math], даже если его нет в исходной сети. Это происходит, когда в исходной сети есть обратный путь [math]\displaystyle{ (v,u) }[/math] и поток по нему положителен.
Увеличивающий (остаточный, дополняющий) путь (augmenting path) — это путь [math]\displaystyle{ (u_1,u_2,\dots,u_k) }[/math] в остаточной сети, где [math]\displaystyle{ u_1=s, }[/math] [math]\displaystyle{ u_k=t, }[/math] и [math]\displaystyle{ c_f(u_i, u_{i+1}) \gt 0. }[/math] Ниже доказано, что поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.
Свойства
Поток через любой разрез равен сумме потоков из источника.
Доказательство: пускай есть разрез (A,B). Рассмотрим сумму всех потоков из всех вершин, принадлежащих А. Она равна
- [math]\displaystyle{ \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]\displaystyle{ t\notin A }[/math]. Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна сумме потоков из s. Следовательно, поток через разрез (A,B) равен сумме потоков из s, что и требовалось доказать.
Сумма потоков из источника равна сумме потоков в сток.
Доказательство: рассмотрим разрез [math]\displaystyle{ (V\setminus\{t\}, \{t\}) }[/math]. Поток через этот разрез равен сумме потоков в сток. С другой стороны, по только что доказанному, поток через этот (как и любой другой) разрез равен сумме потоков из источника. Теорема доказана.
Максимальный поток положителен тогда и только тогда, когда существует путь из источника в сток, проходящий по рёбрам с положительной пропускной способностью.
Доказательство: Пускай такой путь P существует. Пусть c — минимальная из пропускных способностей рёбер, принадлежащих P. Пускай поток равен c на всех рёбрах из P, и нулю на всех остальных рёбрах. Тогда суммарный поток из источника равен c, то есть положителен. Теперь допустим, что такого пути нет, то есть t недостижимо из s по рёбрам с положительной пропускной способностью. Пусть A — множество вершин, достижимых из s по таким рёбрам, B — недостижимых. Тогда, поскольку [math]\displaystyle{ s\in A }[/math], [math]\displaystyle{ t \in B }[/math], то (A,B) является разрезом. Кроме того, не существует ребра (a, b) с положительной пропускной способностью, такого что [math]\displaystyle{ a\in A }[/math], [math]\displaystyle{ b \in B }[/math], иначе b было бы достижимо из s. Следовательно, пропускная способность разреза (A,B) равна нулю, а значит и поток через него всегда равен нулю. Следовательно, сумма потоков из источника всегда равна нулю.
Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети. Доказательство: Пусть в остаточной сети существует увеличивающий путь [math]\displaystyle{ P }[/math], а [math]\displaystyle{ c }[/math] — минимальная из остаточных пропускных способностей рёбер, принадлежащих [math]\displaystyle{ P }[/math], в остаточной сети. Для всех пар [math]\displaystyle{ (u,v)\in P }[/math] увеличим [math]\displaystyle{ f(u, v) }[/math] на [math]\displaystyle{ c }[/math] и уменьшим [math]\displaystyle{ f(v, u) }[/math] на [math]\displaystyle{ c }[/math]. Мы увеличили суммарный поток из источника на [math]\displaystyle{ c }[/math], следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток [math]\displaystyle{ f }[/math] в исходной сети обеспечивает максимальный суммарный поток из [math]\displaystyle{ s }[/math]. Пусть это не так, тогда есть поток [math]\displaystyle{ f' }[/math], обеспечивающий больший суммарный поток из [math]\displaystyle{ s }[/math]. Легко убедиться, что [math]\displaystyle{ f'-f }[/math] — поток в остаточной сети, обеспечивающий в ней положительный суммарный поток из [math]\displaystyle{ s }[/math]. Следовательно, в остаточной сети есть путь из источника в сток, то есть увеличивающий путь. Мы получили противоречие.
Теорема Форда — Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.
Доказательство: сумма потоков из [math]\displaystyle{ s }[/math] равна потоку через любой разрез, в том числе минимальный, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть [math]\displaystyle{ A }[/math] — множество вершин, достижимых из источника в остаточной сети, [math]\displaystyle{ B }[/math] — недостижимых. Тогда, поскольку [math]\displaystyle{ s\in A }[/math], [math]\displaystyle{ t \in B }[/math], то [math]\displaystyle{ (A,B) }[/math] является разрезом. Кроме того, в остаточной сети не существует ребра [math]\displaystyle{ (a, b) }[/math] с положительной пропускной способностью, такого что [math]\displaystyle{ a\in A }[/math], [math]\displaystyle{ b \in B }[/math], иначе бы [math]\displaystyle{ b }[/math] было достижимо из [math]\displaystyle{ s }[/math]. Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез [math]\displaystyle{ (A, B) }[/math] равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. Значит, максимальный поток равен пропускной способности разреза [math]\displaystyle{ (A,B) }[/math], которая не меньше пропускной способности минимального разреза. Теорема доказана.
Пример
Здесь изображена транспортная сеть с источником [math]\displaystyle{ \ s }[/math], стоком [math]\displaystyle{ \ t }[/math] и четырьмя дополнительными узлами. Поток и пропускная способность обозначены соответственно [math]\displaystyle{ \ f/c }[/math]. Пропускная способность из источника к стоку равна 5, что легко видно, так как пропускная способность из [math]\displaystyle{ \ s }[/math] равна 5, что есть также в [math]\displaystyle{ \ t }[/math].
Ниже показана остаточная сеть для данного выше потока. Обратите внимание, что существует ограничивающая пропускная способность для некоторых рёбер, тогда как в исходной сети она равна нулю. Например, ребро [math]\displaystyle{ \ (d,c) }[/math]. Этот поток не максимален. Есть увеличивающие пути [math]\displaystyle{ \ (s,a,c,t) }[/math], [math]\displaystyle{ \ (s,a,b,d,t) }[/math] и [math]\displaystyle{ \ (s,a,b,d,c,t) }[/math]. Остаточная пропускная способность первого пути [math]\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 }[/math]. Увеличивающего пути [math]\displaystyle{ \ (s,a,b,d,c,t) }[/math] не существует в исходной сети, но можно пропустить по нему правильный поток.
Применение
Самый частый пример использования транспортных сетей — нахождение максимального потока, который означает максимальный суммарный поток от [math]\displaystyle{ s }[/math] к [math]\displaystyle{ t. }[/math] Для нахождения максимального потока в сети может быть использован алгоритм Форда — Фалкерсона, алгоритм Эдмондса — Карпа и другие.
В задаче о потоке минимальной стоимости, каждому ребру [math]\displaystyle{ (u,v) }[/math] сопоставляется цена [math]\displaystyle{ k(u,v) }[/math], цена пересылки потока [math]\displaystyle{ f(u,v) }[/math] через ребро [math]\displaystyle{ f(u,v) \cdot k(u,v) }[/math]. Задача — послать заданное количество потока от [math]\displaystyle{ s }[/math] к [math]\displaystyle{ t }[/math] с наименьшей ценой.
См. также
Литература
- Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.