生成有向图全部有向回路的一个有效的回路向量空间算法
AN EFFICIENT CIRCUIT VECTOR SPACE ALGORITHM FOR GENERATING ALL DIRECTED CIRCUITS OF A DIGRAPH
-
摘要: 本文提出一种生成有向图全部有向回路的、有效的回路向量空间算法,其中每个有向回路都由一个连支定义的基本回路(有向回路或半回路)和一组已获得的有向回路的环和产生,同时可将每个有向回路用一个选定的有向回路基集的线性组合表示。
-
关键词:
Abstract: In this paper, an efficient circuit vector space algorithm is presented for enumerating directed circuits of a directed graph, by which every directed circuit is generated by the ring-sum of a fundamental circuit (directed circuit or semi-circuit) defined by a chord of the-cotree and a subset of the previously obtained directed circuits. At the same time every directed circuit in the digraph can be represented by a linear combination of a selected basic set of directed circuits. -
P. Mateti and N. Deo, SIAM J. Comput. 5(1976)1, 90.[2]J. T. Welch, J. ACM, 13(1966), 205.[3]H. T. Hsu and P. A. Honkanen, A fast minimal storage Algorithm for Determing all the Elementary Cycles of a Graph, Computer Sci. Dept., Pennsylvania State Univ., University Park, 1972.[4]N.E. Gibbs, J. ACM, 16(1969), 564.[5]P. Mateti and N. Deo, On Algorithm for Enumerating all Circuits of a Graph, UIUCDCD-R-73585 (revised), Dept. of Computer Sci., University of Illinois, Urbana, 1973.[6]Maciej M. Syslo, SIAM J. Comput., 10(1981)4, 797.[7]D. Y. Xiong(熊德琰), Some Properties about Digraph and a Search Algorithm for Finding Simultaneously all Directed Circuits and the Basic Sets, Proceeding of China 1985 International Conference on Circuits and Systems, Ed. by IEAS, pp. 132-135.[8]熊德琰, 电子学报,1986年,第6期,第42页.[9]熊德琰, 关于生成有向图的全部有向回路的回路向量空间法, 中国电机工程学会第一届理论电工学术讨论会,1985年3月. -
计量
- 文章访问数: 2124
- HTML全文浏览量: 170
- PDF下载量: 722
- 被引次数: 0
下载:
