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

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

г = 1

любые два минимальных разреза. Тогда из теоремы 8.2 следует, что (Xi П Х2, X t f| Х 2) — тоже минимальный разрез. Пусть (Х3, Х 3) —еще один минимальный разрез. Снова используя теоре­

нибудь узел из X, если величина потока в сети равна с(Х, X). Отсюда следует, что множество X не содержит в качестве собствен­

ного подмножества ни одного из множеств Х 4, таких, что (X;, X, ) — минимальный разрез. В частности, X не может содержать в каче-

т

стве собственного подмножества и П -^г- Следовательно, учиты-

i —1

вая, что множество X является одним из множеств Х 4, получим

т

х = n Xt. а

г= 1

8.2.Метод расстановки пометок для нахождения максимального потока

Мы уже рассмотрели конструктивное доказательство теоремы о максимальном потоке и минимальном разрезе. Теперь остано­ вимся подробнее на алгоритме нахождения максимального потока. Как уже отмечалось в § 8.1, задача о максимальном потоке в сети , может быть сформулирована как задача линейного программиро-

\у вания. Однако метод расстановки пометок не является частным случаем симплекс-метода. В симплекс-методе происходит движе­ ние от одной вершины многогранника к другой, пока не будет достигнута оптимальная. Как станет ясно в дальнейшем, в методе расстановки пометок дело обстоит не так.

Метод расстановки пометок начинается с произвольного потока (в качестве начального можно взять нулевой поток). Затем пред­ принимается попытка получить поток с большей величиной. Вычисления заканчиваются, когда получен максимальный поток. Алгоритм заключается в систематическом поиске всех возможных путей из N s в N t, увеличивающих поток. Это осуществляется с помощью процедуры «расстановки пометок». Узлы получают специальные «пометки», указывающие направление, в котором

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

Алгоритм состоит из двух шагов. Шаг 1 — это процесс, в ходе которого узлы получают пометки. Шаг 2 заключается в измене­ нии потока. Шаги 1 и 2 повторяются до тех пор, пока увеличение потока становится невозможным.

Ш а г 1 (процесс расстановки пометок). На шаге 1 каждый узел находится в одном из трех состояний: «помечен и просмотрен»,, «помечен и не просмотрен» или «не помечен». Вначале все узлы не помечены. Пометка произвольного узла N s всегда состоит из двух частей. Первая часть — индекс i узла N и который указы­ вает, что можно «послать» поток из N г в N j. Вторая часть помет­ ки — число, указывающее максимальную величину потока, кото­ рый можно «послать» из источника N s в N], не нарушая ограниче­ ний на пропускные способности дуг.

Прежде всего источник N s получает пометку [s+, е (s) = оо]„ Первая часть этой пометки означает, что можно послать поток из узла N g в этот же узел; символ оо означает, что величина потока не ограничена сверху. Теперь узел N s «помечен и не просмотрен», а все остальные узлы «не помечены».

Вообще выберем любой помеченный и непросмотренный узел N j. Пусть он имеет пометку В+, е (/)] или В“, s (/)]. Два узла будем называть соседними, если они соединены дугой. Из всех узлов, соседних с N j, выделим те узлы N k, которые не помечены и для

теперь «помечены и не просмотрены».) После этого всем соседним

узлы N h теперь также «помечены и не просмотрены».) Теперь все узлы, соседние с N j, имеют пометки. Тогда узел N j считается поме­ ченным и просмотренным, и его можно больше не рассматривать на этом шаге. Может оказаться, что некоторые соседние с N j узлы помечены, а остальные не могут быть помечены (либо все соседние с А /узлы не могут быть помечены); в этих случаях узел N j также-

увеличивающего поток. Е сли принять такую процедуру, то появление отри­ цательного дугового потока на шаге 2 (изменение потока) будет означать, что дуговой поток имеет направление, противоположное направлению пер­ воначального дугового потока.

144 ГЛ. 8. МАКСИМАЛЬНЫЙ ПОТОК

считается помеченным и просмотренным. Знаки «+» и «—» в пер­ вой части пометок указывают, как должен быть изменен поток на шаге 2 .

Продолжим приписывать пометки узлам, которые являются соседними для помеченных и непросмотренных узлов, до тех пор, пока либо узел N t окажется помеченным, либо нельзя будет боль­

поток максимален. Если же N t помечен, то на шаге 2 можно найти путь, увеличивающий поток.

III а г 2 (изменение потока). Предположим, что сток N t имеет пометку [Ат, е (£)]. Тогда заменим xht на xht + е (t). Если же он имеет пометку [А;- , е (/)], то xtk заменим на xth — е (t). Затем в любом из этих случаев переходим к узлу N k. Вообще если узел N h имеет пометку [у'+, е (А;)], то xjh заменим на Xjk + е (t) и перей­ дем к узлу N у, если узел N h имеет пометку [/“, е (А;)],, то xhj заме­

ним на xkj — г (t) и перейдем к Nj. Продолжим эти действия, пока не достигнем источника N s. После этого сотрем все старые пометки узлов и вновь перейдем к шагу 1 .

Чтобы обеспечить конечность процесса, будем предполагать, что дуговые пропускные способности btj целочисленны. (Ниже будет рассмотрена модификация метода, обеспечивающая конеч­ ность процесса при любых неотрицательных Ъц.)

Когда алгоритм заканчивается на шаге 1, то получается мно­

Отсюда следует, что (X , X) — минимальный разрез, поток через который равен его пропускной способности. Таким образом, получен максимальный поток. G другой стороны, каждый раз величина потока увеличивается по крайней мере на единицу (предполагаем, что пропускные способности дуг и исходный поток являются целочисленными). Поскольку величина максимального потока ограничена сверху пропускной способностью минимально­ го разреза (целым числом), то алгоритм расстановки пометок конечен х).

Рассмотрим сеть, изображенную на рис. 8.4. Каждой ориенти­ рованной дуге поставлено в соответствие 2 числа. Первое из них —.

1 1А Если вычисления начались с целочисленного потока, то все после­ дующие потоки (в частности, максимальный), получаемые при работе рас­ смотренного алгоритма, будут целочисленными. Этот простой, но важный факт известен под названием т е о р е м ы о ц е л о ч и с л е н н о с т и : если пропускные способности дуг b t j целочисленны, то сущ ествует максимальный поток, который целочислен.— П р и м , п ерев .