Дискретная математика. Громов Ю.Ю - 108 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

108
Из матрицы
2
1
A
видно, в частности, что имеются два пути длиной 2
из состояния 3 в состояние 2, а именно π
31
π
12
и π
32
π
22
, и нет путей длиной 2
из состояния 2 в состояние 4 или 5.
Путь
1
il
π
,
21
ll
π
, ...,
jl
k 1−
π
, ведущий из σ
i
в σ
j
, называется элементар-
ным путём (длиной k), если индексы i, l
1
, l
2
, …, l
k–1
, j различны, и эле-
ментарным контуром (длиной k), если индексы l
1
, l
2
, …, l
k–1
различны, а
индексы i, j равны. В автомате с n состояниями длина элементарного пу-
ти не может быть больше (n – 1), а длина элементарного контура не мо-
жет быть больше n. Путь, который не является элементарным, называется
избыточным.
Обозначим через
)(k
M
′
матрицу, элемент в ячейке (i, j) которой со-
держит только элементарные пути длиной k, ведущие из σ
i
в σ
j
. По задан-
ной матрице
M
получить матрицу
)(l
M
′
для l > 0 позволяет следующий
алгоритм.
Алгоритм L.
1) Получить
′
M
=
)1(
′
M
из матрицы
M
, заменяя нулями все нену-
левые элементы её главной диагонали. Переменной k ← 1.
2) Найти произведение
)1(
′
M
)(k
M
′
и заменить в нём каждый избы-
точный путь на ноль, получив таким образом
)1( +
′
k
M
.
3) Если k + 1 < l, то k ← k + 1 и вернуться к шагу 2; в противном
случае
)1( +
′
k
M
=
)(l
M
′
. ■
Проиллюстрируем применение алгоритма L для построения матриц
′
1
A
,
)2(
1
′
A
,
)3(
1
′
A
,
)4(
1
′
A
:
1 2 3 4 5
0
π
12
π
13
0 0 1
′
1
A
=
π
21
0 0 0 0 2
π
31
π
32
0 π
34
0 3
π
41
0 0 0 π
45
4
π
51
0 0 π
54
0 5
1 2 3 4 5
0
π
13
π
32
0 π
13
π
34
0
1
)2(
1
′
A
=
0 0 π
21
π
13
0 0
2
π
32
π
21
+ π
π
1
π
31
π
12
0 0 π
34
π
45
3
π
45
π
51
π
41
π
12
π
41
π
13
0 0
4
π
54
π
41
π
51
π
12
π
51
π
13
0 0
5

Страницы