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

UptoLike

ВУЗ: 

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

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

Рубрика: 

83
продолжаем до тех пор, пока некоторый поток
0
z
ϕ
невозможно боль-
ше увеличить данным методом, т.е. если окажется невозможным по-
метить вершину z, то
0
z
ϕ
будет наибольшим потоком сети.
Первая итерация разметки индексов приведена на рис. 2.51.
Вершина z оказалась помеченной индексом (+4). Убывающая после-
довательность индексов (+4,-3, +2, 0) определяет цепь
µ
=(х
0
,x
2
,x
3
,x
4
,z), поток в которой можно увеличить на 1. Первая ите-
рация приводит к сети, приведенной на рис. 2.52, а. Повторяем сно-
ва разметку вершин индексами, находим цепь
µ
=(х
0
,x
2
,х
1
,x
3
,x
4
,z),
увеличиваем поток на 1.
Повторяем разметку (рис. 2.52, б), при которой остаются непо-
меченными вершины х
4
и z. Ситуации, представленной на рис. 2.52,
б, будет соответствовать наибольший поток, а множество V={x
4
,z} -
разрез с наименьшей пропускной способностью
ϕ
(V)=
ϕ
z
0
=c(x
2
,x
4
)+c(x
3
,x
4
)+c(x
3
,z)=3+1+2=6.
Увеличить наибольший поток можно теперь только повышением
пропускной способности какой-либо из дуг, заходящих в разрез V.
б
Рис. 2.52
1
4
+
+
+
2
3
3
1
0
0
4
1
x
0
x
1
x
4
x
2
x
3
z
1
6
2
1
3
3
1
2
5
1
1
1
-
-
+
+
2
4
3
2
0
0
5
1
x
0
x
1
x
4
x
2
x
3
z
1
6
2
1
3
3
1
2
5
а

Страницы