生成有向圖全部有向回路的一個有效的回路向量空間算法
AN EFFICIENT CIRCUIT VECTOR SPACE ALGORITHM FOR GENERATING ALL DIRECTED CIRCUITS OF A DIGRAPH
-
摘要: 本文提出一種生成有向圖全部有向回路的、有效的回路向量空間算法,其中每個有向回路都由一個連支定義的基本回路(有向回路或半回路)和一組已獲得的有向回路的環(huán)和產(chǎn)生,同時可將每個有向回路用一個選定的有向回路基集的線性組合表示。
-
關鍵詞:
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月. -
計量
- 文章訪問數(shù): 2150
- HTML全文瀏覽量: 177
- PDF下載量: 723
- 被引次數(shù): 0
下載:
