一种有向图中道路的识别方法

为改进已有的道路识别方法 ,通过对有向图邻接矩阵的研究 ,提出了一个较为简便的方法。为确定结点 i和 j之间有无道路 ,新方法不需要对有 n个结点的有向图的邻接矩阵 A做 n次乘方 ,而是定义一个对应于节点 i和 j的行向量 V,只需作行向量 V和邻接矩阵 A的 n次乘法。乘法计算量仅为传统方法的 1/ n,当 n比较大时 ,能大幅度节约计算时间

Recognition method of directed paths in a digraph

Finding directed paths between any two vertices in a digraph is one of typical problems in Graph Theory and has a great application significance. To improve previous recognition methods of paths, this paper presents a more convenient approach through studying an adjacent matrix of the digraph. To determine whether there is any path between vertices i and j , the new approach is developed to define the row vector V, corresponding to vertices i and j , and multiply the row vector V by n times of the adjacent matrix A, instead of raising the adjacent matrix of the digraph with n vertices to the power n . The advantage of the approach is obvious in a sense of saving time and energy, the amount of calculation would be only 1/n of that the traditional methods. This approach is to save time to a large extent when n is enough greater.