改进的Hamilton图充分条件与判定算法

"Hamilton图的充分条件 - 谢应泰 - 成都大学信息科学与技术学院" 在图论中，Hamilton图是指包含一个通过每个顶点恰好一次的简单闭合路径（即Hamilton圈）的图。这篇由谢应泰发表的论文主要探讨了Hamilton图的一种新的充分条件，这个条件比已知的一些经典条件更加优越。论文中提到的充分条件优于Fan条件，这意味着所有满足已知充分条件（如Dirac条件、Posa条件、Bondy条件、Chvatal条件和Fan条件）的Hamilton图都是满足谢应泰提出的新条件的子集。 Dirac条件指出，如果一个图G有n个顶点且n >= 3，那么对于图中的任意顶点u，如果d(u) >= (n+1)/2，那么G是Hamilton图。Posa条件则稍微放宽了这个限制，要求存在一个顶点集，使得其内部边数至少是顶点数的一半，这样的图也是Hamilton图。Bondy和Chvatal也提出了相关的充分条件，但它们通常涉及更复杂的图论概念。 谢应泰的论文中提到了一个多项式时间算法，该算法可以用来判断一个给定的图是否满足他提出的新充分条件。如果满足，算法还能找到图中的一个Hamilton圈。这在图论和算法设计中具有重要意义，因为寻找Hamilton圈通常是一个NP完全问题，而能够快速检测充分条件的存在有助于简化这一过程。 论文还涉及了“交替路”和“P-链”等概念，这些是图论中用于分析路径和圈的工具。交替路是指路径上的边交替属于两个不同的集合，而P-链可能是指与特定路径结构相关的连通部分。正规P-链可能是指满足特定规则或性质的P-链，这在证明新条件的优越性中可能发挥了关键作用。 关键词中的“Hamilton圈”指的是图中经过每个顶点恰好一次的闭合路径，“交替路”涉及到路径结构的研究，“P-链”和“正规P-链”是分析图的结构特征，它们在寻找Hamilton圈的过程中可能被用作构造或证明的工具。 这篇论文在图论领域做出了贡献，提供了一个新的、更强的Hamilton图充分条件，并给出了有效的检测和构建Hamilton圈的算法，这对理论研究和实际应用都有积极的影响。