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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

109
1 2 3 4 5
0
0 0 0 π
13
π
34
π
45
1
0 0 0 π
21
π
13
π
34
0
2
)3(
1
′
A
=
π
34
π
45
π
51
π
34
π
41
π
12
0 0 0
3
0 π
41
π
13
π
32 +
π
45
π
51
π
12
π
45
π
51
π
13
0 0
4
0 π
51
π
13
π
32 +
π
54
π
41
π
12
π
54
π
41
π
13
π
51
π
13
π
34
0
5
1 2 3 4 5
0
0 0
0
0
1
)4(
1
′
A
=
0 0 0 0 π
21
π
13
π
34
π
45
2
0 π
34
π
45
π
51
π
12
0 0 0
3
0 π
45
π
51
π
13
π
32
0 0 0
4
0 π
54
π
41
π
13
π
32
0 0 0
5
Если существует путь, который ведёт из состояния σ
i
в состояние σ
j
автомата М с n состояниями, то кратчайший такой путь представляется
некоторым элементом (i, j) одной из матриц
)(k
M
′
при 1 ≤ k ≤ n − 1 и мо-
жет быть найден с помощью следующего алгоритма.
Алгоритм P.
1) k ← 1.
2) Найти
)(k
M
′
.
3) Если элемент (i, j) матрицы
)(k
M
′
равен нулю и k < n − 1, то
k ← k + 1 и вернуться к шагу 2.
4) Если элемент (i, j) этой матрицы равен нулю и k = n − 1, то путь
из σ
i
в σ
j
не существует; иначе элемент (i, j) представляет кратчайший
путь из состояния σ
i
в состояние σ
j
. ■
Например, кратчайшим путём из состояния 1 в состояние 5 является
путь π
13
π
34
π
45
, поскольку элемент (1, 5) в матрицах
′
1
A
и
)2(
1
′
A
равен ну-
лю, но в матрице
)3(
1
′
A
− этому пути.
В автомате с n состояниями полным (гамильтоновым) контуром на-
зывается элементарный контур длины n. Главная диагональ матрицы
′
M
)1( −
′
n
M
содержит все полные контуры автомата М.
Так, все элементы главной диагонали матрицы
′
1
A
)4(
1
′
A
равны ну-
лю, следовательно автомат А1 не содержит полных контуров. Напротив,
автомат А4 с тремя состояниями и матрицей

Страницы