您的位置：首页 > 论文页面
四正则连环图的哈密顿图性质研究及其判定的多项式算法
发表时间：2008-03-15 浏览量：2377 下载量：927
| 全部作者： | 宁安琪，宁宣熙，商红岩 |
| 作者单位： | 南京航空航天大学经济与管理学院 |
| 摘 要： | 在本文中定义了一般四正则连环图，并讨论了它的哈密顿图性质。研究表明，并非在全部四正则连环图中都存在哈密顿圈。研究了几种存在哈密顿圈的四正则连环图，并给出了一种构造其哈密顿圈的多项式算法。在文中的最后，讨论了一种三角形四正则连环图，编制了它的生成器，并用在一般图中构造哈密顿轨的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. |
11
评论数 0请您登录
暂无评论
下载全文
多维论文