最大平面图中哈密顿圈的计算机辅助分析
COMPUTER AIDED ANALYSIS OF HAMILTONIAN CYCLES IN MAXIMUM PLANAR GRAPHS
-
摘要: 本文提出了一个递推算法,可用来产生某种类型的最大平面图的全部哈密顿圈。对于Wagner型图,计算结果可用下式表示: M(p)=6+4(p-5),5p20其中,p为该型最大平面图的阶(点数),M(p)是p阶图中哈密顿圈的个数。文中还给出了一个定理,证明了算法的正确性。
-
关键词:
Abstract: A recursive algorithm for generating all hamiltonian cycles in maximum planar graphs of certain type has been proposed. For wagner graphs, the computed results may be represented by the following formula: M(p) =6+4(p-5), 5 p 20 where p is the order of the graph and M (p) is the total number of hamiltonian cycles. A theorem has been given and the correetness of the algorithm has been proved. -
陆生勋,电子学报,8(1980), 29.[2]陆生勋,杭州大学学报,1980年,第1期,第63页.[3]金绥更,用王氏积产生任意图的全部哈密顿圈,电子学报,1981年,第6期,第33页.[4]金绥更,张丽君,割算法在719机上的实现,科技通讯,1981年,第3期,第89页.[6]F. Harary著,李藯萱译,图论,上海科技出版社,1980. -
计量
- 文章访问数: 1856
- HTML全文浏览量: 120
- PDF下载量: 552
- 被引次数: 0
下载:
