Z-H算法正确性证明改写

关键词：算法，HC问题，NP完全问题 中图分类号：T022 文献标识码：A Rewriting the Proof to Theorem 2 of Z-H Algorithm JIANG Xin-wen (School of Computer, National University of Defence Technology, Changsha 410073, China) Abstract: It is given a new proof to theorem 2 of [1] in this paper. The only difference between the new proof and the previous one is that we divide the case 2 into case 2 and case 3 more precisely. Key words: Algorithm; HC problem; NP complete problem 1 引言 [1]中定义了加标多级图、路径集、可达路径集、简单路径、半简单路径等概念，并在此基础上给出了一个关于加标多级图中简单路径存在性的判定算法。算法如下： Z-H判定算法 (1)对E中所有边e，产生e的可达路径集R(e) (2)For l：1 to L 对于l级的任一顶点v 2．1计算Comp(S - v，1) 2．2修改可达路径集：对任意的边e，若e不属于Comp(S - v，1)，去掉R(e)中与v关联的边 2．3整理可达路径集：对任意的可达路径集R(a，b，k)以及任意的边e属于R(a，b，k)，如果R(a，b，k)中没有点b到点D的经过e的路径，去掉 R(a，b，k)中的e (3)如果Comp(S - D，L)中包含S到D的路径，则断言G中存在半简单路径，否则断言G中不存在半简单路径。 上面算法中间的Comp(S - v，1)是反复执行以下操作的结果： (1)设e是(S - v，1)中的一条边，若．R(e)中不含点v到D的路径，从(S—v，1)中去掉e。 (2)设e是(S - v，1)中的一条边，R(e)中包含点v到D的路径v-．．． -u-．．．- D，但(S - u， k)中不含S到v且经过e的路径，去掉R(e)中与u关联的所有边。 (3)设e是(S - v，1)中的一条边，(S - v，1)不存在S到v的同时经过边e的路径，从(S - v，1)中去掉e。 (4)反复执行上面三个步骤，直到(S - v，1)不再变化。 定理2的结论是，设G是一个多级图。如果算法执行的结果，Comp(S - D，L)中包含S到D的路径，则G中一定存在半简单路径。 定理2的证明比较长，基本思想是，根据G构 定理2证明中采用的构造方法是，自底向上寻找多入度点进行撕裂。于是自然产生的情况分类是，存在多入度点和不存在多入度点两种情况。然而由于图的结构的复杂性，在存在多人度点的情况下(即情形2)，进一步将该多人度点分成S到该点的路径有交点和没有交点2种情况(即情形3和情形2)将更加精确。 2 定理2的新证明 定理2设G是一个多级图。如果算法执行的结果，Comp(S - D，L)中包含S到D的路径，则G中一定存在半简单路径。 证明自L - 1级(含L - 1级)往下寻找G中出现的多入度点。 于是我们可以推断： b到c的边。各顶点的路径集仅仅增加新引入的a到b的边。这将保证新增加路径决不会在半简单路径上。对于路径a - b～… - t - D上的新增加顶点b…．，t，其路径集初值为顶点a的路径集初值与路径a - b - … - t - D的并集。这将保证一条边e=(k<1)可以在通过a以后，绕过v经过b到达l+1级的顶点c，因为如果Comp(S - a，1 - 1)非空，则有C0mp(S - b，1)=C0mp(S - a，1 - 1)U{}非空。 于是我们可以推断： 对情形3的图的撕裂，减小了点v所在级的多入度点，1+1级增加了情形3下的多入度点，同时1 - 1级增加了情形2下的多入度点。反复撕裂，可以逐步消灭1+1级、1+2级…．、L - 1级的情形3下的多入度点(这个过程中会产生许多情形2下的多入度点)。对情形2的图的撕裂，减小了点、，所在级的多入度点，1+1级增加了情形2下的多人度点。反复撕裂，可以逐步消灭1+1级、1+2级、…、L - 1级的情形2下的多入度点。所以，反复对情形2和情形3的G进行撕裂，将得到如情形 3 讨论 定理2的证明还可以有许多变种。甚至多级图的定义、可达路径集的定义都可以不出现。但是，我们认为，相关的思想必须体现，对图进行撕裂以便构造一个序列的思路必须体现。进一步的工作将分析算法复杂性。 致谢关于对图进行撕裂并最终得到“简单的图”的直观构想是姜子恒提出的。这使得定理2的证明得以完成。就我的认识而言，这个直观构想是至关重要的。 参考文献 [1] 姜新文．多级图方法求解哈密顿图判定问题改进[J]．计算技术与自动化．2004．3(增刊)．100～107