关于生成有向图的全部有向回路的回路向量空间法
ON CIRCUIT VECTOR SPACE APPROACH FOR GENERATING ALL DIRECTED CIRCUITS OF A DIGRAPH
-
摘要: 本文提出一个由有向图的(1)有向回路基集或(2)定向回路基集,通过线性组合,生成全部有向回路的算法。文中证明了一条点数边数相等原则。根据此原则,得到一个识别有向回路的简单方法,从而使算法的计算时间与对应的无向图算法基本相同。
-
关键词:
- 有向图; 有向回路; 回路向量空间法
Abstract: 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. -
N. Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall Inc, Englewood Cliffs, N. J. 1974, pp287-290.[2]熊德琰,电子学报,1986年,第6期,第42-47页.[3]Y. M. Wu.[J].K. T. Chiu, S. P. Chan, On Transformations among Network Matrices, Proc.16th Asilomar Conf. on Circiuts, Systems and Computers.1982,:-[4]陈树柏,左垲,张良震等编,网络图论及其应用,科学出版社,北京,1982,第117-121页.[5]P. Mateti, N. Deo, SIAM J.Comput., 5(1976)1, 90-99. -
计量
- 文章访问数: 2060
- HTML全文浏览量: 133
- PDF下载量: 605
- 被引次数: 0
下载:
