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

UptoLike

ВУЗ: 

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

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

Рубрика: 

82
все дуги которого не насыщены, и выполняем следующие действия
⎩
⎨
⎧
∉
∈
+
=
.),(
;,1)(
)(
,
µϕ
µ
ϕ
ϕ
ии
ии
и
Таким способом производим постепенное увеличение
ϕ
z
до тех
пор, пока он не станет полным. Для примера на рис. 2.51 имеем три
пути из х
0 в z, и все они имеют насыщенные дуги, т.е. поток в сети
полный. Определим его.
µ
1
={x
0
,x
1
,x
3
,z};
ϕ
(
µ
1
)=1,
→
c{(x
0
,x
1
)}=1;
µ
2
={x
0
,x
2
,x
4
,x
3
,z};
ϕ
(
µ
2
)=1,
→
c{(x
4
,x
3
)}=1;
µ
3
={x
0
,x
2
,x
4
,z};
ϕ
(
µ
3
)=2,
→
c{(x
2
,x
4
)}=3;
ϕ
(
µ
1
)+
ϕ
(
µ
2
)+
ϕ
(
µ
3
)=1+1+2.
2. Нахождение наибольшего потока. Процесс увеличения
ϕ
(z)
состоит в разметке вершин графа индексами, указывающими путь,
на котором возможно увеличение потока. Помечаем х
0 индексом 0.
Если х
i
уже помеченная вершина, то помечаем индексом +i все не-
помеченные вершины, в которые идут ненасыщенные дуги из х
i,
т.е.
вершины y, для которых (x
i
,y)
∈
U и
ϕ
(x
i
,y)
<
c(x
i
,y),и индексом –i все
непомеченные вершины, из которых идут дуги в x
i, т.е. вершины у,
для которых (y,x
i
)
∈
U и
ϕ
(y,x
i
)
>
0.
Если в результате этого процесса окажется помеченной верши-
на z, то между вершинами x
0 и z, найдётся цепь
µ
, все вершины кото-
рой различны и помечены номерами предыдущих вершин. Поток во
всех ребрах цепи увеличиваем на 1 в направлении от x
0 к z, т.е.
⎩
⎨
⎧
∈+
∉
=
,,1)(
;),(
)(
,
µϕ
µ
ϕ
ϕ
ии
ии
и
и при совпадении направления движения с ориентацией дуги;
,если,1)()(
,
µ
ϕ
ϕ
∈−= иии и при несовпадении направления движения
с ориентацией дуги. Поток будет увеличиваться. Далее этот процесс

Страницы