Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

ности wt узлов целочисленны, и пусть F st — произвольный поток, не обязательно максимальный. Если величина этого потока равна пропускной способности некоторого разреза, то теорема доказана (ясно, что величина любого потока из N s в N t не превышает пропускной способности разреза, разделяющего N s и N t). В про­ тивном случае найдем цепь, с помощью которой можно увеличить поток. Для этого определим подмножество узлов X, такое, что поток может быть послан в любой узел, принадлежащий X.

Обозначим wtj = min (wt, Wj).

Используя текущий поток F st, определим рекуррентно множе­

При таком определении X возможны 2 случая.

Случай 1. Узел N t попадает в множество X. Покажем, что поток может быть тогда увеличен. Так как N s £ X, то должна существовать цепь из N s в N (, для дуг которой выполняются усло­ вия правил 1—3. Очевидно, что если выполняются условия пра­ вил 1—2, то поток вдоль такой цепи может быть увеличен. Если же

через узел N j остается равным пропускной способности Wj. Так как величины Wj целочисленны, то и е будет целым числом. А так как максимальный поток ограничен сверху, то поток из N s в N t может возрастать на е конечное число раз, и, следовательно, случай 1 может встретиться только конечное число раз.

Случай 2. Узел N t попадает в X. Покажем, что построенный поток равен пропускной способности некоторого разреза. Назовем соседние с X узлы у-узлами, или узлами из у. Утверждается сле­ дующее.

N j £ у, так как в противном случае узел N j попадал бы в X по пра­ вилу 2 .

Следовательно, xt = wt, т. e. узел N t насыщен. Очевидно, что насыщенный узел N t не может попасть в X по правилу 1. Далее, насыщенный узел N г не может попасть в X по правилу 2. Действи­ тельно, тогда существовал бы дуговой поток xip, где Np £ X.

Таким образом, все у-узлы являются насыщенными.

соседний с ним узел Nii £X. Поскольку N h$X, а узел Nj насы­

последовательность узлов Ni , Ni2, .. ., Nik, .. ., каждый из кото­

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

вании узла N hd X с xhj^> 0 неверно, и утверждения 3° —4° до­ казаны.

Таким образом, величина потока из N s в Ni равна 2 хц =

— 2 wj• Так как у-узлы—это все соседние узлы для узлов из X,

то множество у является разрезом. м

Можно разработать метод расстановки пометок, аналогичный методу, приведенному в гл. 8 и основанный на рассмотренных

трех рекуррентных правилах. Однако правило 3 требует, чтобы просматривались не только все узлы N h, соседние с каждым узлом, но также и все соседние для каждого узла N k. Это резко увели­ чивает объем вычислений. Рассмотрим процедуру расстановки пометок, которая основана только на правилах 1 и 2 .

Все узлы разбиваются на пять типов:

1. Помеченные узлы (П-узлы). Узел N t называется помечен­ ным, если по рекуррентным правилам 1 или 2 он попадает в мно­

жество X.

2. Помеченные и просмотренные узлы (ПП-узлы). Узел N t называется помеченным и просмотренным, если он является

П-узлом и просмотрены все . узлы, с ним соседние.

3.Отброшенные узлы'(О-узлы). Узел Nj называется отбро­ шенным, если он насыщен, т. е. xj — Wj.

4.Отброшенные и просмотренные узлы (ОП-узлы). Узел называется отброшенным и просмотренным, если он является

О-узлом, все соседние с ним О-узлы N h просмотрены и при этом

меченным, если он не принадлежит ни к одному из четырех пере­ численных выше типов.

Процедура расстановки пометок осуществляется следующим образом.

272 ГЛ. 12. ПОТОКИ В НЕПРЕРЫ ВНОЙ СРЕДЕ

Сначала помечают узлы, которые можно включить в X только по правилам 1 или 2. После этого производятся действия, анало­ гичные тем, которые осуществлялись на шаге 1 в § 8.2. При этом помеченные узлы получают пометку П, а отброшенные узлы получают пометку О. Если сток оказался помеченным (в этом случае говорят, что произошел прорыв), то поток увеличивают {как на шаге 2 в § 8 .2 ), затем стирают все пометки и вновь пере­ ходят к шагу 1 .

Если сток оказался непомеченным (произошел непрорыв), то просматриваются по очереди один за другим все О-узлы. Если

и получает пометку П. После этого просматривают все соседние

сN h 0-узлы и Н-узлы, ищутся среди них новые П-узлы и О-узлы. Если все узлы имеют пометки ОП, ПП или Н, то процедура рас­

становки пометок прекращается.' Если при этом N t £ X, то мак­ симальный поток построен.

В описанной процедуре расстановки пометок некоторый узел N j сначала может быть помечен как О-узел (если = wj), затем он может, стать ОП-узлом (если не существует О-узла N h, такого,

пометок, приписываемых некоторому узлу Nj, может быть сле­ дующей: Н — О — ОП -> П -> ПП. Следовательно, при осущ е­ ствлении описанной итерации расстановки пометок каждый узел просматривается вместе со своими соседями самое большее дважды *).

12.3. Потоки в непрерывной среде

Рассмотрим известную задачу вариационного исчисления. Имеется прямоугольная область со сторонами A, S, В, Т (рис. 12.3). В этой области определена ограниченная непрерывная весовая функция w (х, у) > 0. Надо найти кривую, соединяющую стороны А и В, такую, чтобы интеграл по этой кривой

j w (х, у) dc

был бы минимальным.

1) Преимущества этого алгоритма не очевидны, так как при «раздвое­ нии» узлов и дуг (см. примечание на стр. 268) число дуг становится равным п + 2 т , но каждая дуга просматривается только один раз, а здесь может оказаться, что каждую дугу понадобится просмотреть 4 раза.— Прим, перев.