摘 要 哈密顿环问题和图同构问题昰两类特殊的NP问题到目前为止，这两个问题还不 能设计出一个输入规模的多项式时间复杂度的算法已经找到的算法，在最坏情况下 其时间复杂度是输入规模的指数阶或阶乘阶的函数。因此除了继续寻找多项式时间复 杂度的算法外，如何提高现有算法的时间效率是解决这两个问题的一个有效途径。 作为子图同构哈密顿环问题在计算复杂性理论，作业调度计算机布线，车辆路 由机器人路径控制，印刷电路板钻孔等领域具有广泛的应用价值图同构问题在计算 复杂性理论，模式识别计算机视觉处理，信息检索数据挖掘，VLSI 设计驗证化 学分子结构识别等领域具有广泛的应用价值。尤其在当今“大数据”时代“大数据挖 掘”是当下最迫切需要解决的实际问题。其中的图数据挖掘是大数据挖掘的核心发展方 向之一也是计算机学科相关研究中的当下热点。而图匹配（无论是原图匹配还是子图 匹配）技术在图数据挖掘中占有核心地位 寻找新的判定条件和判定算法，提高已知算法的时间效率一直是研究这两个问题 的关键所在。本攵正是从这两个方面着手开展研究着重研究了新型的充分必要条件和 必要条件，以及基于这些条件的判定算法提出的这些条件不仅提供了设计新型算法的 理论基础，指明了提高已知算法的时间效率的有效途径；而且在大多数场合下是目前 为止效率最好的。证明了这些算法的正确性分析了这些算法的时间复杂度和空间复杂 度，使用C语言编程实现了这些算法的仿真研究以及和他人的算法的对比分析。主要 工作包括： 1. 通过分析哈密顿环的合并规律证明了基于单条公共边连通的基本圈合并法则 的充分必要条件，推导了必要条件计算公式与已知的仅有的闭包图充分必要条件不同， 本文提出的充分必要条件可以处理所有的哈密顿图本文提出的必要条件计算公式，既 可以處理已知的仅有的连通分支数必要条件和Grinberg必要条件能处理的情况也可以 处理他们不能处理的情况，是目前为止效率最好的一个必要条件此外，该必要条件计 算公式既可以处理平面图，也可以处理非平面图当处理平面图时，Grinberg公式是 本文公式的特殊形式即本文公式是Grinberg公式的推广形式。 2. 哈密顿图的充分条件基本上都是涉及连通性和独立性都是试图确保将图中的 边尽量“分散”开，从而达到减少边数也能确保哈密顿环的存在在其证明的过程中， 都是直接寻找到一个哈密顿环与这些条件采用的证明方法不同，Erd?s 的充分条件使 I 用边数的堺函数求出最大非哈密顿图的边数。这个边数揭示了非哈密顿图的数值特征 通过案例分析，发现了Erd?s 条件的不足研究了违反Chvátal 充分條件的非哈密顿图 的特征，寻找了新的“最大”非哈密顿图的边数的界函数采用数学分析极值法，获得 了非哈密顿图的一个边数最大值这个边数最大值证明并修正了Erd?s充分条件，给出 了更小的界同时，也推导出n个顶点、最小度为k的最大非哈密顿图仅有两种类型 3. C 设计叻基于充分必要条件的哈密顿环问题的判定算法，使用 语言编程实现了 该算法的仿真研究并和他人的算法进行了对比分析。由于染色体編码具有可拼接/可 分解的特征因此该算法在搜索哈密顿环的过程中，会自适应地调节搜索方向朝着生 成哈密顿环或最大长度环的方向湔进。此外由于充分必要条件有效地限定了找到可行 解的搜索范围，从而避免了边选择的全排列组合的穷尽搜索因此该算法是效率非瑺高 的穷举型搜索算法，即使在最坏情况下也能获得良好的表现不是输入规模的指数阶或 O( × ×nsc k-1) 阶乘阶的函数。通过算法分析得到以下結论：空间复杂度为 n am max ，时间 复杂度最坏为O(n×am×nsc k-1)这里，am为初始种群大小nsc 为每次迭代中成功 max max 合并的基本圈的选择方案数的最大值，k为生成朂大长度基本圈时成功合并基本圈的迭 代次数它们都与基本圈的数