摘要
图的可达性矩阵在判断图的强连通性以及求强连通分图中具有重要作用.根据传统求解图的可达性矩阵的特点,在定义链长的基础上,寻求了一种新的计算方法,采用逐次求平方的方法进一步降低计算量.
The reachability matrix of directed graph plays a very important role on identifying whether a directed graph to be strongly connected or not and calculating the strongly connected sub graph. Basing on the traditional method to compute the reachability matrix of directed graph and the definition of chain length, a new method is indicated. The algorithm of successive square is employed, which can greatly decrease the calculation complexity.
出处
《数学的实践与认识》
CSCD
北大核心
2009年第12期223-225,共3页
Mathematics in Practice and Theory
基金
北京市属高等学校人才强教计划资助项目(PHR200906210)
关键词
有向图
可达性矩阵
链
逐次平方法
directed graph
reachability matrix
chain
the algorithm of successive square
