关于产生哈密顿圈的定理及其应用
ON THE THEOREM OF GENERATING HAMILTONIAN CYCLES AND ITS APPLICATIONS
-
摘要: 作者曾提出利用王氏代数产生图的全部哈密顿圈,本文继续研究了这种算法。为了简化计算,给出一个关于王积度数约束的定理,为了避免算法中的不必要的重复,提出一种改进的方法。 最后讨论了本算法在布线设计中的应用等。
-
关键词:
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. -
陆生勋,电子学报,1980年,第1期,第29页.[2]陆生勋,杭州大学学报,1980年,第1期,第63页.[3]金绥更,电子学报,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]斋藤正男,村木克己,电子通信学会论文誌(C),51-C (1968), 384.[7]陆生勋,张礼和,电子学通讯,4(1982), 198. -
计量
- 文章访问数: 2317
- HTML全文浏览量: 139
- PDF下载量: 382
- 被引次数: 0
下载:
