您的位置:首页  > 论文页面

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

发表时间:2008-03-15  浏览量:1860  下载量:756
全部作者: 宁安琪,宁宣熙,商红岩
作者单位: 南京航空航天大学经济与管理学院
摘 要: 在本文中定义了一般四正则连环图,并讨论了它的哈密顿图性质。研究表明,并非在全部四正则连环图中都存在哈密顿圈。研究了几种存在哈密顿圈的四正则连环图,并给出了一种构造其哈密顿圈的多项式算法。在文中的最后,讨论了一种三角形四正则连环图,编制了它的生成器,并用在一般图中构造哈密顿轨的SOA算法对36个三角形四正则连环图(n=6-399 6,m=12-799 2)进行了实证研究,验证了SOA算法的有效性。
关 键 词: 图论;哈密顿圈;多项式算法;堵塞流理论
Title: A polynomial algorithm for constructing a Hamiltonian circuit in a special 4-regular graph of connected cycles
Author: NING Anqi, NING Xuanxi, SHANG Hongyan
Organization: College of Economic and Management, Nanjing University
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-399 6, m=12-799 2) and construct their Hamilton circuits by the use of SOA, an algorithm we designed for determining Hamilton path and circuits.
Key words: graph theory; Hamiltonian circuit; polynomial algorithm; blocking flow theory
发表期数: 2008年7月第5期
引用格式: 宁安琪,宁宣熙,商红岩. 四正则连环图的哈密顿图性质研究及其判定的多项式算法[J]. 中国科技论文在线精品论文,2008,1(5):538-544.
 
1 评论数 0
暂无评论
友情链接