Дискретная математика: графы и автоматы. Альпин Ю.А - 53 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

§ 2. Нахождение максимального потока: алгоритм и теорема 53
Докажем теорему о результатах работы алгоритма.
Теорема 1. Поток f, вычисленный алгоритмом, имеет макси-
мальную величину, а разрез (X,
¯
X), где X — множество вершин,
помеченных при последнем помечивании, имеет минимальную про-
пускную способность.
Д о к а з а т е л ь с т в о. Для всякой дуги (i, j), где i ∈ X, j ∈
¯
X,
верно f
ij
= c
ij
. Действительно, если допустить, что f
ij
< c
ij
, то j
должна была быть помечена из i по первому правилу помечивания.
А для всякой дуги (j, i), где i ∈ X, j ∈
¯
X, верно f
ji
= 0, поскольку
при f
ji
> 0 вершина j должна была быть помечена из i по второму
правилу помечивания. В силу этих свойств
f(X,
¯
X) = c(X,
¯
X),
и утверждение теоремы следует из леммы 3 §1. ¤
Если опустить детали, связанные с конкретным алгоритмом (су-
ществуют различные алгоритмы вычисления максимального потока),
теорему 1 можно сформулировать так:
Теорема 2 (о максимальном потоке и минимальном разрезе).
В любой сети существует максимальный поток. Величина макси-
мального потока равна пропускной способности минимального раз-
реза.
Пример 2. Требуется построить максимальный поток в сети
Рис. 2
Решение. (Ниже по технической причине вместо c
ij
, f
ij
пишем
c(i, j), f(i, j).) Начальный поток возьмем нулевой.
Помечивание вершин. Источник s получает метку (−, ∞). Для
смежной с s вершины a
1
имеем c(s, a
1
) − f(s, a
1
) = 4 − 0 = 4 > 0,
поэтому a
1
получает метку (s
+
, 4). Аналогично, для вершины a
3
име-
ем c(s, a
2
) − f(s, a
2
) = 3 − 0 = 3 > 0, поэтому a
3
получает метку
(s
+
, 3). Теперь вершина s обработана. Переходим к помеченной вер-
шине a
1
. Поскольку c(a
1
, a
2
) − f(a
1
, a
2
) = 6 − 0 = 6 > 0, можно
§ 2. Нахождение максимального потока: алгоритм и теорема                53


   Докажем теорему о результатах работы алгоритма.
   Теорема 1. Поток f , вычисленный алгоритмом, имеет макси-
мальную величину, а разрез (X, X̄), где X — множество вершин,
помеченных при последнем помечивании, имеет минимальную про-
пускную способность.
   Д о к а з а т е л ь с т в о. Для всякой дуги (i, j), где i ∈ X, j ∈ X̄,
верно fij = cij . Действительно, если допустить, что fij < cij , то j
должна была быть помечена из i по первому правилу помечивания.
А для всякой дуги (j, i), где i ∈ X, j ∈ X̄, верно fji = 0, поскольку
при fji > 0 вершина j должна была быть помечена из i по второму
правилу помечивания. В силу этих свойств
                          f (X, X̄) = c(X, X̄),
и утверждение теоремы следует из леммы 3 §1. ¤
    Если опустить детали, связанные с конкретным алгоритмом (су-
ществуют различные алгоритмы вычисления максимального потока),
теорему 1 можно сформулировать так:
    Теорема 2 (о максимальном потоке и минимальном разрезе).
В любой сети существует максимальный поток. Величина макси-
мального потока равна пропускной способности минимального раз-
реза.
    Пример 2. Требуется построить максимальный поток в сети




                                  Рис. 2

Решение. (Ниже по технической причине вместо cij , fij пишем
c(i, j), f (i, j).) Начальный поток возьмем нулевой.
     Помечивание вершин. Источник s получает метку (−, ∞). Для
смежной с s вершины a1 имеем c(s, a1 ) − f (s, a1 ) = 4 − 0 = 4 > 0,
поэтому a1 получает метку (s+ , 4). Аналогично, для вершины a3 име-
ем c(s, a2 ) − f (s, a2 ) = 3 − 0 = 3 > 0, поэтому a3 получает метку
(s+ , 3). Теперь вершина s обработана. Переходим к помеченной вер-
шине a1 . Поскольку c(a1 , a2 ) − f (a1 , a2 ) = 6 − 0 = 6 > 0, можно

Страницы