Основы синтеза и диагностирования автоматов. Воронин В.В. - 85 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

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

Рубрика: 

81
из А. Полную совокупность дуг U
A
=U
A
+
∪
U
A
-
называют разрывом
транспортной сети. Для сети на рис. 2.51 имеем U
A
={(x
4
,x
2
),
(z,x
3
)}
∪
{(x
3
,x
4
)}.
Поскольку каждая частица вещества, идущая от х
0 к z, обяза-
тельно пройдёт по какой-либо дуге разреза, то общий поток через
разрез будет равен значению потока транспортной сети т. е.
+−
∈∈
=
==−
∑∑
AAz
CuBu
UCUBuu ;)()(
ϕ
ϕ
ϕ
.
Пропускной величиной разреза называют величину
;)()(
−
∈
==
∑
x
Bu
UBucAC
т.к. имеет место
ϕ
(u)
≤
с(u), то ясно, что
ϕ
(z)
≤
с(A).
Рассмотрим постановку и решение задачи о наибольшем пото-
ке. При заданной конфигурации транспортной сети и известной про-
пускной способности дуг найти наибольшее значение потока, кото-
рый может пропустить транспортная сеть, а также распределение
этого потока по дугам транспортной сети.
Справедливо следующее утверждение. Если для некоторого
значения потока транспортной сети
ϕ
z
и некоторого разреза V имеет
место
ϕ
(z)=C(V), то поток
ϕ
z
является наибольшим, а разрез V - раз-
рез с наименьшей пропускной способностью.
Это утверждение не даёт практического метода нахождения
наибольшего потока. Для изложения такого метода введём несколько
вспомогательных определений. Дугу и называют насыщенной, если
ϕ
(u)=с(u). Поток
ϕ
z
называется полным, если каждый путь из х0 в z
содержит хотя бы одну насыщенную дугу. Нахождение наибольшего
потока для целых с(и) производится в два этапа.
1. Нахождение полного потока. Пусть
ϕ
(u) - некоторое распре-
деление потока по дугам транспортной сети. Ищем путь µ из х
0 в z,

Страницы