传递概率矩阵正则性的判定

传递概率矩阵正则性的判定 ON THE REGULARITY DECIDING PROBLEM OF TRANSITION PROBABILITY MATRIES 杨挺 Yang Ting first-author 传递概率矩阵是分析软件系统可靠性的重要数学方法之一。本文致力于其一个重要子类——正则传递概率矩阵的判定问题及判定算法的讨论,并给出了判定传递概率矩阵正则性的两个充要条件（见定理2,定理3）。在定理3的基础上提出了一个有效的正则性判定算法,分析表明其最坏时间复杂性为O（n 4 ）。 Transition Probability Matrix is an important mathematical tool for analizing software system reliability. This paper discusses one of the important subclasses of transition probability matrix—regular transition probability matrix, its deciding rules and deciding algorithm. The two main results we have obtained are Theorem 3（appeared in the text） and the algorithm JRTPM. Suppose P be an n order transition probability matrix, and GS P （V, E） be the labeled directed graph with adjacence matrix P; let TC（P） be lengthes of all the simple cycles of all nodes v∈V, then we have following theorem 3: Theorem 3: P is a regular transition probability matrix, iff following two conditions hold: （1） GS P （V, E） is strongly connected; （2） suppose all the elements contained in TC（P）are l 1 , …l m respectively, then gcd （l 1 , …, l m ）=1. according to the above theorem, an effective deciding algorithm is presented, mathematical anatizing has shown that under the worst cases, its complexity is O（n 4 ）. 1985-04-01 2021-04-01 4