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

Задача о критическом пути

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

При использовании указанных методов зависимость между отдельными работами задается с помощью некоторого орграфа Г,в котором каждая дуга отвечает определенной работе. Если в этом графе дуги образуют путь из вершины в вершину , то это означает, что выполнение работ s, для которых = , может начинаться лишь после завершения всех работ . Ввиду этого каждую вершину i орграфа Г интерпретируют как событие, означающее возможность выполнения тех работ s, для которых = i, т. е. завершение всех работ s, для которых = i. Приведенная интерпретация означает, что для выполнимости рассматриваемого комплекса работ соответствующий орграф Г не должен содержать контуров. Действительно, если бы имелся некоторый контур , то для выполнения каждой работы потребовалось бы предварительно завершить все остальные работы, что приводит к неразрешимому вопросу, типа известного вопроса о том, кто снес яйцо, из которого вылупилась первая курица.

Следовательно, практически реализуемые комплексы работ описываются орграфами Г, не содержащими контуров. Ясно, что в каждом таком орграфе имеется, по крайней мере, одна начальная вершина , для которой

Æ,

и, по крайней мере, одна конечная вершина , для которой

Æ.

В сетевом планировании обычно ограничиваются рассмотрением случая, когда = 1 является единственной начальной вершиной, a = n — единственной конечной вершиной. Первая из этих вершин интерпретируется как начальное событие, а вторая — как конечное событие, означающее завершение всего комплекса работ. При этом, как нетрудно проверить, для каждой вершины в орграфе Г имеется путь с концом в этой вершине и началом в вершине = 1. Точно так же для каждой вершины имеется путь из этой вершины в конечную вершину ⁼ n.

Рис. 16.

Легко проверить, что в орграфе Г, изображенном на рис. 16, нет контуров и в нем имеются одна начальная вершина = 1 и одна конечная вершина = 8. Жирной линией показан путь из начальной вершины = 1 в конечную вершину = 8.

Допустим теперь, что рассматриваемый комплекс работ описывается орграфом Г, обладающим указанными свойствами. Кроме того, известно время , необходимое для выполнения каждой работы . В этом случае, говорят, что имеется сетевой график Г,где .

Календарный план выполнения сетевого графика Г,определяется выбором m-мерного вектора

, (6.1)

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

, . (6.2)

При этом срок выполнения всего комплекса работ определяется величиной

. (6.3)

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

Задача о кратчайшем сроке. При заданном сетевом графике Г определить вектор (6.1), минимизирующий линейную функцию (6.3) при ограничениях (6.2).

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

Задача о критическом пути. При исходных данных задачи о кратчайшем сроке определить п-мерный вектор

x = (x₁, х₂, ..., х_m), , (6.4)

максимизирующий линейную функцию

(6.5)

при ограничениях

(6.6)

Ясно, что задача о критическом пути является частным случаем сетевой транспортной задачи, в которой = 1, = -1 и = 0, , a , .

Рассмотренные задачи могут решаться простым методом, сводящийся к последовательным просмотрам дуг сетевого графика.

Для каждой вершины , как уже отмечалось, имеется, по крайней мере, один путь р = {} с концом в этой вершине и началом в вершине = 1. Множество та­ких путей обозначим через и рассмотрим величины

, , . (6.7)

Нетрудно проверить, что они удовлетворяют соотношениям

, (6.8)

где — определяемый формулой (5.3) кратчайший срок для сетевого графика Г. Но тогда в качестве решения задачи о кратчайшем сроке может быть принят вектор (6.1) с компонентами (6.7).

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

, , (6.9)

где под ,как и выше, понимается множество дуг с концом в вершине i. Используя приведенные формулы, мы можем определить все величины (6.7) за просмотров списка дуг сетевого графика, где через обозначена максимальная длина путей . Соответствующий алгоритм для вычисления величин (6.7) поясним более подробно на числовом примере.

Пример 6.1. Рассмотрим сетевой график Г, отвечающий числовым данным, приведенным в табл. 10. Заметим, что соответствующий орграф Г совпадает с изображенным на рис. 16.

Таблица 10

s
is, js	1, 2	1, 3	1, 4	2, 5	3, 2	3, 5	3, 6	3, 7	4, 3	4, 7	5, 8	6, 8	7, 6	7, 8

