一种求布尔矩阵传递闭包的基于自反矩阵构造的平方算法

A Reflexive Matrix Constructing based Square Algorithm for Calculating the Transitive Closure of Boolean Matrix

首先,介绍布尔矩阵传递闭包的概念及计算问题;随后,分析布尔矩阵的传递闭包和由该布尔矩阵与单位矩阵取并所得到的自反矩阵的传递闭包之间的关系;最后,利用上述结果给出一种求解布尔矩阵传递闭包的基于自反矩阵构造的平方算法,并通过实例说明了其具体计算过程.

First, the transitive closure of general boolean matrix and it＇s computing problems are discussed. Then, the relations between the transitive closure of general boolean matrix and that of the reflexive boolean matrix constructed by the union of boolean matrix and identity matrix are studied. At last, the reflexive matrix contracting based square algorithm is presented for calculating the transitive closure of the general binary relation, and the procedure of it is showed through an example.