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

UptoLike

ВУЗ: 

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

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

Рубрика: 

35
Продолжение таблицы 2.3
вершина входящий поток ребро выходящий поток ребро
a 0
2 (a, e)
сумма 1 7
Снова разница входящего и выходящего потока равна 6. Но поскольку
ребра, обе вершины которых принадлежат
S
, удалены, то выходящий поток –
это сумма потоков ребер, которые идут из
S
в
T
, а входящий поток – это сумма
потоков ребер, которые идут из
T
в
S
. Аналогичные рассуждения будут исполь-
зованы в приведенной ниже теореме.
ТЕОРЕМА 2.1. Для любого фиксированного потока ƒ
()
(
)
(
)()
()()
.zпоток ef ef
aout e zin e
∑
∑
∈∈
=
=
=
апоток
СЛЕДСТВИЕ. Пусть
S
– подмножество множества
V
, содержащее
а
, но
не содержащее
z
, и
T = V - S
. Тогда
()
(
)
()()
(
)()
.zпоток апоток ef - ef
T S, e ST, e
=
=
∑
∑
∈∈
●
Величина потока
ƒ
, обозначаемая как
υal(ƒ)
, равна
() ()
.zпоток aпоток =
● Пусть S – подмножество множества
V
и
T = V - S
. Тогда
(
){}
T S, e : e
∈
называется
сечением
. Если
S
a∈
и
T,z
∈
то сечение называется
a – z сечением
.
● Величина
()
(
)
()
∑
∈
=
TS, e
ec TSС ,
называется
пропускной способностью
сечения.
● Поток
f
€
в сети называется
максимальным потоком
, если
(
)
()
fal fal
υυ
≥
€
для любого возможного потока
ƒ
в сети.
●
a
-
z
сечение (
S, T
) называется
минимальным сечением
, если
C
(
S
,
T
) не
больше пропускной способности любого другого
a
–
z
сечения.
ТЕОРЕМА 2.2. Пусть
S
– подмножество множества
V
, содержащее
а
, но
не содержащее
z
, и
T = V – S
. Тогда
(
)
(
)
.T S,C fal
≤

Страницы