Предположим, что уже имеются некоторые неотрицательные величины , . Тогда при просмотре очередной дуги s новое значение определяется по формуле

.

Получаемые при этом величины , очевидно также не превосходят . Далее, если при очередном просмотре всех дуг не происходит ни одного изменения величин , то это означает, что имеющиеся совпадают с искомыми величинами (6.9).

В качестве исходных принимаем =0, . Затем, просматривая дуги , последовательно находим новые значения

= 10, = 3, = 2, = 15, = 10, = 23, = 15, = 7, = 12, = 7, = 33, = 33, = 15, = 33,

которые приведены во второй строке табл. 11.

На втором просмотре дуг определяем новые значения величин , приведенные в третьей строке табл. 11. На третьем просмотре дуг ни одна из найденных величин не изменяется. Следовательно, полученные при втором просмотре величины ti совпадают с искомыми величинами .

Таблица 11

Рассмотренные величины (6.7) определяют минимально возможные сроки выполнения всех событий. При анализе сетевых графиков представляет интерес выявление имеющихся резервов в сроках выполнения отдельных событий. С этой целью через для каждой вершины обозначим множество путей из этой вершины в конечную вершину i= n. Затем рассмотрим величины

, , . (6.10)

Так как множество путей очевидно, совпадает с множеством путей , то

.

Что касается остальных вершин , то для них, очевидно, имеют место неравенства

, . (6.11)

При этом неотрицательные величины

, (6.12)

можно интерпретировать как имеющиеся резервы времени для выполнения соответствующих событий. Событие i сетевого графика Г называется критическим, если в соответствующем неравенстве (6.11) достигается равенство, т. е. резерв времени (6.12) для выполнения этого события равен нулю.

Для практического вычисления величин (6.10), как и в предыдущем случае, нет надобности в предварительном определении соответствующих множеств путей . Достаточно заметить, что интересующие нас величины (6.10) связаны между собой следующими соотношениями:

, (6.13)

где под понимается множество дуг с началом в вершине i.

Работу s сетевого графика Г называют напряженной если события и , являются критическими и при этом , или, что то же, . Ясно, что для определения всех критических событий и всех напряженных дуг достаточно вычислить величины (6.7) и (6.10).

Пример 5.2. Для сетевого графика Г, который уже рассматривался в связи с определением величин (см. пример 6.1), найдем величины , , , а также все критические события и напряженные работы. Исходные данные примера повторены в табл. 10 с тем, чтобы читатель мог проводить соответствующие выкладки, не отрываясь от текста. Кроме того, во второй строке табл. 11 приведены величины , , найденные при решении примера 6.1. Интересующие нас величины , , также определяются за просмотров дуг . Предпо­ложим, что уже имеются некоторые величины , , причем = = 42. Тогда при просмотре очеред­ной дуги s новое значение определяется по формуле

.

Получаемые при этом величины , очевидно, также не меньше . Далее, если при очередном просмотре всех дуг не происходит ни одного изменения величин t_i, то это означает, что имеющиеся t_i совпадают с искомыми величинами (6.10). В качестве исходных принимаем , . Затем за несколько просмотров дуг находим величины которые приведены в третьей строке табл. 12. В последнюю строку таблицы заносим величины , подсчитанные по формулам (6.12). Так как ===== 0, то соответствующие события являются критическими. Что касается напряженных работ, то таковыми являются работы s{3, 6, 9, 11). На рис. 16 соответствующие дуги отмечены жирными линиями.

Таблица 12

i

Лемма. Путь р = {s₁, s₂, .. ., s_l} из = 1 в = n в том и только том случае является критическим, когда соответствующим вершинам отвечают критические события, а дугам — напряженные работы.

Дана сеть, дуги которой ориентированы. В сети должны быть два специальных узла, называемых источник (исток) 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 .

а) б)

Рис. 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_2n = 1, а все остальные x_ij = 0, то е₀₃,е₃₂,е₂₁, e_4n является увеличивающим путем с обратной дугой e₂₁.

Рис. 20.

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

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

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

Следствие. Поток F_0n максимален тогда и только тогда, когда относительно F_0n не существует увеличивающего пути.