關(guān)于產(chǎn)生哈密頓圈的定理及其應(yīng)用
ON THE THEOREM OF GENERATING HAMILTONIAN CYCLES AND ITS APPLICATIONS
-
摘要: 作者曾提出利用王氏代數(shù)產(chǎn)生圖的全部哈密頓圈,本文繼續(xù)研究了這種算法。為了簡化計算,給出一個關(guān)于王積度數(shù)約束的定理,為了避免算法中的不必要的重復(fù),提出一種改進的方法。 最后討論了本算法在布線設(shè)計中的應(yīng)用等。
-
關(guān)鍵詞:
Abstract: In this paper the study of the algorithm which has been done by the author for generating all the Hamiltonian cycles in a graph by a method of Wang algebra is continued. For simplifing the algorithm, a theorem of the constraint of degrees in the Wang s product is presented and for avoiding unnecessary repetitions in the algorithm some modified procedures are given.Finally, the application of the algorithm in layout design is discussed. -
陸生勛,電子學(xué)報,1980年,第1期,第29頁.[2]陸生勛,杭州大學(xué)學(xué)報,1980年,第1期,第63頁.[3]金綏更,電子學(xué)報,1981年,第6期,第33頁.[4]W. K. Chen, Applied Graph Theory, North-Holland, Amsterdam,1976.[5]I. Berger and A. Nathan, IEEE Trans. on CT, CT-15 (1968), 221.[6]齋藤正男,村木克己,電子通信學(xué)會論文誌(C),51-C (1968), 384.[7]陸生勛,張禮和,電子學(xué)通訊,4(1982), 198. -
計量
- 文章訪問數(shù): 2422
- HTML全文瀏覽量: 158
- PDF下載量: 386
- 被引次數(shù): 0
下載:
