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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов транспортная сеть — ориентированный граф , в котором каждое ребро имеет неотрицательную пропускную способность и поток . Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из в , при этом . Транспортная сеть может быть использована для моделирования, например, дорожного трафика.

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

Определения

[править | править код]

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

  • каждое ребро имеет неотрицательную пропускную способность, выражаемую функцией (в некоторых источниках также ), такую, что для любого значение функции равно нулю.
  • выделены две вершины: источник (source) и сток (sink) , такие, что любая другая вершина сети лежит на пути из в , при этом .

Поток (flow) — функция (в некоторых источниках также ) со следующими свойствами:

  • Ограничение пропускной способности (capacity constraints). Величина потока для любого ребра не может превысить его пропускную способность:
  • Кососимметричность (skew symmetry). Поток из в должен быть противоположным потоку из в :
  • Сохранение потока (flow conservation): для всех .

Величина потока (value of flow) — сумма потоков из источника или сумма потоков в сток .

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

Разрез (s-t cut) — пара непересекающихся множеств такая, что и и . Также встречается определение, где разрез — это подмножество ребер , где - подмножество вершин такое, что и .

Пропускная способность разреза (the capacity of an s-t cut) — сумма пропускных способностей всех рёбер разреза: или .

Величина потока разреза — сумма величин потока всех рёбер разреза или . Она не превышает пропускную способность разреза, поскольку для всех .

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

Остаточная пропускная способность ребра (residual capacity) — . Она всегда неотрицательна из-за условия на ограничение пропускной способности.

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

Увеличивающий (остаточный, дополняющий) путь (augmenting path) — это путь в остаточной сети, где и Ниже доказано, что поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.

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

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

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

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

Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети. Доказательство: Пусть в остаточной сети существует увеличивающий путь , а  — минимальная из остаточных пропускных способностей рёбер, принадлежащих , в остаточной сети. Для всех пар увеличим на и уменьшим на . Мы увеличили суммарный поток из источника на , следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток в исходной сети обеспечивает максимальный суммарный поток из . Пусть это не так, тогда есть поток , обеспечивающий больший суммарный поток из . Легко убедиться, что  — поток в остаточной сети, обеспечивающий в ней положительный суммарный поток из . Следовательно, в остаточной сети есть путь из источника в сток, то есть увеличивающий путь. Мы получили противоречие.

Теорема Форда — Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.
Доказательство: сумма потоков из равна потоку через любой разрез, в том числе минимальный, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть  — множество вершин, достижимых из источника в остаточной сети,  — недостижимых. Тогда, поскольку , , то является разрезом. Кроме того, в остаточной сети не существует ребра с положительной пропускной способностью, такого что , , иначе бы было достижимо из . Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. Значит, максимальный поток равен пропускной способности разреза , которая не меньше пропускной способности минимального разреза. Теорема доказана.

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

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

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

Ниже показана остаточная сеть для данного выше потока. Обратите внимание, что существует ограничивающая пропускная способность для некоторых рёбер, тогда как в исходной сети она равна нулю. Например, ребро . Этот поток не максимален. Есть увеличивающие пути , и . Остаточная пропускная способность первого пути . Увеличивающего пути не существует в исходной сети, но можно пропустить по нему правильный поток.

Применение

[править | править код]

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

В задаче о потоке минимальной стоимости, каждому ребру сопоставляется цена , цена пересылки потока через ребро . Задача — послать заданное количество потока от к с наименьшей ценой.

Литература

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

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

[править | править код]