Дискретная математика: графы и автоматы. Альпин Ю.А - 40 стр.

40                                      Глава 2. Ориентированные графы


     Предложение 4. Если матрица A порядка n примитивна, то
                          k0 ≤ s(n − 2) + n,
где s — длина самого короткого контура в графе матрицы A.
     Д о к а з а т е л ь с т в о. Для любой вершины i в графе матрицы
A существует путь длины n − s из i в некоторую вершину j кратчай-
шего контура. Теперь рассмотрим примитивную матрицу As . В графе
этой матрицы вокруг вершины j есть петля. Используя при необхо-
димости эту петлю, построим путь длины n − 1 из j в произвольно
выбранную вершину l. В графе A ему соответствует (j, l)-путь длины
s(n − 1). Соединяя упомянутые пути в графе матрицы A, получаем
(i, l)-путь длины (n − s) + s(n − 1) =s(n − 2) + n для произвольно
взятых вершин i, l. ¤
                                                        2
     Итак, если булева матрица A примитивна, то An −2n+2 = I. Вы-
ведите самостоятельно два следствия из предложения 4.
     Следствие 1. Для любой примитивной матрицы порядка n
                          k0 ≤ n2 − 2n + 2.

   Следствие 2. Если на диагонали примитивной матрицы по-
рядка n есть единица, то
                             k0 ≤ 2n − 2.


                        § 6. Цепи Маркова

    Представим себе случайную динамическую систему, состояния ко-
торой изменяются по следующему закону: если в некоторый момент
времени система находится в состоянии u, то в следующий момент
она переходит в состояние v с вероятностью, которая зависит лишь
от u и v и не зависит от предыдущих состояний.
    Переходя на более точный язык, назовём марковской системой
пару (S, p), где S — конечное непустое множество, а p — такая
функция
P         на множестве S × S с неотрицательными значениями, что
  v∈S p(u, v) = 1 для всех u ∈ S. Число p(u, v) понимается как ве-
роятность перехода системы из состояния u в состояние v за один
шаг. Графом марковской системы назовём орграф с множеством S
вершин, в котором дуга u → v существует, если p(u, v) > 0.
    Если считать, как обычно делают, что S = {1, 2, . . . , n}, то мар-
ковские системы вполне описываются стохастическими матрицами