Поиск максимального потока. 1 страница
Пусть задана сеть S. Введём важное понятие разреза сети. Разрезом сети называется та-кое множество С дуг сети S, после удаления которых сеть распадается на несколько изолиро-ванных друг от друга частей, так что источник x1 и сток xn оказываются в разных частях, при-чём ни одно подмножество С этим свойством не обладает.
Пример 4. В сети, показанной на рис.2, множество дуг {v4, v5, v6} образует разрез; разрез образуют также множества дуг {v6, v7, v8} и {v4, v5, v7, v9} (все эти разрезы показаны на рис.6). Множество дуг {v1, v5, v6, v8} разреза не образует (см. рис.7). Дуги, образующие указанные мно-жества, на рис.6 и 7 отмечены штриховкой ■
Рис.6
| 
Рис.7
Рис.8
|
Разрезы удобно изображать также линиями (не обязательно прямыми), «разрезающими» соответствующие дуги. На рис.8 показан разрез {v6, v7, v8}. Дуги относительно разреза «ведут себя» по-разному. Обозначим через Аs множество вершин, каждая из которых может быть сое-динена неориентированным путём с источником, через Аt- множество остальных вершин гра-фа, которые соединяются неориентированным путём со стоком.
Пример 4. Для разреза {v6, v7, v8}, показанного на рис.6b и 8
Аs = {x1, x2, x3, x4}, Аt = {x5, x6};
для разреза {v4, v5, v6} (рис.6а)
Аs = {x1, x2, x3}, Аt = {x4, x5, x6} ■
Легко понять, что каждая дуга разреза соединяет между собой вершины, лежащие в раз-ных множествах: одна в Аs, а другая в Аt. Дуга v называется прямой дугой разреза, если она выходит из Аs и входит в Аt; обратной, если она выходит из Аt и входит в Аs. В разрезе {v6, v7, v8} дуги v6 и v8 - прямые, а дуга v7 - обратная. Далее разрезы будем обозначать латинскими буквами A, B, ... .
Пусть u- поток в сети, Р(u) - величина этого потока. Потоком u(A) через разрез A назы-вается число, равное сумме потоков uj во всех прямых дугах разреза A минус сумма потоков uj во всех обратных дугах разреза A.
Утверждение 2. Для любого разреза A
u(A) = Р(u). (7)
Содержательно это утверждение понятно: все, что «вытекает» из источника, проходит по сети и «втекает» в сток. Это же количество продукта протекает через любой разрез. Поэтому надо сложить все, что течёт в нужном направлении (учтя с обратным знаком то, что течёт в противоположном направлении, т.е. по обратным дугам).
Пропускной способностьюс(A) разреза A называется сумма пропускных способностей всех его прямых дуг. Ясно, что для любого разреза A и любого потока в сети u
u(A) ≤ с(A). (8)Действительно, сумма потоков в прямых дугах разреза не превосходит с(A); потоки же в об-
ратных дугах входят в u(A) со знаком минус, откуда сразу следует (8).
Разрез A, пропускная способность которого с(A) минимальна (минимум берется по всем разрезам сети S), называется минимальным разрезом. Из определений минимального разреза, максимального потока и формул (7) и (8) следует, что максимальный поток в сети не превосхо-дит пропускной способности минимального разреза. Гораздо более сложным является следую-щее утверждением
Утверждение 3. Максимальный поток равен пропускной способности минимального раз-реза ■
Алгоритм поиска потока в сети, для которого выполняется указанное в утверждении 3 ра-венство, излагается далее.
Пример 6. Найдем минимальные разрезы (и тем самым величины максимальных потоков) в нескольких простых сетях. В сети рис.1 минимальный разрез образует дуги v1 и v2, выходящие из источника x1. Его пропускная способность равна 4-ём. В сети рис.2 минимальным является разрез {v6, v7, v8}, показанный на рис.6b и 8. Его пропускная способность равна 3. Обратим вни-мание, что дуга v7 (с пропускной способностью 5) здесь не учитывается, поскольку она является обратной дугой этого разреза. В сети рис.9 минимальный разрез указан линией. Его пропускная способность равна 3. В этом разрезе всего три дуги являются прямыми, остальные - обратны-ми.
Рис.9 ■
4.1. Алгоритм Форда-Фалкерсона (АФФ).Перейдем к изложению алгоритма, предло-женному американскими математиками Фордом и Фалкерсоном в 1945г. (впервые опубликован в 1951г.). Он находит поток u с максимальной величиной Р(u), т.е. решает задачу (1) - (3). В основе этого алгоритма лежит переход от уже построенного потока u к новому потоку u', тако-му, что Р(u') >Р(u). Если такой переход оказывается невозможным, то это значит, что потокuявляется решением исходной задачи (т.е. потокu уже является максимальным).
Алгоритм перехода от потока u к новому потоку u' состоит из четырёх этапов:
1. Построение меток у вершин сети (исходя из заданного потока u).
2. Построение так называемого увеличивающего пути между источником и стоком (ис-ходя из построенных на этапе 1 пометок).
3. Вычисление инкремента найденного увеличивающего пути (исходя из самого пути и заданного потока u).
4. Построение нового потока u' (исходя из заданного потока u, построенного на этапе 2 увеличивающего пути и вычисленного на этапе 3 инкремента) ■
Наиболее важным и сложным этапом является этап 1. Рассмотрим его отдельно, учитывая, в частности, то обстоятельство, что расстановка пометок у вершин используется в самых разно-образных задачах, связанных с графами (см., например, раздел 6-4.1).
1. Алгоритм расстановки меток. В процессе работы этого алгоритма каждая вершина сети находится в одном из следующих трёх состояний:
1. Не помечена.
2. Помечена и не просмотрена.
3. Помечена и просмотрена.
Каждая вершина может перейти из состояния с мéньшим номером в состояние с бóльшим номером (не помеченная вершина может стать помеченной и не просмотренной; помеченная и не просмотренная вершина может стать помеченной и просмотренной). Обратные переходы, как и изменение полученных меток, невозможны. Как и во всех других алгоритмах, при отсутс-твии явного указания после проверки условия всегда выполняется следующий шаг.
0. Инициализация. Источник x1 получает метку 0; вершина x1 объявляется помеченной и не просмотренной; все остальные вершины объявляются не помеченными.
1. Из множества помеченных и не просмотренных вершин произвольно выбираем любую. Пусть это будет вершинаxi.
2. Помечаем индексом i все не помеченные ранее вершины x, обладающие следующим свойст-вом: существует дуга vj, ведущая из хi в x, для которой uj<cj (говорят, что дуга vjне насыщена в прямом направлении). Вершина x объявляется помеченной и не просмотренной.
3. Если после выполнения шага 2 сток xnоказывается помеченным, алгоритм 1 расстановки по-меток завершает работу и следует переход к описываемому далее алгоритму 2 построения уве-личивающего пути.
4. Помечаем индексом i все не помеченные ранее вершины x, обладающие следующим свойст-вом: существует дуга vj, ведущая из xв хi, для которой uj> 0 (говорят, что дуга vjне насыщена в обратном направлении). Вершина x объявляется помеченной и не просмотренной.
5. Вершина xiобъявляется помеченной и просмотренной.
6. Если текущее множество помеченных и не просмотренных вершин не пусто, то переходим к шагу 1.
7. АФФ завершает работу. Рассматриваемый в качестве исходного для алгоритма 1 расстановки меток поток uявляется искомым максимальным потоком■
При реализации алгоритма целесообразно описывать сеть таблицей вида следующей таб-лицы 1. Таблица содержит n×n ячеек, каждая из которых состоит из двух клеток (напомним, что через n обозначено число вершин сети). Ячейка таблицы с номером (i, j), находящаяся на пере-сечении i-ой строки и j-ого столбца, делится на две клетки – левую и правую – и заполняется только в том случае, если в сети есть дуга, ведущая из вершины i в вершину j. Поскольку по определению потоковой сети из стока ни одна дуга не выходит, то последняя строка таблицы остаётся незаполненной. Поэтому она будет использоваться другим образом: в каждую её ячей-ку с номером j будет записываться текущее состояние вершины j (в левую клетку) и её метка (в правую клетку). Состояния вершин и метки определены при описании алгоритма. В основной части таблицы размера (n−1)×nв левую клетку ячейки (i, j) записывается поток по дуге (i, j), в правую – пропускная способность этой дуги. В отличие от состояний вершин, эти величины в процессе работы алгоритма расстановок меток не меняются.
Таблица 1. Общий вид таблицы для алгоритма расстановки меток
| • • • | j | • • • | n | ||||||
| • • • | |||||||||
| ••• | • • • | ||||||||
| i | • • • | • • • | • • • | u | c | • • • | • • • | ||
| ••• | • • • | ||||||||
| n–1 | • • • | ||||||||
| σ1 | μ1 | • • • | • • • | σj | μj | • • • | σn | μn | |
Если j – номер вершины, выбираемой на шаге 1, то при выполнении шага 2 просматрива-ются все ячейки таблицы, находящиеся в j-ой строке. По построению таблицы, заполненным ячейкам соответствуют вершины, в которые ведёт дуга из вершины j. Для каждой из них дела-ются операции шага 2 алгоритма. Затем (если следует переход на шаг 4) на шаге 4 просматрива-ются все ячейки таблицы, находящиеся в j-ом столбце. Для заполненных ячеек делаются опера-ции шага 4 алгоритма. Заметим, что ячейки (j, j) в таблице 1 при j<n никогда не заполняются, поскольку дуг вида (j, j), т.е. петель при вершине, в потоковых сетях не бывает. Ячейка (n, n) в последней строке содержит информацию, относящуюся к самой вершине n.
После изменения состояний и меток вершин в соответствии с шагами 2 и 4 вновь выбира-ется одна из вершин с состоянием 2 (если таковая существует) и выполнение алгоритма про-должается. Важно, что после инициализации, т.е. начального заполнения таблицы, рисунком, изображающим сеть, можно не пользоваться: таблица содержит всю необходимую информа-цию.
Пример 7. Применим алгоритм 1 расстановки пометок для сети, показанной на рис.2 и для удобства дальнейшего изложения перерисованной здесь. В качестве исходного рассмотрим
поток u = (2, 0, 1, 1, 1, 0, 0, 2, 0) (см. пример 2). При «ручной» реализации алгоритма воспользу-емся описанной непосредственно перед данным примером таблицей типа 1.
Таблица 2. Инициализация для расстановки пометок по заданному потоку
При инициализации таблицы 1, в соответствии с алгоритмом расстановки пометок, вер-шина 1 (источник) объявляется помеченной и не просмотренной (состояние 2), а все остальные вершины объявляются непомеченными (состояние 1). Метки при инициализации не определя-ются. В левую клетку ячейки (i, j) запишем поток по дуге (i, j), в правую – ограничение в ней. Таким образом, в таблице 1 представлен результат инициализации, и в этой таблице собрана вся необходимая для дальнейшего информация.
Итерация 1. Результаты итерации записываются в таблицу 2.1, которая сначала является просто копией таблицы 2. Выбирается любая помеченная и не просмотренная вершина в состо-янии 2. Таковая имеется только одна – вершина 1, поэтому она и выбирается. Далее, в соответс-твии с алгоритмом 1, рассматриваются все вершины, в которые ведут дуги из вершины 1. Этим вершинам соответствуют заполненные ячейки 1-ой строки: 2-ая и 3-ья. Поскольку в обеих ячей-ках число в левой клетке меньше числа в правой клетке, то это и значит, что обе дуги: v1 = (1, 2) и v2 = (1, 3) не насыщены в прямом направлении. Поэтому, в соответствии с алгоритмом, вер-шины 2 и 3 получают метку 1 и становятся отмеченными, но не просмотренными, т.е. перехо-дят из состояния 1 в состояние 2, что и отмечается в таблице 2.1. Далее, в соответствии с шагом 4 алгоритма, надо проверить вершины, из которых ведут дуги в вершину 1. Но поскольку за-полненных ячеек в 1-ом столбце таблицы 2.1 нет, то, значит, нет и таких вершин, и все опера-ции шага 4 просто не выполняются. Для завершения итерации осталось, в соответствии с шагом 5, перевести вершину 1 из состояния 2 в состояние 3 и отметить это в таблице 2.1.
Таблица 2.1.Итерация 1 расстановки пометок по заданному потоку
Итерация 2. Результаты итерации записываются в таблицу 2.2, которая сначала является просто копией таблицы 2.1. Выбирается любая помеченная и не просмотренная вершина (т.е. в состоянии 2). Таковых имеется две – вершины 2 и 3. Поскольку можно выбирать любую, для определённости здесь и далее будем выбирать вершину с минимальным номером. Таковой яв-ляется вершина 2. Далее, в соответствии с алгоритмом 1, рассматриваются все вершины, в кото-рые ведут дуги из вершины 2. Этим вершинам соответствуют заполненные ячейки 2-ой строки: 3-ья и 4-ая. Вершина 3 уже помечена (находится в состоянии 2) и, в соответствии с описанием шага 2, здесь не рассматривается. Вершина 4 ещё не помечена (находится в состоянии 1) и по-ток (1) в дуге (2, 4) меньше ограничения (12). Поэтому, в соответствии с шагом 2, вершина 4 по-лучает метку 2 и переходит в состояние 2 (она объявляется помеченной и не просмотренной). Далее, в соответствии с шагом 4 алгоритма, надо проверить вершины, из которых ведут дуги в вершину 2. Таковой является только вершина 1, которой соответствует единственная заполнен-ная клетка во 2-ом столбце. Но поскольку вершина 1 помечена, то операции шага 4 просто не выполняются. Для завершения итерации осталось, в соответствии с шагом 5, перевести верши-ну 2 из состояния 2 в состояние 3 и отметить это в таблице 2.2.
Таблица 2.2.Итерация 2 расстановки пометок по заданному потоку
Итерация 3. Результаты итерации записываются в таблицу 2.3, которая сначала является просто копией таблицы 2.2. Выбирается любая помеченная и не просмотренная вершина в со-стоянии 2. Таковых имеется две – вершины 3 и 4. Выберем вершину 3 (как имеющую мéньший номер). Далее, в соответствии с алгоритмом 1, рассматриваются все вершины, в которые ведут дуги из вершины 3. Этим вершинам соответствуют заполненные ячейки 3-ьей строки: 4-ая и 5-ая. Вершина 4 уже помечена (находится в состоянии 2) и, в соответствии с описанием шага 2, здесь не рассматривается. Вершина 5 ещё не помечена (находится в состоянии 1) и поток (0) в дуге (3, 5) меньше ограничения (1). Поэтому, в соответствии с шагом 2, вершина 5 получает метку 3 и переходит в состояние 2 (она объявляется помеченной и не просмотренной). Далее, в соответствии с шагом 4 алгоритма, надо проверить вершины, из которых ведут дуги в вершину 3. Таковыми являются вершины 1 и 2, которым соответствуют заполненные ячейки в 3-ем стол-бце. Но поскольку вершины 1 и 2 помечены, то операции шага 4 просто не выполняются. Для завершения итерации осталось, в соответствии с шагом 5, перевести вершину 3 из состояния 2 в состояние 3 и отметить это в таблице 2.3.
Таблица 2.3.Итерация 3 расстановки пометок по заданному потоку
Итерация 4. Результаты итерации записываются в таблицу 2.4, которая сначала является просто копией таблицы 2.3. Выбирается любая помеченная и не просмотренная вершина в со-стоянии 2. Таковых имеется две – вершины 4 и 5. Выберем вершину 4 (как имеющую мéньший номер). Далее, в соответствии с алгоритмом 1, рассматриваются все вершины, в которые ведут дуги из вершины 4. Этим вершинам соответствуют заполненные ячейки 4-ьей строки. Таковой является только 6-ая ячейка. Вершина 6 ещё не помечена (находится в состоянии 1), но поток (2) в дуге (4, 6) равен ограничению (2) в этой дуге. Поэтому, в соответствии с шагом 2 алгоритма, никаких меток не ставится. Далее, в соответствии с шагом 4 алгоритма, надо прове-рить вершины, из которых ведут дуги в вершину 4. Таковыми являются вершины 2, 3 и 5, кото-рым соответствуют заполненные ячейки в 4-ем столбце. Но поскольку все эти вершины уже по-мечены, то операции шага 4 просто не выполняются. Для завершения итерации осталось, в со-ответствии с шагом 5, перевести вершину 4 из состояния 2 в состояние 3 и отметить это в таб-лице 2.4.
Таблица 2.4.Итерация 4 расстановки пометок по заданному потоку
Итерация 5. Результаты итерации записываются в таблицу 2.5, которая сначала является просто копией таблицы 2.5. Выбирается любая помеченная и не просмотренная вершина в со-стоянии 2. Таковой является единственная вершина 5. Далее, в соответствии с алгоритмом 1, рассматриваются все вершины, в которые ведут дуги из вершины 5. Этим вершинам соответст-вуют заполненные ячейки 5-ой строки. Таковыми является 4-ая и 6-ая ячейка. Вершина 4 уже помечена, так что она не рассматривается. Вершина 6 ещё не помечена (находится в состоянии 1), и поток (0) в дуге (5, 6) меньше ограничения (4) в этой дуге. Поэтому, в соответствии с ша-гом 2 алгоритма, вершина 6 получает метку 5 и объявляется помеченной и не просмотренной, т.е. переходит в состояние 2, что и отмечается в таблице 2.5. Далее, в соответствии с шагом 3, алгоритм прекращает работу, поскольку сток – вершина 6 – теперь помечен.
Таблица 2.5.Итерация 5 расстановки пометок по заданному потоку
Задание 2. Применить алгоритм расстановки меток ко всем потокам из задания 1 (см. при-мер 7) ■
Рассмотрим теперь алгоритмы 2 - 4 по отдельности.
2. Алгоритм построения увеличивающего пути. Алгоритм 2 начинает работу, когда сток сети помечен.
1. Концом пути p является сток n.
2. Пусть уже построен путь от некоторой вершины xдо стока n. Пусть i- метка у вершины x. Тогда предыдущей вершиной пути p является вершина i.
3. Если вершина i является источником, то искомый путь pпостроен; переходим к алгоритму 3 вычисления инкремента пути p. В противном случае возвращаемся на шаг 2 ■
Пример 8. Применим алгоритм 2 построения увеличивающего пути для сети с метками, представленными в таблице 2.5. В соответствии с алгоритмом 2 путь p заканчивается в стоке 6. Поскольку у вершины 6стоит метка 5, предыдущей вершиной пути p является вершина 5. Предшествующей 5 вершиной является вершина 3, предшествующей 2 – источник 1. Поэтому сам увеличивающий путь от источника к стоку оказывается таким: 1→3→5→6 ■