摘要
本文提出一个由有向图的(1)有向回路基集或(2)定向回路基集,通过线性组合,生成全部有向回路的算法。文中证明了一条“点数边数相等”原则。根据此原则,得到一个识别有向回路的简单方法,从而使算法的计算时间与对应的无向图算法基本相同。
An algorithm is presented for generating all directed circuits of a directed graph by the linear combination in the basic set of (1) the directed or (2) the oriented circiuts. A theorem named 'principle of equality between numbers of edges and vertices' is proved. Based on this pringiple a simple method is worked out. Using it to identify the directed circuits makes the running time of the algorithm for digraphs being mainly the same as for undirected graphs.
关键词
有向图
有向回路
向量空间法
Digraph
Directed circuits
Circuit vector space approach
