四正则连环图的哈密顿图性质研究及其判定的多项式算法.pdfVIP

四正则连环图的哈密顿图性质研究及其判定的多项式算法∗ [1] [2] [2] 宁安琪 宁宣熙 商红岩 （南京航空航天大学经济与管理学院，南京210016） [1]ningangie@163.com ,[2] nhning@ 摘要: 在本文中定义了一般四正则连环图，并讨论了它的哈密顿图性质。研究表明，并非在全部四正则连环图 中都存在哈密顿圈。研究了几种存在哈密顿圈的四正则连环图，并给出了一种构造其哈密顿圈的多项式算法。在 文中的最后，讨论了一种三角形四正则连环图。编制了它的生成器，并用在一般图中构造哈密顿轨的自组织算法 （S-O 算法）对36 个三角形四正则连环图（n=6-3996,m=12-7992）进行了实证研究，验证了S-O 算法的有效性。 关键词：哈密顿圈，图论，多项式算法 中图分类号:TP301 A polynomial algorithm for constructing a Hamiltonian circuit in a special 4-regular graph of connected cycles Angelika Ning, Xuanxi Ning,hongyan Shang College of Economic and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, P. R. China Abstract: In this paper we define a 4-regular graph of cycles, and show that it not necessarily is a Hamilton graph. Next we define a special 4-regular graph of cycles, in which there exist Hamiltonian circuits, and design a graphical algorithm for constructing a Hamilton circuit in a special 4-regular graph of cycles, show that it is correct and that the algorithm only needs linear time. At last we design a triangular 4-regular graph of cycles (n=6-3996, m= 12-7992) and construct their Hamiltonian circuits by the use of SOA, an polynomial algorithm we designed for determining Hamiltonian path and circuits in general graph 。 Keywords: Hamiltonian circuit, Graph theory, Polynomial algorithm 1、四正则连环图的构成 所谓连环图是指（园）环与（园）环彼此相交而构成的图。其中，环与环的交点构成该图的点 集、交点之间的环边构成连环图的边集，（见图1），下文所研究的四正则连环图是指满足下面两 个条件的连环图。 ∗ 自然科学基金资助项目（N和N 1 2 10 1