Федоров В.Н. - Введение в теорию графов (1023556), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

.

Назовем цепь ненасыщенной, если все её прямые дуги являются ненасыщенными, а все обратные дуги – положительными.

Цепь насыщена, если, по крайней мере, одна из её дуг (прямая или обратная) имеет

s–t цепь Р называется дополняющей, если она является ненасыщенной. Для s–t цепи Р неравенство >0 справедливо тогда и только тогда, когда она является дополняющей.

Для дополняющей s–t цепи Р в сети N можно определить новый поток следующим образом:

В дугах, не принадлежащих цепи P, поток не изменяется.

Очевидно, что val( ) = val(f) + .

Таким образом, val( ) > val(f) тогда и только тогда, когда Р является дополняющей цепью. Другими словами, поток f не максимален, если в сети существует дополняющая цепь.

В качестве примера рассмотрим сеть N, изображенную на рис. 13.1.

Пусть поток f будет таким, каким он показан на этом рисунке. В цепи Р, состоящей из е₂, е₅, е₇ и е₈, дуги е₂, е₇ и е₈ – прямые, а е₅ – единственная обратная дуга. По отношению к потоку f имеем

= 1, = 1, = 1, = 2.

Следовательно,

Так как >0, то Р является дополняющей цепью.

Измененный на цепи Р поток представлен на рис. 13.2. Отметим, что получен увеличением потока на всех прямых дугах Р на величину и его уменьшением на обратной дуге Р на величину . Потоки в остальных дугах остаются неизменными.

Р
исунок 13.2

Поток в сети называется полным, если любой s–t путь содержит, по крайней мере, одну насыщенную дугу. Полный поток не обязательно максимальный, иначе говоря, нельзя увеличить поток сети до максимального, рассматривая только пути. Иногда это можно сделать, рассматривая s–t цепи.

Поток в транспортной сети N максимален тогда и только тогда, когда в сети нет не только дополняющих путей, но и дополняющих цепей.

Дополняющих цепей в сети нет, если во всех возможных цепях между s и t имеется хотя бы одна насыщенная или нулевая дуга. (Такие дуги имеют ). Эти дуги всех возможных цепей (по одной дуге в цепи, если их несколько) образуют разрез сети, разделяющий s и t. Если бы это было не так, то существовала бы какая–нибудь дополняющая цепь.

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

Разрез с минимальной суммарной пропускной способностью называется минимальным разрезом.

Поскольку все s–t цепи насыщены, то поток в сети не может быть увеличен, следовательно, он максимален. Таким образом, величина максимального потока в сети равна пропускной способности минимального разреза.

13.2. Алгоритм нахождения максимального потока

Рассмотрим алгоритм определения максимального потока в сети. Этот алгоритм состоит из двух фаз.

В первой фазе по заданному потоку, используя процедуру пометок вершин, проверяем, существует ли хотя бы одна дополняющая цепь.

Если такой цепи нет, то данный поток максимален.

Иначе переходим ко второй фазе, в которой, используя метки, полученные в первой фазе, определим дополняющую цепь Р – и получим измененный на основе цепи Р поток .

Затем первая фаза повторяется для нового потока .

В первой фазе метка вида (d_v, _v) приписывается вершине v.

Первый символ d_v в метке указывает на вершину, из которой v получила эту метку. Она также указывает и направление помечивания – прямое или обратное.

Второй символ показывает возможное приращение потока в сети.

Если вершина сток t получает метку, то это значит, что существует ненасыщенная s—t цепь Р и что для этой цепи = _t.

Первая фаза начинается с пометки источника парой (–, ). Здесь значение d_s несущественно. Пометка остальных вершин происходит в соответствии со следующими правилами.

Предположим, что вершина и помечена, а вершина v нет. Пусть е – дуга, связывающая и и v.

Прямое помечивание. Если дуга e прямая, т.е. е = (u, v), то прямое помечивание v из и вдоль дуги е возможно, если c(e)>f(e). В этом случае v получает метку (u⁺, _v), где _v = min{ _u, c(e) – f(e)}.

Обратное помечивание. Если e обратная дуга, т. е. е = (v, и), то обратное помечивание v из и вдоль дуги е возможно, если f(e)>0. В этом случае v получает метку (и^–, _v), где _v = min{ _u, f(e)}.

На первой фазе вершины помечаются только однажды.

Эта фаза завершается, когда, либо

• вершина t получает метку, либо

• вершина t не помечена, и ни одну из вершин нельзя пометить.

Если t получает метку в первой фазе, то из правил помечивания следует, что существует дополняющая цепь Р и = _t, которая прослеживается во второй фазе в обратном направлении с помощью символов d_v и определяется измененный на основе Р поток .

Затем первая фаза повторяется применительно к новому потоку .

