Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.3. Графы, у которых пропускные способности дуг ограничены сверху и снизу

Рассмотрим граф дуги которого имеют пропускные способности (верхние границы потока), скажем, а также имеют нижние границы потока, скажем, Допустим,

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

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

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

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

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

Теорема 3. Если значение максимального потока (от в графе не равно графе не существует никакого допустимого потока.

Доказательство этой теоремы предлагаем в качестве упражнения читателю (см. задачу 5).

<< Предыдущий параграф Следующий параграф >>
Оглавление