Сайт в помощь студенту Грамоте учиться – всегда пригодится


Скачать полностью

ГЛАВА 2. ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ

2.1. ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ
Пусть G = (N, А) - ориентированная сеть с одним источни­ком s I N и одним стоком t I N, и пусть дуги (i, j) I А имеют ограниченную пропускную способность. Задача о максималь­ном потоке заключается в поиске таких потоков по дугам, при­надлежащим множеству А, что результирующий поток, проте­кающий из источника s в сток t, является максимальным. Предполагается, что в источник может поступать неограничен­ный поток, для каждого промежуточного узла сети вы­полняется условие сохранения потока, а пропускная способность Uij каждой дуги представляет собой конечную верхнюю границу потока fij по этой дуге.
Задача о максимальном потоке может быть сформули­рована в виде следующей задачи линейного программирования:

максимизировать                                                               (2.1)
при условии, что                  (2.2)
0 ? fij ? Uij , (i,j) I A.                                              (2.3)

 Поэтому для ее решения можно воспользоваться обычным симплексным методом. Однако существует бо­лее эффективная процедура поиска решения данной задачи. Алгоритм начинает работу с некоторого допустимого решения. Затем выполняется процедура расстановки пометок, разрабо­танная Фордом и Фалкерсоном, с помощью которой опре­деляется другой допустимый поток большей величины. В дан­ном алгоритме узлы рассматриваются как промежуточные пункты передачи потока, а дуги - как распределительные ка­налы. Для формального описания алгоритма необходимо вве­сти два основных понятия - пометки и аугментального пути потока.
Пометка узла используется для указания как величины по­тока, так и источника потока, вызывающего изменение теку­щей величины потока по дуге, соединяющей этот источник с рассматриваемым узлом. Если qj единиц потока посылается из узла i в узел j и вызывает увеличение потока по этой дуге, то узел j помечается из узла i символом + qj.
В данном случае узлу j приписывается пометка [+ qj, i]. Аналогично если посылка  qj единиц потока вызывает уменьше­ние потока по дуге, то узел j помечается из узла i символом - qj. В данном случае узлу j приписывает­ся пометка [- qj, i].
Текущий поток из узла i в узел j увеличивается, когда  qjединиц дополнительного потока посылается в узел j по ориен­тированной дуге (i, j) в направлении, совпадающем с ее ори­ентацией. В данном случае дуга (i, j) называется прямой.
Текущий поток из i в j уменьшается, когда qj единиц пото­ка посылается в узел j по ориентированной дуге (i, j) в направ­лении, противоположном ее ориентации. В этом случае дуга (i, j) называется обратной.
Если узел j помечается из узла i и дуга  (i, j) прямая, то поток по данной дуге увеличивается и величина, соответствую­щая оставшейся неиспользованной пропускной способности ду­ги, должна быть нужным образом скорректирована. Данную величину называют остаточной пропускной способ­ностью дуги. Если неко­торому узлу приписывается пометка и при этом используется прямая ветвь, то она может иметь только положительную «остаточную пропускную способность». Кроме того, узел j мо­жет быть помечен из узла i только после того, как узлу i при­писана пометка.
Аугментальный путь потока из s в t определяется как связ­ная последовательность прямых и обратных дуг, по которым из s в t можно послать несколько единиц потока. Поток по каж­дой прямой дуге увеличивается, не превышая при этом ее про­пускной способности, а поток по каждой обратной дуге умень­шается, оставаясь при этом неотрицательным.
Аугментальный путь потока используется для выбора такого способа измене­ния потока, при котором поток в узле t увеличивается и при этом для каждого внутреннего узла сети не будет нарушено ус­ловие сохранения потока.


2.1.1. ПРОЦЕДУРА РАССТАНОВКИ ПОМЕТОК ДЛЯ ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ
Задача о максимальном потоке часто встречается на прак­тике, причем число узлов и дуг в сети нередко достигает не­скольких тысяч. Поэтому для решения таких задач необходимо использовать эффективную процедуру вычислений. Благодаря простоте постановки задачи о максимальном потоке был раз­работан эффективный рекуррентный алгоритм поиска опти­мального решения (максимального потока), использующий про­цедуру расстановки пометок. Перейдем к описанию этого алго­ритма.

Пусть (i, j) - ориентированная дуга, ведущая из узла iв узел j. Поток по ней можно увеличить на qj единиц, если дуга (i, j) является прямой и узлу j приписывает­ся пометка [+ qj, i]. Предположим, что дуге  (i, j) уже приписан поток  fij ? 0 (fij ? Uij). Очевидно, что величина qj не может превосхо