Если первая фаза завершается, не приписав метки вершине t, то это означает, что ни одной дополняющей цепи нет и, следовательно, имеющийся поток максимален.

Формальное описание алгоритма, предложенного Фордом и Фалкерсоном, представлено ниже.

Алгоритм:

1. Выбрать какой–либо поток f в сети. можно положить f(e) = 0 для всех дуг в N.

2. Пометить s парой (–, ). (Начинается фаза 1.)

3. Если существуют непомеченные вершины, которые можно пометить с помощью прямого или обратного помечивания, то выбрать одну такую вершину v. (Правила выбора вершин см. ниже.) Пометить ее и перейти к шагу 4. Иначе идти к шагу 7.

4. Если v = t, то идти к шагу 5. (Фаза 1 завершена.) Иначе к шагу 3.

5. (Начинается фаза 2.) Пусть метка вершины v есть (d_v, _v). Тогда выполнить следующие действия:

если d_v= u⁺, то положить f(и, v) = f(u, v) + _t,

если d_v= u^–, то положить f(v, u) = f(v, u) – _t.

1. Если u = s, то удалить все метки (фаза 2 завершена) и идти к шагу 2. Иначе положить v = u и идти к шагу 5.

2. СТОП. (Полученный поток f – максимален.)

В рассмотренном алгоритме выбор вершин для помечивания производится в произвольном порядке, что может привести к зацикливанию. Для устранения этого недостатка выбор вершин следует производить руководствуясь правилом “первая помечена – первая должна использоваться для продолжения помечивания вершин”. “Использование” здесь означает помечивание (когда это возможно) всех непомеченных вершин, смежных с рассматриваемой вершиной. В этом случае алгоритм закончит работу через конечное число шагов, причем число построенных цепей не превысит m(n+2)/2, где n – число вершин сети, m – число дуг.

Пример. Рассмотрим сеть N, представленную на рис. 13.3. На рисунке рядом с каждой дугой е показаны значения с(е) и f(e) соответственно.

В качестве начального потока принимаем f(e) = 0 для всех дуг сети.

Р
исунок 13.3

Начиная с метки (–, ) для источника s, помечаем (шаг 3 алгоритма) вершины а, b, с, d и t в указанном порядке. Получаем метки

а: (s⁺, 3), b: (а⁺, 3), с: (а⁺, 3), d: (c⁺, 2), t: (b⁺, 2).

Первая фаза завершается, так как вершина t помечена.

Во второй фазе определяем дополняющую цепь Р и измененный поток f₁ (шаги 3 и 6 алгоритма).

Первый символ в метке t есть b⁺. Это означает, что в цепи Р вершина b предшествует вершине t. Первый символ в метке b указывает, что вершина а предшествует вершине b. Аналогично видим, что s предшествует а в цепи Р. Таким образом, Р: .

Все дуги в Р являются прямыми, поэтому для получения измененного потока f₁ увеличиваем потоки во всех дугах пути Р на _t = 2.

Поток f₁ имеет величину, равную 2, и изображен на рис.13.4, а.

Стираем метки всех вершин. Имея поток f₁, получаем новое множество меток, показанных на рис. 13.4, а. Добавляющая цепь по отношению к f₁ состоит из вершин s, с, d, t в указанном порядке. Все дуги в этой цепи Р являются прямыми, _t = 2. Поэтому потоки в этих дугах увеличиваются на 2.

Получающийся поток f₂ = 4 показан на рис. 13.4, б.

Р
исунок 13.4

Новые метки, основанные на f₂ = 4, показаны на рис.13. 4, б.

Дополняющая цепь по отношению к f₂ состоит из вершин s, с, b, а, d, t. Дуга, соединяющая вершины а и b, является обратной дугой в этой цепи. Все другие дуги являются прямыми. _t = 1. Увеличим потоки в прямых дугах на 1 и настолько же уменьшим поток в обратной дуге. Получающийся в результате поток f₃ = 5 представлен на рис. 13.4, в.

Имея f₃, переходим к помечиванию вершин. Этот процесс завершается в состоянии, показанном на рис. 13.4, в, когда вершина t еще не помечена. Таким образом, не существует дополняющей цепи по отношению к потоку f₃. Поэтому f₃ = 5 – максимальный поток.

13.3. Результаты исследования сети

Пусть S – множество вершин, помеченных на рис.13.4, в.

Тогда S = {s, а, b, с}, а = {d, t} – разрез < >, являющийся минимальным разрезом.

Этот разрез проходит через дуги: (c, d), (a, d), (d, b), (b, t).

Из рисунка видно, что все дуги полученного разреза насыщены.

c( ) = 2+1+2 = 5 – пропускная способность дуг разреза и сети,

f( ) = 2+1+2 = 5 – прямой поток через дуги разреза,

f( ) = 0 – обратный поток через разрез.

Характеристики

Список файлов книги