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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3
Задача о максимальном потоке в сети
§ 1. Основные леммы о потоках и разрезах в сети
Сеть — это орграф, в котором выделены две вершины — источ-
ник s и сток t . По определению из источника дуги могут лишь вы-
ходить, а в сток — лишь входить. Каждой дуге (i, j) сопоставлено
положительное целое число c
ij
— пропускная способность дуги.
Потоком в сети называется функция f, заданная на дугах сети,
принимающая целые значения и удовлетворяющая условиям:
1) 0 6 f
ij
6 c
ij
,
2)
P
i:i→j
f
ij
=
P
l:j→l
f
jl
, для любой промежуточной вершины j (то
есть, неравной s, t).
Число f
ij
называется величиной потока по дуге (i, j).
Пример 1. Рассмотрим сеть, изображённую на рис. 1.
Рис. 1
Первое из чисел, приписанных дуге, — пропускная способность, вто-
рое — величина потока по этой дуге.
Разрезом сети называется любое разбиение (X,
¯
X) множества вер-
шин на две части, такое, что s ∈ X, t ∈
¯
X. Пропускной способностью
разреза называется сумма пропускных способностей дуг, ведущих из
X в
¯
X, то есть, число
c(X,
¯
X) =
X
i→j
i∈X,j∈
¯
X
c
ij
.
Величиной потока через разрез называется сумма величин потока
на дугах, ведущих из X в
¯
X, минус сумма значений потока на дугах,
                             Глава 3
        Задача о максимальном потоке в сети


     § 1. Основные леммы о потоках и разрезах в сети

   Сеть — это орграф, в котором выделены две вершины — источ-
ник s и сток t. По определению из источника дуги могут лишь вы-
ходить, а в сток — лишь входить. Каждой дуге (i, j) сопоставлено
положительное целое число cij — пропускная способность дуги.
   Потоком в сети называется функция f , заданная на дугах сети,
принимающая целые значения и удовлетворяющая условиям:
   1) 0P6 fij 6 cijP
                   ,
   2)     fij =      fjl , для любой промежуточной вершины j (то
      i:i→j     l:j→l
есть, неравной s, t).
Число fij называется величиной потока по дуге (i, j).

   Пример 1. Рассмотрим сеть, изображённую на рис. 1.




                               Рис. 1

Первое из чисел, приписанных дуге, — пропускная способность, вто-
рое — величина потока по этой дуге.
    Разрезом сети называется любое разбиение (X, X̄) множества вер-
шин на две части, такое, что s ∈ X, t ∈ X̄. Пропускной способностью
разреза называется сумма пропускных способностей дуг, ведущих из
X в X̄, то есть, число
                                     X
                         c(X, X̄) =       cij .
                                     i→j
                                   i∈X,j∈X̄


    Величиной потока через разрез называется сумма величин потока
на дугах, ведущих из X в X̄, минус сумма значений потока на дугах,

Страницы