Максимальный поток

Рассмотрим ориентированный граф. Будем рассматривать его как сеть труб, по которым некоторое вещество движется от истока (где оно производится с некоторой постоянной скоростью) к стоку (где оно потребляется - с той же скоростью). Вместо потоков вещества можно рассматривать движение тока по проводам, деталей по конвейеру, информации по линиям связи или товаров от производителя к потребителю.

Как и в задаче о кратчайших путях, на каждом ребре графа мы пишем число. Но если там это число означало длину пути, то теперь это скорее ширина дороги, или пропускная способность трубы - максимальная скорость потока в этой трубе. Например, она может быть 200 литров в час, или 20 ампер (если речь идёт об электричестве).

Мы считаем, что в вершинах вещество не накапливается - сколько приходит, столько и уходит (если вершина не является истоком или стоком). Это свойство называется «законом сохранения потока» (flow conservation). Для электрического тока это свойство называется первым правилом Кирхгофа.

Задача о максимальном потоке для данной сети состоит в следующем: найти максимально возможную скорость производства (и потребления) вещества, при которой его ещё можно доставить от истока к стоку при данных пропускных способностях труб. В этой главе после точной формулировки этой задачи (раздел 27.1) описаны два метода её решения. В разделе 27.2 разобран классический метод Форда-Фалкерсона. Его использование для поиск максимального паросочетания в двудольном неориентированном графе описано в разделе 27.3. Раздел 27.4 излагает схему «проталкивания предпотока» которая используется во многих современных алгоритмах для решения задач о потоках в сетях. Один из таких алгоритмов описан в разделе 27.5. Хотя он и не самый быстрый из известных (время работы 0(V3)), но он использует те же идеи, что и самые быстрые алгоритмы, и достаточно эффективен на практике.

27.1. Потоки в сетях

В этом разделе мы дадим точное определение сетей и потоков в них, обсудим их свойства, сформулируем задачу о максимальном потоке и введём некоторые полезные обозначения.

Сети и потоки

Назовем сетью (flow network) ориентированный граф G = (V, Е), каждому ребру (и, v) £ Е которого поставлено в соответствие число с(и, v) 0, называемое пропускной способностью (capacity) ребра. В случае (и, v) Е мы полагаем с(и, v) = 0. В графе выделены две вершины: исток (source) s и сток (sink) t. Для удобства мы предполгаем, что в графе нет «бесполезных» вершин (каждая вершина v £ V лежит на каком-то пути s v t из истока в сток). (В таком случае граф связен и \Е\ \V\ - 1.) Пример сети показан на рис.27.1.

Теперь дадим определение потока. Пусть дана сеть G = (V,E), пропускная способность которой задаётся функцией с. Сеть имеет исток s и сток t. Потоком (flow) в сети G назовём функцию / : V X V -> R, удовлетворяющую трём свойствам:

Ограничение, связанное с пропускной способностью (capacity constraint): f(u, v) c(u, v). для всех и, v из V.

Кососимметричность (skew symmetry): f(u,v) = -f(v,u) для всех и, v из V.

Сохранение потока (flow conservation):

для всех и из V - {s, t}.

Величина f(u, v) может быть как положительной, так и отрицательной. Она определяет, сколько вещества движется из вершины и в вершину v (отрицательные значения соответствуют движению в обратную сторону).

Величина (value) потока / определяется как сумма

(складываем потоки по всем рёбрам, выходящим из истока). Она обозначается / (не спутайте с абсолютной величиной числа!). Задача о максимальном потоке (maximum-flow problem) состоит в следующем: для данной сети G с истоком s и стоком t найти поток максимальной величины.

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

vEV

vEV

Рис. 27.1 27.1. (а) Сеть G = (V, Е), описывающие возможности перевозок продукции фирмы «Кленовые листья». Исток s - фабрика в Ванкувере, сток t - склад в Виннипеге. На каждом ребре написано максимальное число ящиков, которые можно отправить в день. (Ь) Пример потока / в сети G величины 19. Показаны только положительные значения /(u, v) > О (после косой черты стоит пропускная способность c(u,v).

него следует также, что f(u, и) = 0 для любой вершины и (положим и = v). Третье свойство означает, что для любой вершины и (кроме стока и истока) сумма потоков во все другие вершины равна нулю. Учитывая кососимметричность, это свойство можно переписать как

uev

(теперь переменная суммирования обозначена и) и прочесть так: «сумма всех потоков из других вершин равна нулю».

Заметим также, что если вершины и и v не соединены ребром, то поток между ними, то есть f(u, v), равен нулю. Действительно, если (и, v) Е и (v, и) Е, то с(и, v) = c(v, и) = 0. Тогда из первого свойства следует, что f(u, v) 0 и f(v, и) 0. Вспоминая, что f(u,v) = -f(v,u) (кососимметричность), мы видим, что f(u,v) = f(v,u) = 0.

Разделим вещество, поступающее в данную вершину v и вещество, из неё выходящее (то есть положительные и отрицательные значения f(u,v)). Сумму

Е(27-2)

uev

f{u,v)>0

назовём входящим (в вершину v) потоком. Выходящий поток определяется симметрично. Теперь закон сохранения потока можно сформулировать так: для любой вершины, кроме истока и стока, входящий поток равен исходящему. Пример сети

Рассмотрим пример на рис. 27.1 (а). Компания «Кленовые листья» производит хоккейные шайбы на фабрике в Ванкувере (исток s) и складирует их в Виннипеге (сток t). Она арендует место в грузовиках другой фирмы, и место это ограничено: из города и в город v можно доставить не более с(и, v) ящиков в день. Ограничения с(и, v) показаны на рисунке. Задача состоит в том, чтобы перевозить максимально возможное количество шайб из Ванкувера в Виннипег ежедневно. При этом путь может занимать несколько дней, и ящики могут ждать отправки в промежуточных пунктах, но необходимо, чтобы для каждого пункта число ежедневно прибывающих ящиков было равно числу увозимых (иначе ящиков не