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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

50 Глава 3. Задача о максимальном потоке в сети
ведущих в обратном направлении, то есть, число
f(X,
¯
X) =
X
i→j
i∈X, j∈
¯
X
f
ij
−
X
i→j
i∈
¯
X,j∈X
f
ij
.
На рис. 1 указаны два разреза сети — вертикальной чертой и вол-
нистой линией. Для первого разреза пропускная способность равна 9,
величина потока равна 3. Для второго, соответственно, 7 и 3.
Лемма 1. Величина потока через любой разрез одна и та же.
Д о к а з а т е л ь с т в о. Пусть (X ,
¯
X) — произвольный разрез, j
— любая вершина из X, но не источник. Докажем, что через разрез
(X \ {j},
¯
X ∪ {j}) протекает поток той же величины, что и через
(X,
¯
X). После перемещения вершины j инцидентные ей дуги иначе
влияют на величину потока через разрез. А именно,
f
³
X \ {j},
¯
X ∪ {j}
´
= f(X,
¯
X) +
X
i→j
i∈X
f
ij
+
X
i→j
i∈
¯
X
f
ij
−
X
j→l
l∈X
f
jl
−
X
j→l
l∈
¯
X
f
jl
.
Однако, в силу свойства 2) потока сумма последних четырех слага-
емых в правой части равенства равна нулю. Удалив из X еще одну
вершину k и рассуждая вполне аналогично, получим
f
³
X \ {j, k},
¯
X ∪ {j, k}
´
= f(X,
¯
X).
Продолжая перемещения вершин, на некотором шаге получим равен-
ство
f(X,
¯
X) = f({s},
¯
{s}) =
X
l: s→l
f
sl
.
Итак, величина потока через любой разрез равна суммарной величине
потока на дугах, выходящих из источника. Этим завершено доказа-
тельство леммы. ¤
В частности,
X
l: s→l
f
sl
=
X
m: m→t
f
mt
,
то есть, сумма потоков на дугах, выходящих из источника, равна сум-
ме потоков на дугах, входящих в сток. Лемма 1 делает законным сле-
дующее определение.
Величиной val(f) потока f называется величина потока через
(любой) разрез сети.
50                                Глава 3. Задача о максимальном потоке в сети


ведущих в обратном направлении, то есть, число
                            X           X
                f (X, X̄) =     fij −        fij .
                                    i→j               i→j
                                  i∈X, j∈X̄         i∈X̄,j∈X


   На рис. 1 указаны два разреза сети — вертикальной чертой и вол-
нистой линией. Для первого разреза пропускная способность равна 9,
величина потока равна 3. Для второго, соответственно, 7 и 3.
     Лемма 1. Величина потока через любой разрез одна и та же.
    Д о к а з а т е л ь с т в о. Пусть (X, X̄) — произвольный разрез, j
— любая вершина из X, но не источник. Докажем, что через разрез
(X \ {j}, X̄ ∪ {j}) протекает поток той же величины, что и через
(X, X̄). После перемещения вершины j инцидентные ей дуги иначе
влияют на величину потока через разрез. А именно,
  ³                   ´               X        X         X       X
 f X \ {j}, X̄ ∪ {j} = f (X, X̄) +       fij +     fij −   fjl −   fjl .
                                              i→j      i→j     j→l    j→l
                                              i∈X      i∈X̄    l∈X    l∈X̄


Однако, в силу свойства 2) потока сумма последних четырех слага-
емых в правой части равенства равна нулю. Удалив из X еще одну
вершину k и рассуждая вполне аналогично, получим
                ³                       ´
               f X \ {j, k}, X̄ ∪ {j, k} = f (X, X̄).

Продолжая перемещения вершин, на некотором шаге получим равен-
ство                                    X
                                    ¯ =
               f (X, X̄) = f ({s}, {s})   fsl .
                                                     l: s→l
Итак, величина потока через любой разрез равна суммарной величине
потока на дугах, выходящих из источника. Этим завершено доказа-
тельство леммы. ¤
   В частности,         X         X
                            fsl =      fmt ,
                         l: s→l           m: m→t
то есть, сумма потоков на дугах, выходящих из источника, равна сум-
ме потоков на дугах, входящих в сток. Лемма 1 делает законным сле-
дующее определение.
    Величиной val(f ) потока f называется величина потока через
(любой) разрез сети.

Страницы