哈密顿图判定问题的多项式时间算法

1哈密顿图判定问题的多项式时间算法姜新文等**（）Abstract:本文给出一个称为问题的定义及其多项式时间判定算法。已经证明包括哈密顿图判定问题在内的众多完全问题可以多项式归结到问题。问题的多项式时间判定算法就是完全问题的多项式判定算法。本文结果暗示。本文涉及的内容属于简单的图论问题算法设计的入门性范畴，被计算机、数学和信息安全等类专业本科以上知识背景覆盖。相关专业本科甚至专科以上学生通过适当求教算法设计、计算复杂性、图论、运筹学和密码算法相关教师和权威可以阅读本文。Keywords:Algorithm,problem,problem,completeproblem1问题引入及若干定义哈密顿图判定问题是完全问题。为了求解该问题，我们需要对问题进行转化。为缩短证明长度，以分段确认，分割围歼，综合众多意见，我们提出问题，并将注意力集中在问题多项式时间判定上。算法是一堆动作的有序集合。为一个问题设计算法是容易的，将一些动作凑在一起即可。设计算法的困难性和严肃性在于，你的算法是否实现了你的计算目标？于是需要证明。而如何证明常常让人无从着手。问题是一个人工构造的问题，它的特别的结构特性，使我们容易找到时间复杂性为关于问题规模的多项式函数算法并证明其正确性。该问题的定义已经可以在很多文章中查到。为了本文的完整性，我们首先转述对问题的定义。定义1称,,,,是加标多级图(labeledmultistagegraph)，如果满足以下条件：1.为顶点集合，∪∪∪⋯∪，∩∅，0,，。如果∈，0，称所在级为级，也称是级的顶点。称为的级。2.为边的集合，中的边均为有向边，它用三元组〈,,〉表示。如果〈,,〉∈，1，则∈，∈。称〈,,〉为的第l级的边。3.和都只包含唯一顶点。称中的唯一顶点为源点，记为，称中的唯一顶点为汇点，记为。4.对每个顶点∈，都有一个边集()作为标记，()⊆ 。称()为的边集。例如，图1所示的两个图，都是加标多级图。各个顶点的边集的一组可能的取值定义如下。对左边的图，(1)，(2)，(3),,,，(4),,，(5),,，(6),,,，(7)，(8),,,，(),,,,。对右边的图,(1)∅，(2)∅，(3)∅，(4),,，(5),,，(6),,，(7)(7),,,，(8),,,，()∅。定义2设,,,,是一个加标多级图，⋯⋯ (1，)是中一**Pleasevisit条路径。如果对任意的，∈1,2,⋯,，⋯∈()，称中的这条路径为简单路径。如果对任意的，∈1,2,⋯,2或者∈1,2,⋯,1，⋯∈()，称中的这条路径为半简单路径。()1显然，根据定义，简单路径必为半简单路径。现在提出一个问题。设,,,,是一个加标多级图。问：中是否存在一条简单路径，即是否存在路径⋯⋯，使得对路径上除外的所有顶点，有⋯∈()?这个问题就是要判定一个多级图中简单路径的存在性。我们称这个问题为问题，即多级图简单路径（Multistage-graphSimplePath）问题。不是所有图都有简单路径。一个图是否存在简单路径，取决于图，同时也取决于各个顶点的边集的取值。例如，对于图1中左图，S1346D是一条简单路径。而右图中没有简单路径。本文讨论中将经常用到边集。由于边的集合当然地可以表示图，所以我们常常不加区分地说一个点属于这个边集，一条边属于这个边集，一条路径属于这个边集，等等。2求解问题的算法2．1四个基本算子定义基本算子1：。设是边集的任意子集，，∈。定义|∈, is on a path ⋯,andalltheedgeson⋯arecontainedin。的目的是整理边集。中可能包含一些零零散散的边。这些边因为不可能在到路径上，因而从中去掉。如果用||表示中边的数目，可以设计(||)的算法计算。定义3如果,,,,中存在一条路径⋯⋯，使得边〈,,〉∈()，()，()，⋯，()，⋯，()，我们称边〈,,〉可由()达到 ()，路径⋯⋯称为〈,,〉由()达到 ()的路径，或者由到达的路径，有时候还简称〈,,〉的可达路径。为了描述〈,,〉的可达路径，我们引进集合(,,)。(,,)是边集的子集，其中包含的是〈,,〉的可达路径经过的边。称(,,)为〈,,〉的可达路径集。一个加标多级图给定之后，可以计算出所有边的可达路径集。基本算子2：((,,))。3((,,))用来计算〈,,〉的(,,)的初值：(1)←〈,,〉|〈,,〉∈,,〈,,〉∈()∩()//Collectingedges(2)(,,)←//Linkingedgestogether如果用||表示中边的数目，可以设计(||)的算法计算((,,))。虽然称作可达路径集，()也是边的集合。本文讨论中的所有涉及路径的集合都是边集，因而，他们的规模是多项式的而不是指数的。如同英文单词很多，但字母表只有26个字符。基本算子3：,,()。设⊆,∈,()()|∈。,,()等于以下迭代结束时_中的结果：(1)_←(2)Forall〈,,〉∈_:Letbeavertexatstage.If and (,,)∩_containsnopathfromto,_←_.If , ,and (,,)containsnopathfromto,_←_.(3)_←_,where,istheuniquevertexof.(4)Repeatstep2andstep3untilS_willnotchangeanymore.解释一下,,()的计算过程。第二步是去掉_中的边，去边〈,,〉的条件是(,,)∩_不含到然后到的路径。第三步是整理边集_。这个去边和整理的过程反复实施，直到_不再变化。由于中包含的边的条数是一个定数，这个计算过程必然终止。显然，对任意()，有(),,()⊆()。可以设计(||)的算法计算步骤2。步骤2和步骤3因而可以在(||)内完成。每次迭代至少减少一条边，_昀多有||条边，所以计算(),,()的时间复杂性为(||)。基本算子4：((,,))。((,,))是用()()|∈中其它的()限制和绑定(,,)。(1)Forall〈,,〉∈(,,),if( | 〈,,〉∈,,()∩(),,() contains a path that contains 〈,,〉 and 〈,,〉, ,())∅then〈,,〉iskeptin(,,)else〈,,〉isdeletedfrom(,,).(2)(,,)←(,,).(3)Repeatstep1andstep2until(,,)willnotchangeanymore解释一下((,,))的计算过程。步骤1中，如果〈,,〉继续留在(,,)中，一定有一条这样的路径⋯，该路径上所有边的()包含〈,,〉和〈,,〉。或者更粗略和更简单地说，〈,,〉能够经过〈,,〉除非有路径 ⋯陪着〈,,〉经过〈,,〉。((,,))的复杂性依赖于算子1,2and3。我们可以在||∗(||)的时间内完成计算( | 〈,,〉∈,,()∩(),,() 包含一条路径，该路径包含〈,,〉 和 〈,,〉, ,())，从而||∗||∗(||)时间内完成步骤1。每次迭代至少减少一条边，因此((,,))的复杂性为||∗||∗||∗(||)(||)。4修改后的(,,)是修改前的(,,)子集。为了方便，我们仍然称其为〈,,〉的可达路径集。2．2算法、复杂性分析、必要性证明现在给出求解问题的、由以下四个语句构成的算法以及关于算法的分析证明。算法的输入是,,,,。算法中符号:表示边的集合中从第级到第级的边，其中1。如果，:∅。ZHAlgorithm1.Forall∈,weuseoperator2togenerate()directly.2.For2to12.1Forall〈,,〉ofstage,call((,,))tomodify(,,)2.2Forallofstage,()←(),,()2.3Forall〈,,〉∈,,executethefollowingtwosteps:(,,)1:←⋃(,,)∩(),,()∈//LimitR(e)(,,)←(,,)//TidyR(e)3.Repeatstep2untilno(,,)in()()|∈willchangeanymore.4.If(),,()∅,weclaimtheexistenceofasimplepathin.Otherwise,weclaimthatthereisnosimplepathin.解释一下算法的动作。‘(,,)1:←⋃(,,)∩(),,()∈’意味着(,,)的从1级到级的边由⋃(,,)∩(),,()∈替换。替换之后，进一步执行‘(,,)←(,,)’以便保持(,,)(,,)。算法的核心思想是用()绑定(,,)(step2.1)，用()修改()(step2.2)，同时用(),,()限制修改()(step2.3)。step3之后，用 ()计算(),,()。结论是，(),,()∅，当且仅当中存在简单路径。定理1.设||表示的顶点个数，||表示中边的条数。算法的时间复杂性是||*|| 的多项式函数。证明首先指出，任意边集，任意可达路径集中包含的边的条数||，因为他们都是边集的子集；顶点边集的个数||；可达路径集的个数||。前面已述，计算,,()的复杂性为(||)。计算((,,))的复杂性为(||)。可以分析出来步骤2.3限制()的复杂性为(||)。对步骤3的每次迭代，(,,)至少减少一条边。算法的第二步是算法中昀为复杂的语句。所以算法的时间复杂性为||∗||∗(||)。由此证明了算法的时间复杂性为||*||的多项式函数。■定理2.如果中存在简单路径，则一定有(),,()∅。证明设⋯是中一条简单路径,,。根据简单路径定义，有⋯∈(),1，并且，对路径⋯上所有〈,,〉，1，有〈,,〉∈()，()，()，⋯，()。所以，算法步骤1执行完毕，(,,)将包含⋯，1。步骤2之后，(,,)仍然包含⋯，1。步骤3不会截断(,,)中的任何路径。我们因此知道(),,()包含⋯。■2.3充分性证明准备5我们现在开始证明，如果(),,()∅，则中存在简单路径。2.3.1两个函数为了下面讨论需要，引进两个函数，一个是换名函数，另一个是撕裂函数,。两个函数都是处理三元组的。一个三元组在多级图中表示一条边。建议在引理2介绍完撕裂，获得一些直观认识后，再细看这里的定义。换名函数.设是一个集合，〈,,〉|,∈， 是一个整数，⊆，∈，并且，∈。递归定义如下：()〈,,〉, 〈,,〉〈,,〉, 〈,,〉, ()()∈ 撕裂函数,.设是一个集合；〈,,〉|,∈， 是一个整数；，，∈，是一个整数；，，是的子集，∅，∅，∩∅，∪|∈,〈,,〉,∈。,定义如下：,(,,)(|∈,〈,,〉 〈,,1〉,∈ ∪ |〈,,〉,〈,,〉∈,∈ ∪|〈,,〉,〈,,〉∈,∈ ∪|〈,,1〉 〈,,1〉,〈,,1〉∈,∈ 在,(,,)中，我们从中去掉所有三元组〈,,〉和〈,,1〉，如果〈,,〉∈，用〈,,〉替换〈,,〉，如果〈,,〉∈，用〈,,〉替换〈,,〉，如果〈,,1〉∈，用〈,,1〉 和〈,,1〉替换〈,,1〉。2.3.2定义证明算法我们还需要两个符号。\4:\4表示算法除步骤4之外的其余步骤。:设是一个多级图。将的2的()都置成()()∪3:，将的1级的()都置成()()∪，由此得到的图称为。为了构造反驳，我们将算法应用两次。一次将算法应用于，得到一个中间结果。然后将算法应用于，并结合刚才得到的中间结果，得到昀终结果。根据昀终结果，我们推断中简单路径的存在性。为了方便提及，我们将算法应用两次的这个过程称作ProvingAlgorithm。证明算法的输入包括图,,,,以任意的一个边集(当然只能是的子集)。为了简化讨论，我们讨论的图需要满足一些性质。对不满足这些性质的图，算法将停机。因为反驳中必须有新的实例构造，而新的构造同样必须具备这些性质，为了讨论中不会遗漏的原因，我们将这些性质全部列在证