ЛЕКЦИЯ 7. Максимальные потоки. Теорема Форда и Фалкерсона

Дана сеть, дуги которой ориентированы. В сети должны быть два специальных узла, называемых источник (исток) V ₀ и слив (сток) V_n. V ₀ – узел, у которого инвалентность равна нулю, а V_n – узел у которого аутвалентность равна нулю. Каждой дуге сети приписывается некоторое число. Это число является не длиной дуги, а скорее ее шириной.

Рассмотрим сети, которые представляют собой поток «товара» через серию каналов ("трубопроводов"). 'Товар' может фактически (но не только) представлять собой жидкость, текущую через сеть труб. Дуги просто представляют собой части сети транспортирования для специфического товара, и их веса представляют собой их максимальные пропускные мощности (возможности). Это могут быть, например, рельсы, дорожные или воздушные линии связи, или даже электрические или волокнисто-оптические кабели, если транспортируемый "товар" представляет собой цифровые сигналы. Т.е., если сеть — это модель железной дороги, а узлы представляют железнодорожные станции, то число, приписанное дуге, может быть равно количеству путей между двумя станциями. Другой пример, если сеть моделирует трубопровод, а узлы являются сочленениями, то это число может представлять площадь сечения трубы между двумя сочленениями. Оно определяет наибольшее количество жидкости, которое может пройти через дугу. Это число будем называют пропускной способностью дуги. Пропускную способность дуги e_ij обозначим через b_ij. Предполагается, что b_ij >0 при всех i, j.

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

Если D — сеть, которая имеет несколько источников и/или сливов, рис. 22, а. Мы можем определить сеть N, добавляя два узла V ₀ и V_n. к D, соединяя V ₀ с помощью направленной дуги с каждым из источников и соединяя каждый слив с помощью направленных дуг с узлом V_n, рис. 22, б; N имеет единственный источник и единственный слив. Веса, которые должны соответствовать этим дополнительным ребрам зависят от того, что собой представляет данная сеть. В случае планирования проблем, дополнительным ребрам был бы присвоен вес 0, так, чтобы время на завершение всего проекта не было бы искусственно увеличено. Если D сеть для определения максимального потока, то ребрам, исходящим из источника присваивают значения пропускных способностей не менее чем, суммарная пропускная способность выходящих дуг из следующего звена, а дополнительным дугам, входящим в слив – сумму пропускных способностей входящих дуг в предыдущий узел, см. рис. 17.

[1]

[1]

а) б)

Рис. 17. а - Сеть D; б – сеть N c одним источником и одним сливом

Поток в сети ведет себя не совсем так, как вода или другая жидкость. Обозначим через x_ij поток из V_i в V_j через дугу е_ij. Для потока имеется ограничение

. (7.1)

Кроме ограничения (7.1), потребуем, чтобы приток в каждый узел был равен оттоку из него; т. е. поток сохраняется в каждом узле (за исключением источника и слива):

при всех . (7.2)

Т.к. поток сохраняется в каждом узле, то отток в источнике должен быть равен притоку в сливе:

, (7.3)

где v – величина (цена) потока, т.е. полный поток приходящий на слив.

Набор значений x_ij, определенных для всех дуг сети и удовлетворяющих (7.1)-(7.3), называется потоком в сети. Поток наибольшей возможной величины называется максимальным потоком.

Легко видеть, что может существовать более одного максимального потока. Например, максимальная цена любого потока через сеть, представленную на рис. 18, a равна 3. В квадратных скобках дано значение пропускной способности каждой дуги, рядом поток по этой дуге. Имеются различные пути, которыми этот результат может быть достигнут. Максимальная цена всех возможных потоков равна 3, но имеется несколько различных максимальных потоков, которые достигают этого максимума. Два различных максимальных потока показаны на рис. 18, а и б.

а) б)

Рис. 18. Сеть с разными потоками и одинаковой ценой

Потоки в сетях широко используются во многих приложениях. Например, каково наименьшее число дуг, которые нужно удалить для разъединения двух заданных узлов графа? Этот вопрос является задачей теории графов, однако его можно решить, используя понятие потока.

Если сеть представляет собой цепочку V ₀, V ₁, V ₂, …, V_k , V_n, то наибольшая величина потока, который может пройти из V ₀в V_n при выполнении (7.1)-(7.3), равна

. (7.4)

Дуга с наименьшим значением пропускной способности является «узким местом» сети. Теперь определим понятие «узкого места» для произвольной сети. Узкое место сети называется разрезом.

Максимальная цена потока в сети тесно связана с идеей «разреза» сети, к описанию которой мы теперь переходим. Интуитивно ясно, что разрез можно рассматривать как множество ребер, которые, в случае их блокировки, полностью останавливают поток от источника к стоку. Однако, если какое-либо из ребер не заблокировано, то поток может и проходить. Сеть на рис. 18 имеет три различных разреза: { e ₁}, { е ₂, е ₃} и { е ₄}.

Разрезом сети N называется множество ребер, которое после удаления из N, порождают орграф с двумя компонентами, одна из которых содержит источник, а другая содержит слив.

И теперь более формальное определение разреза:

