Материал: Проектное управление в строительстве. Баркалов С.А., Бурков В.Н

f(xi, xj) = – f(xj, xi),

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

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

∑f (xi , xj )≥0, для всех xj. V\ {x0; z}

xi V

Учитывая, что свойство сохранения потока в данном алгоритме выполняется в ослабленном виде, то есть требуется только выполнение условия неотрицательности предпотока, в ходе решения возникают ситуации, когда в вершине скапливается избыточный поток, величину которого в произвольной вершине v обозначаем через ef(v). Кроме того, для каждой из вершин сети u вводится понятие высоты h(u), задаваемой специальной функцией на множестве целых положительных числе и удовлетворяющей следующим свойствам:

h(z) = 0; h(x0) = n; h(u) ≤ h(v) + 1.

Алгоритм заключается в том, что последовательно выполняются два вида операций: передача потока, коротко называемая «проталкивание», и изменение высоты вершин, иначе называемая «подъем».

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

1.вершина u является активной, то есть в ней имеется избыточный поток ef(u);

2.имеются ненасыщенные дуги, то есть из данной вершины u выходит хотя бы одна дуга по которой еще можно передать поток, то есть поток по этой дуге еще не достиг ее пропускной способности;

3.высота данной вершины u удовлетворяет соотношению

h(u) ≤ h(v) + 1.

Вполне возможна ситуация, когда активная вершина, то есть вершина с накопленным потоком есть, а вот дуг, по которым можно передать этот поток или хотя бы его часть, нет (то есть отсутствуют допустимые дуги). В этом случае выполняется другая операция «подъем», заключающаяся в том, что у рассматриваемой вершины изменяется высота. Причем из всех вершин, с которыми связана рассматриваемая вершина, выбирается та, у которой высота минимальна и рассматриваемой вершине u присваивается значение высоты на единицу больше, то есть:

h(u)= min [h(v)+1],

(u,v) Ef

где Ef – остаточная сеть, то есть сеть, состоящая из ненасыщенных дуг, поток по которым еще можно увеличить.

Таким образом, каждая произвольная вершина u будет характеризоваться двумя величинами: избыточным потоком ef(u) и высотой h(u), а каждое ребро (u, v) – пропускной способностью cuv; величиной пропускаемого предпотока f(u, v) и потока φ(u, v).

В общем виде алгоритм выглядит следующим образом:

Подготовительный шаг. На этом шаге задаются начальные значения предпотока по всем дугам сети, значения избыточных потоков ef(u) для каждой вершины и высоты всех вершин. Предпоток для дуг, выходящих из источника, то есть вершины x0, в прямом направлении принимается равным пропускным способностям этих дуг, то есть f(x0, u) = cx0u , а в обратном направлении: f(u, x0) = –cux0. Для остальных дуг величина предпотока принимается равной нулю.

Значения избыточных потоков ef(u) по всем вершинам, выходящим из источника принимаются равными пропускной способности дуги (x0, u), то есть ef(u) = cx0u, значение избыточного потока в источнике уменьшается на величину cx0u; для всех остальных вершин, включая сток, данный параметр принимаются равными нулю.

95

Величина высоты для источника x0 назначается равная n, то есть h(x0)=n, а для всех остальных вершин, включая и сток, высота принимается равной нулю, то есть h(u)=0 для

всех u V\x0.

k-й шаг. Осуществляется проверка: если на рассматриваемой сети активные вершины или нет?

В том случае если на рассматриваемой сети нет активных вершин, то алгоритм заканчивается.

Если есть, то осуществляется выбор активной вершины для продолжения решения и проверяется: имеет ли выбранная активная вершина допустимые, то есть ненасыщенные, дуги?

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

= min[ef(u); cuv – f(u, v)]

Разность вида cuv – f(u, v), как правило, называют остаточной пропускной способностью дуги (u, v) и обозначают как cf(u, v).

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

