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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

76
Задачи и упражнения
1. Укажите независимые множества вершин; максимальные незави-
симые множества вершин; наибольшее независимое множество вершин;
число независимости α(G); клики; максимальные клики; наибольшую
клику; кликовое число ω(G); дополнение до полного графа
G
; кликовое
число
)(Gω
; вершинные покрытия; минимальные вершинные покрытия;
наименьшее вершинное покрытие; число вершинного покрытия β(G)
графа G:
15. ЦЕПИ МАРКОВА
Цепью Маркова называется дискретная абстрактная система, кото-
рая состоит из: 1) конечного множества состояний S = {s
1
, s
2
, …, s
n
};
2) матрицы переходов P = [p
ij
]
n×n
, где p
ij
− вероятность того, что в сле-
дующий момент времени система будет находиться в состоянии s
j
при
условии, что в текущий момент времени она находится в состоянии s
i
.
Заметим, что
1
1
=
∑
=
n
j
ji
p
(i = 1, 2, …, n).
Определённую таким образом цепь Маркова называют иногда ста-
ционарной, поскольку вероятности переходов p
ij
не являются функциями
времени.
Цепи Маркова можно поставить в соответствие ориентированный
взвешенный граф, вершины которого обозначают состояния цепи, а дуги −
переходы из состояния s
i
в состояние s
j
(при условии, что p
ij
> 0).
Например, цепи Маркова, состоящей из множества состояний S =
= {s
1
, s
2
, s
3
, s
4
, s
5
, s
6
} и матрицы переходов
1 0 0 0 0 0
1/2 1/6 1/3 0 0 0
P =
0 1/2 1/6 1/3 0 0
,
0 0 1/2 1/6 1/3 0
0 0 0 1/2 1/6 1/3
0 0 0 0 0 1
соответствует граф, представленный на рис. 41.
а)
1
2
3
4
5
6
7
б)
1
2
3
4
5
6
7

Страницы