Цепь Маркова. Классы состояний

[artemio]

Добрый вечер. Имеется матрица смежности для цепи Маркова. Требуется найти классы существенных состояний цепи (если они есть).
(* Существенное состояние — это такое состояние цепи Маркова, покинув которое, она всегда может в него вернуться *).
Помогите пожалуйста с алгоритмом нахождения существенных состояний. Мне нужно анализировать матрицу переходов за один шаг (т.е. исходную) или же за 2, 3 и т.д шагов (т.е. )?

[MBo]

Насколько я понял насчет существнных состояний:

Можно выделить сильно связанные компоненты графа, и посмотреть, как они связаны между собой.
Компоненты со входящими дугами содержат существенные состояния (f,g на присунке http://en.wikipedia.org/wiki/Strongl...cted_component)
Компоненты с исходящими - несущественные состояния (a,b,e)
Компонент с обоими типами внешних дуг (c d h) в данном случае содержит несущественные состояния. Но всегда ли это так - навскидку не скажу.


P.S. см. понятие матрица достижимости