關(guān)于生成有向圖的全部有向回路的回路向量空間法
ON CIRCUIT VECTOR SPACE APPROACH FOR GENERATING ALL DIRECTED CIRCUITS OF A DIGRAPH
-
摘要: 本文提出一個(gè)由有向圖的(1)有向回路基集或(2)定向回路基集,通過(guò)線(xiàn)性組合,生成全部有向回路的算法。文中證明了一條點(diǎn)數(shù)邊數(shù)相等原則。根據(jù)此原則,得到一個(gè)識(shí)別有向回路的簡(jiǎn)單方法,從而使算法的計(jì)算時(shí)間與對(duì)應(yīng)的無(wú)向圖算法基本相同。
-
關(guān)鍵詞:
- 有向圖; 有向回路; 回路向量空間法
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]熊德琰,電子學(xué)報(bào),1986年,第6期,第42-47頁(yè).[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]陳樹(shù)柏,左塏,張良震等編,網(wǎng)絡(luò)圖論及其應(yīng)用,科學(xué)出版社,北京,1982,第117-121頁(yè).[5]P. Mateti, N. Deo, SIAM J.Comput., 5(1976)1, 90-99. -
計(jì)量
- 文章訪問(wèn)數(shù): 2080
- HTML全文瀏覽量: 138
- PDF下載量: 608
- 被引次數(shù): 0
下載:
