электронный учебник

"Экономико-математические методы"

 

На главную страницу

Графы и сети. Потоки в сетях

В конец страницы

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

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

        Узел s множества R называется источником потока f, если ; узел t называется стоком потока f, если ; узел х называется нейтральным, если . Поток с одним источником s и стоком t называется потоком от s к t. При всех    (все, что «вытекает» из источника, попадает в сток). Мощностью потока f называется число . Поток наибольшей мощности носит название максимального потока. Сечением (или разрезом) сети  относительно s и  t   называется   разбиение   узлов   R   на   такие   два   множества     и  , что  Пропускной  способностью  сечения  называется величина  (сумма пропускных способностей дуг, начала которых находятся в S, а концы – в ).

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

    Лемма. Если f – поток в сети  от  s  к  t  и   – сечение в сети G, то мощность потока  f  не превосходит , т. е.

                                                 .                                   (14.6)

Доказательство.

 .

Замечание. Если в (14.6) имеет место равенство, то сразу можно сделать вывод о максимальном потоке f и минимальном сечении .

    Теорема 14.6 (о максимальном потоке и минимальном сечении). Для любой сети величина максимального потока из  s  в  t  равна пропускной способности минимального сечения, отделяющего  s  от  t.

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

Будем говорить, что ребро  насыщенно потоком , если . Определим сечение  следующим образом. Узел , если  или если существует ненасыщенный путь от s к х, т. е. последовательность ребер , , …, , ни одно  из которых не является насыщенным. За  берется, как обычно, дополнение множества S. Чтобы показать, что  – сечение, нужно установить лишь принадлежность t к . Но если бы , то имелся бы ненасыщенный путь Р из s  в t, т. е. для всех ребер  . Тогда, если положить

,                          (14.7)

то можно определить новый поток , для которого

Отсюда следует, что мощность  больше мощности , а не , что противоречит максимальности потока .

Теперь можно показать, что в соотношении (14.6) имеет место равенство. Действительно, если бы было

,                                  (14.8)

то для некоторых  и  оказалось бы . С другой стороны, из определения S следует, что имеется ненасыщенный путь от  s к x. Так как ребро  также ненасыщено, то можно продолжить ненасыщенный путь от s к у, что противоречит . Следовательно, неравенство (14.8) невозможно и теорема доказана.

Алгоритм отыскания максимального потока в сети называется алгоритмом Форда Фалкерсона.

Этот алгоритм можно сформулировать следующим образом.

1°. Построить некоторый начальный поток  (например, поток, состоящий из нулевых компонент).

2°. Проверить, попала ли вершина  в множество вершин S, достижимых по ненасыщенным ребрам из вершины s. Если вершина t  не попала в множество S (случай а), то построенный поток максимален и алгоритм завершается. Если вершина t  попала в множество S (случай б), перейти к п. 3°.

3°. Выделить путь, состоящий из ненасыщенных ребер и ведущий из s в t, и увеличить поток через каждое ребро этого пути на величину  из (14.7). Построить новый поток и перейти к п. 2°.

Заметим, что алгоритм может завершиться, только если на каком-нибудь шаге будет иметь место случай а). На каждом шаге, на котором реализовался случай б), алгоритм может быть продолжен. Вместе с тем на каждом шаге при выполнении п. 3° образуется по крайней мере одно новое насыщенное ребро (то самое ребро, на котором достигается минимум в (14.7)). А так как число ребер в сети конечно, то п. 3° может выполняться лишь конечное число раз, поэтому указанный алгоритм обязательно построит максимальный поток, и притом за конечное число шагов.

Пример. Построить максимальный поток в сети, изображенный на рис. 14.7.

 

 

 

 

 

 

 Рисунок 14.7.

 Опишем сеть матрицей пропускных способностей:

 

 

s

1

2

3

4

5

6

t

 

s

0

1

4

0

0

4

0

0

 

1

1

0

0

1

1

0

2

0

2

4

0

0

2

0

0

0

1

3

0

1

2

0

0

0

3

0

 

4

0

1

0

0

0

3

1

0

 

5

4

0

0

0

3

0

0

1

 

6

0

2

0

3

1

0

0

6

 

t

0

0

1

0

0

1

6

0

 В качестве начального возьмем поток , в котором 1 единица перевозится по «верхнему» пути, 1 единица – по «нижнему» и 1 единица – по «среднему» пути; непосредственно из рисунка видно, что такой поток допустим для данной сети. Получим матрицу потока :

 

 

s

1

2

3

4

5

6

t

 

s

 

1

1

 

 

1

 

 

 

1

–1

 

 

 

 

 

1

 

2

–1

 

 

 

 

 

 

1

3

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

 

 

5

–1

 

 

 

 

 

 

1

 

6

 

–1

 

 

 

 

 

1

 

t

 

 

–1

 

 

–1

–1

 

 Найдем пути, которые не насыщены потоком . Вычтем  из :

 

 

s

1

2

3

4

5

6

t

 

s

0

3

 

 

3

 

 

 

1

2

 

 

1

1

 

1

 

2

5

 

 

2

 

 

 

0

3

 

1

2

 

 

 

3

 

 

4

 

1

 

 

 

3

1

 

 

5

5

 

 

 

3

 

 

0

 

6

 

3

 

3

1

 

 

5

 

t

 

 

 

 

 

2

7

 

 Опишем все узлы, которых можно достичь, идя из s по ненасыщенным ребрам. Это соответствует положительным элементам первой строки матрицы . Цепочка ненасыщенных ребер: (s, 2), (2, 3), (3, 6), (6, t).

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

min{3, 2, 3, 5} = 2.

Заметим, что если ненасыщенный путь неединственный, выбираем тот из них, для которого min является наибольшим.

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

 

 

s

1

2

3

4

5

6

t

 

s

0

1

 

 

3

 

 

 

1

2

 

 

1

1

 

1

 

2

7

 

 

0

 

 

 

0

3

 

1

4

 

 

 

1

 

 

4

 

1

 

 

 

3

1

 

 

5

5

 

 

 

3

 

 

0

 

6

 

3

 

5

1

 

 

3

 

t

 

 

2

 

 

2

9

 

 Цепочка ненасыщенных ребер: (s, 5), (5, 4), (4, 6), (6, t).

        Величина дополнительного потока: min{3, 1, 3, 3} = 1.

Вычитая из содержимого кружков 1 и добавляя 1 к содержимому квадратов, получим матрицу :

 

 

s

1

2

3

4

5

6

t

 

s

0

1

 

 

2

 

 

 

1

2

 

 

1

1

 

1

 

2

7

 

 

0

 

 

 

0

3

 

1

4

 

 

 

1

 

 

4

 

1

 

 

 

4

0

 

 

5

6

 

 

 

2

 

 

0

 

6

 

3

 

5

2

 

 

2

 

t

 

 

2

 

 

2

10

 

 Цепочка ненасыщенных ребер: (s, 5), (5, 4), (4, 1), (1, 6), (6, t).

        Величина дополнительного потока: min{2, 2, 1, 1, 2} = 1.

Матрица : 

 

 

s

1

2

3

4

5

6

t

 

s

 

0

1

 

 

1

 

 

 

1

2

 

 

1

2

 

0

 

2

7

 

 

0

 

 

 

0

3

 

1

4

 

 

 

1

 

 

4

 

0

 

 

 

5

0

 

 

5

7

 

 

 

1

 

 

0

 

6

 

4

 

5

2

 

 

1

 

t

 

 

2

 

 

2

11

 

 В этой матрице мы выделили все узлы, которых можно достичь из S. Они не включают t и потому вычисления закончены. Следовательно, множество S минимального сечения есть {s, 2, 4, 5}, = R\S = {1, 3, 6, t}. Из первоначальной матрицы пропускных способностей находим, что

 C(s, 1) + C(2, 3) + C(2, t) + C(4, 1) + C(4, 6) + C(5, t) =

= 1 + 2 + 1 + 1 + 1 + 1 = 7.

Мы должны, наконец, определить матрицу максимального потока , но она, очевидно, равна . В результате получим: 

 

 

s

1

2

3

4

5

6

t

 

s

 

1

3

 

 

3

 

 

 

1

–1

 

 

 

–1

 

2

 

2

–3

 

 

2

 

 

 

1

3

 

 

–2

 

 

 

2

 

 

4

 

1

 

 

 

–2

1

 

 

5

–3

 

 

 

2

 

 

1

 

6

 

–2

 

–2

–1

 

 

5

 

t

 

 

–1

 

 

–1

–5

 

 Общий поток, выходящий из s, равен сумме чисел первой строки и, конечно, равен общему стоку в t, который представляет сумму элементов последнего столбца. Мощность максимального потока равна 7, что совпадает с пропускной способностью минимального сечения. Это может служить проверкой правильности вычислений. На рис. 14.2 изображен этот поток.

 

Назад    К началу страницы     Вперед