Разрез - это совокупность всех дуг, идущих из некоторого подмножества узлов в его дополнение. 0н обозначается через (),где X — заданное подмножество узлов, а - его дополнение. Таким образом, разрез (X, ) - это множество всех таких дуг e_ij, что либо и , либо и . Удаление всех дуг из разреза разобьет сеть на две или более компоненты. Разрез, разделяющий узлы V ₀и V_n - это такой разрез (), что и .

На рис. 19 сеть изображена условно.

Рис. 19. Условное представление сети и разреза

Емкостью разреза называется сумма весов его дуг.

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

Например, у сети, изображенной на рис. 18 разрез { e ₁} имеет емкость 4, разрез { е ₂, е ₃} – 14, и { е ₄} - 3.

Разрез является минимальным, если его емкость меньше или равна емкости любого другого разреза.

Замечание. В определении разреза учитываются все дуги между множествами X и , тогда как при вычислении его пропускной способности подсчитываются пропускные способности только дуг из X в , а дуги из в X игнорируются. Поэтому в общем случае .

Величина максимального потока всегда совпадает с минимальной пропускной способностью разреза, разделяющего V ₀и V_n. Разрез с наименьшей пропускной способностью, разделяющий V ₀и V_n, называется минимальным разрезом.

Факт совпадения величины максимального потока с пропускной способностью минимального разреза впервые был доказан А.Фордом и Д.Фалкерсоном в 1955г. Это центральная теорема теории потоков в сетях.

Теорема Форда и Фалкерсона (о максимальном потоке и минимальном разрезе). В любой сети с целыми значениями пропускных способностей дуг величина максимального потока из источника в слив равна пропускной способности минимального разреза, разделяющего источник и слив.

Доказательство. Дадим конструктивное доказательство теоремы, которое строит максимальный ноток и находит минимальный разрез. Доказательство показывает, что всегда существует поток, значение которого равно пропускной способности минимального разреза. Поскольку максимальный поток всегда не превосходит пропускной способности произвольного разреза, в частности, минимального разреза, то это и доказывает справедливость теоремы.

Если текущая величина потока равна пропускной способности некоторого разреза, то теорема доказана. Если величина потока не равна пропускной способности разреза, то ищем среди путей из V ₀в V_n такой, вдоль которого можно послать дополнительный поток. Это увеличивает величину потока. Продолжаем данную процедуру до тех пор, пока такого пути нельзя будет найти. Докажем, что величина потока равна пропускной способности некоторого разреза. Опишем систематический способ отыскания такого пути.

Начнем с произвольного множества величин Х_ij, удовлетворяющих (6.1) и (6.2) (например, X_ij = 0 при всех i и j). На основе текущего потока в сети рекурсивно определим подмножество узлов X при помощи следующих правил.

0. .

1. Если и , то .

2. Если и , то .

Все узлы, не лежащие в X, принадлежат . Используя данные правила определения множества X, рассмотрим два возможных случая.

Случай 1. . Следовательно, для всех дуг из X в справедливо (в силу правила 1) и не существует потока через дугу из в X (в силу правила 2). Поэтому

и

Следовательно, найден поток со значением, равным с ().

Случай 2. . Тогда существует путь из V ₀в V_n, образованный дугами, удовлетворяющими правилу 1 или правилу 2. Обозначим этот путь V ₀ ,…, V_i, e_ij, V_j,…, V_n. Каждая дуга в данном пути должна удовлетворять либо правилу 1, либо правилу 2. Если дуга удовлетворяет правилу 1, т. е. , то можно отправить дополнительный поток из V_i в V_j. Это увеличивает величину потока вдоль дуги. Такой тип дуги называется прямой дугой. Если же дуга удовлетворяет правилу 2, т. е. , то можно отправить поток из V_j, в V_i, фактически отменяя существующий поток вдоль дуги. Эффект состоит в сокращении величины потока вдоль дуги. Такой тип дуги называется обратной дугой. Данный путь по отношению к текущему потоку называется увеличивающим путем.

Например, возьмем сеть на рис. 20, где числа в квадратных скобках обозначают пропускные способности дуг. Если потоки на дугах равны x ₀₁ = х ₁₂= x _{2 n} = 1, а все остальные x_ij = 0, то е ₀₃, е ₃₂, е ₂₁, e _{4 n} является увеличивающим путем с обратной дугой e ₂₁.

Рис. 20.

Пусть ɛ ₁ — минимум среди всех разностей b_ij - x_ij в этом пути, ɛ ₂ - минимум среди x_ji в нем, а ɛ = min{ ɛ ₁, ɛ ₂} — целое положительное число. Тогда можно увеличить дуговые потоки на ɛ по всем прямым дугам пути и уменьшить дуговые потоки на ɛ по всем его обратным дугам. Таким образом, величина потока увеличивается на ɛ и новые значения x_ij удовлетворяют всем ограничениям (7.1) и (7.2). Теперь на основе нового потока можно переопределить множество X. Если V_n все еще лежит в X, то снова увеличиваем величину потока на некоторое ɛ. Поскольку пропускная способность минимального разреза — конечное число, а величина потока увеличивается по крайней мере на единицу, то после конечного числа шагов будет получен максимальный поток.

Теорема доказана.

Обозначим через F _{0 n} набор неотрицательных целых чисел x_ij, удовлетворяющих (6.1)-(6.3).

Следствие. Поток F _{0 n} максимален тогда и только тогда, когда относительно F _{0 n} не существует увеличивающего пути.