Графы и сети. Харитонова Е.В. - 35 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

34
вытекающий из
b
, равен 4. Таким образом, оба потока совпадают, и в вершине
b
имеет место сохранение потока. Это верно также и для всех других вершин, за
исключением вершин
a
и
z
. Воспользуемся принципом сохранения потока для
доказательства того, что интуитивно кажется очевидным. А именно, поток из
a
равен потоку в
z
, т.е.
()
(
)
,
zпотокaпоток =
что и утверждает приведенная ниже
теорема. Рассмотрим сначала конкретную сеть.
Заметим, что для потока на рис 2.2 выполняется равенство
() ()
6.
== zпотокaпоток
Пусть
S
– множество вершин
{
}
,
d c, b,
а
T = V – S
–
множество вершин
{
}
.z f, a,
Если просуммировать потоки в
S
, то согласно при-
веденной ниже таблице 2.1 получим, что входящий поток равен 9 и выходящий
поток равен 9. Таким образом, разность потоков равна 0.
Таблица 2.1
вершина входящий поток ребро выходящий поток ребро
b 4 (a, b) 3 (b, c)
1 (b, d)
c 3 (b, c) 3 (c, z)
d 1 (e, d) 2 (d, z)
1 (b, d)
сумма 9 9
Если во множество
S
добавить вершину a, получим, что разность 15 (вы-
ходящий поток) и 9 (входящий поток) равна
(
)
.6
aпоток
=
Таблица 2.2
вершина входящий поток ребро выходящий поток ребро
b 4 (a, b) 3 (b, c)
1 (b, d)
c 3 (b, c) 3 (c, z)
d 1 (e, d) 2 (d, z)
1 (b, d)
a 0 4 (a, b)
2 (a, e)
сумма 9 15
Заметим, что ребра
(a, b), (b, c)
и
(b, d)
присутствуют в колонке для вхо-
дящего и выходящего потока, потому что обе вершины каждого ребра принад-
лежат
S
. При вычитании эти ребра сокращаются, поэтому, удалив их из обеих
частей, получаем
Таблица 2.3
вершина входящий поток ребро выходящий поток ребро
b
c 3 (c, z)
d 1 (e, d) 2 (d, z)

Страницы