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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 2. Нахождение максимального потока: алгоритм и теорема 51
Лемма 2. Для любого потока f и любого разреза (X,
¯
X)
val(f) 6 c(X,
¯
X).
Доказательство следует из определений соответствующих вели-
чин.
Лемма 3. Если для некоторого потока f
0
и некоторого разреза
(X
0
,
¯
X
0
)
val(f
0
) = c(X
0
,
¯
X
0
), (1)
то величина потока f
0
— максимально возможная, а пропускная
способность разреза (X
0
,
¯
X
0
) — наименьшая из пропускных способ-
ностей разрезов сети.
Д о к а з а т е л ь с т в о. Действительно, для произвольного
потока f и произвольного разреза (X,
¯
X) из леммы 2 и равенства (1)
следует:
val(f) 6 c(X
0
,
¯
X
0
) = val(f
0
) 6 c(X,
¯
X). ¤
Для краткости поток максимальной величины называют макси-
мальным потоком, а разрез с минимальной пропускной способностью
— минимальным разрезом.
§ 2. Нахождение максимального потока: алгоритм и
теорема
В этом параграфе излагается алгоритм построения максимально-
го потока и теорема о максимальном потоке и минимальном разрезе
(Форд и Фалкерсон, 1955).
Пусть некоторый поток f в сети уже имеется, например, поток с
нулевыми значениями на всех дугах. Алгоритм Форда—Фалкерсона
состоит из двух чередующихся процедур — помечивания вершин и
изменения потока.
Помечивание вершин. Вершины снабжаются метками, состоящи-
ми из двух элементов. Источник s получает условную метку (−, ∞).
Теперь пусть имеется некоторое множество помеченных вершин. Вы-
бираем любую из них и обрабатываем ее. Обработка i-ой вершины с
меткой (x, ε) состоит в помечивании из вершины i смежных непоме-
ченных вершин по следующему правилу:
если i → j и f
ij
< c
ij
, то вершине j присваивается метка
(i
+
, min(ε, c
ij
− f
ij
));
если i ← j и f
ji
> 0, то вершине j присваивается метка
(i
−
, min(ε, f
ji
)).
Затем обрабатывается другая помеченная вершина и так далее.
§ 2. Нахождение максимального потока: алгоритм и теорема         51


    Лемма 2. Для любого потока f и любого разреза (X, X̄)
                           val(f ) 6 c(X, X̄).
    Доказательство следует из определений соответствующих вели-
чин.
    Лемма 3. Если для некоторого потока f0 и некоторого разреза
(X0 , X̄0 )
                         val(f0 ) = c(X0 , X̄0 ),               (1)
то величина потока f0 — максимально возможная, а пропускная
способность разреза (X0 , X̄0 ) — наименьшая из пропускных способ-
ностей разрезов сети.
    Д о к а з а т е л ь с т в о. Действительно, для произвольного
потока f и произвольного разреза (X, X̄) из леммы 2 и равенства (1)
следует:
             val(f ) 6 c(X0 , X̄0 ) = val(f0 ) 6 c(X, X̄). ¤
    Для краткости поток максимальной величины называют макси-
мальным потоком, а разрез с минимальной пропускной способностью
— минимальным разрезом.

    § 2. Нахождение максимального потока: алгоритм и
                          теорема

    В этом параграфе излагается алгоритм построения максимально-
го потока и теорема о максимальном потоке и минимальном разрезе
(Форд и Фалкерсон, 1955).
    Пусть некоторый поток f в сети уже имеется, например, поток с
нулевыми значениями на всех дугах. Алгоритм Форда—Фалкерсона
состоит из двух чередующихся процедур — помечивания вершин и
изменения потока.
    Помечивание вершин. Вершины снабжаются метками, состоящи-
ми из двух элементов. Источник s получает условную метку (−, ∞).
Теперь пусть имеется некоторое множество помеченных вершин. Вы-
бираем любую из них и обрабатываем ее. Обработка i-ой вершины с
меткой (x, ε) состоит в помечивании из вершины i смежных непоме-
ченных вершин по следующему правилу:
      если i → j и fij < cij , то вершине j присваивается метка
  +
(i , min(ε, cij − fij ));
      если i ← j и fji > 0, то вершине j присваивается метка
  −
(i , min(ε, fji )).
Затем обрабатывается другая помеченная вершина и так далее.

Страницы