В том случае, когда вершина не имеет инцидентных ей ненасыщенных дуг, тогда выполняется операция «подъема». Таким образом, данная операция применима для вершины u, если эта вершина активна, то есть выполняется неравенство e(u)>0, для каждой дуги (u,v), инцидентной вершине u и принадлежащей остаточной сети Ef ( (u,v) Ef будет выполняться условие h(u) h(v).

Операция «подъема» заключается в том, что среди всех вершин, смежных с рассматриваемой вершиной u выбирается вершина с минимальным значением высоты и рассматриваемой вершине присваивается высота равная величине

h(u) = min [h(v)+1] .

(u,v) Ef

Осуществляется переход к началу k-го шага.

Вычислительная сложность приведенного алгоритма проталкивания предпотока в классическом виде составляет О(V2E), где V – число вершин; E – число дуг.

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

Модификация исходного алгоритма «поднять в начало» позволяет получить вычислительную трудоемкость порядка O(V3). А правило, получившее условное название «выбор высшей активной вершины», то есть всегда выбирается вершина, имеющая наибольшую высоту, h(u) → max, обеспечивает снижение трудоемкости до величины O(V2

E ).

Существуют и другие модификация алгоритма, уменьшающие его трудоемкость.

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

Согласно теореме Форла-Фалкерсона задача о максимальном потоке эквивалентна задаче о минимальном разрезе, а согласно теории двойственности оказывается, что задача о минимальном разрезе может быть сведена к задаче о кратчайшем расстоянии в сети определенного вида. Ограничение накладывается на сам граф: он должен быть планарным

96

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

Утверждение. Двудольный связный граф не является планарным.

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

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

1 шаг. Источник исходной сети соединяют ребром с стоком этой же сети, но так чтобы новое ребро не пересекало никаких других ребер, то есть чтобы свойство планарности исходного графа сохранялось. Таким образом в результате этого шага вся плоскость оказывается разделенной на области, которые называются грани. Внутри каждой грани нет ни ребер, ни вершин и каждая область ограничена ребрами исходного графа. Новое ребро, соединяющее источник и сток разделило плоскость на две области-грани внутреннюю, находящуюся под вновь проведенным ребром и внешней, находящейся за пределами исходного графа.

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

3 шаг. В двойственной сети в качестве длин дуг будет приниматься пропускная способность дуги исходного графа, которую пересекает дуга двойственной сети. Отсюда и требование того, что только одна дуга может пересекать дугу исходного графа.

Процесс построения двойственной сети хорошо представлен на рис. 3 где в двойственной сети вершин для наглядности обозначены буквами. Дуга (s´; t´) представляет собой дополнительное ребро, делящее плоскость на внутреннюю и внешнюю части.

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

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

В данном случае каждая дуга заданной транспортной сети будет описываться кортежем

< cij; pij; φij >,

где cij – пропускная способность дуги (xi, xj ); pij – стоимость транспортировки единицы продукта по дуге (xi, xj ); φij – имеющийся поток по дуге (xi, xj).

Вычисление потока минимальной стоимости строится по двум известным классическим алгоритмам: Басакера-Гоуэна и Клейна.

97

t’

Рис. 3. Планарный граф или плоская сеть

Алгоритм Басакера-Гоуэна представляет собой следующую последовательность действий:

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

1 шаг. Вычислить модифицированные стоимости по каждому ребру графа по следующей формуле:

2 шаг. При полученных стоимостях определить кратчайший путь минимальной стоимости из источника 0 в сток n и пропускать по этому пути поток до тех пор, пока этот путь не перестанет быть кратчайшим. Получить величину нового потока, прибавив к величине старого величину потока, текущего по рассматриваемому пути. В том случае, когда величина суммарного потока окажется равной заданной величине v, то завершаем выполнение алгоритма, так как поток минимальной стоимости найден. Если же нет, то переходим вновь к шагу 1.

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

Для выполнения алгоритма Клейна необходимо выполнить следующую последовательность действий:

98

Предварительный шаг. Применяя любой из алгоритмов нахождения максимального потока, находим такой поток для заданной сети.

Шаг 2. Определяем модифицированные стоимости для каждой из дуг.

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

= min[φ(v, u); cuv – φ(u, v)] ,

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

Существенное упрощение алгоритма выполняется за счет того, что все ребра, входящие в минимальный разрез будут насыщенными, поэтому их модифицированные

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

Естественно возникает вопрос о том, как найти отрицательные контуры в произвольном графе. Эта задача с необходимостью приводит нас к алгоритмам нахождения кратчайшего расстояния в графах с отрицательными длинами дуг. Следует напомнить, что ребра отрицательной длины появляются в ходе вычисления модифицированных стоимостей по формуле (4). Для этой цели имеется несколько алгоритмов различной степени сложности. Вначале остановимся на самых простых алгоритмах, основанных на элементарных представлениях о том, что наличие отрицательного контура в любом графе однозначно приводит к тому, что задача о кратчайшем расстоянии не будет иметь конечного решения. Действительно, попав на контур отрицательной длины, мы при каждой итерации будем получать все более меньшее расстояние, чем на предыдущем шаге. В этом случае, происходит зацикливание алгоритма. Данный факт и может быть использован для установления самого факта наличия контуров отрицательной длины. С этой целью необходимо определить теоретически максимально возможное число шагов алгоритма по нахождению кратчайшего пути в графе. Самый простой подсчет дает следующие числа: при однократном просмотре всех дуг графа, а их количество обычно обозначается через m, как минимум становится известным расстояние от начальной вершины графа до одной из его вершин. Учитывая, что вершин в графе n, то получаем, что максимальное число шагов в любом алгоритме по нахождению кратчайшего расстояния в графе будет равно nm.

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

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

Стандартный алгоритм определения кратчайшего расстояния в графе предполагает задания для каждой из вершин графа индекса, связанного с расстоянием, который принято обозначать через λi. Предполагается, что величину этой характеристики ограничиваем числом di. В том случае, когда на некоторой итерации оказалось, что величина λi будет меньше наперед заданного значения di, необходимо осуществить проверку за счет чего произошло уменьшение: действительно за счет сокращения пути в графе или же в рассматриваемом графе имеется контур отрицательной длины.

99