算法分析与设计2007第6讲.docVIP

上次内容： (1)Karp证的6个NPC问题，已经证明了前3个。3sat,3dm,VC，需要看书。 (2)稍微解释： NP类：只限于decision问题，有的decision问题也不是多项式时间可验证的。 NPC类：NP类的一部分，只要由一个能找到多项式时间算法，则所有NP类中的问题都能找到多项式时间算法。 任何一个NP问题都能多项式时间求解，几乎不可能，所以NPC问题多项式时间求解也几乎不可能。 定理4.4：HC(NPC。 HC的描述： 实例：图G=(V,E) 询问：G中是否含有一个hamilton圈？ 解释什么是hamilton圈：走遍所有点，点不重复的圈。游戏。 例子：下面的实例，是顶点覆盖的实例， k=2, 是否存在两个点的顶点集合，覆盖所有边。 证明： 先讲一个图，称为检测覆盖子图， 14条边，12个点，检测怎样走遍所有点但不重复。两种方法。 a(a’ b(b’ 一遍走完所有点，怎么走？从点a开始，a’结束；或b开始b’结束。 两遍走完所有点，怎么走？分别从点a, b开始。 梯子怎样走完，只能一次走完或两次走完。一次走完则走完两边，两次走完则一次走完一边。 ,K=2 *每条边对应一个检测子图，形成|V|条通路。 *ai与每条通路的头和尾相连接。 证明(()：若G有顶点覆盖V’(V，|V|=k，在该例中，{a,c}是顶点覆盖。 则，hamilton圈为：a1-a*b-…a*-…-a*d-a2-*c-…c*b-…-c*d-…a1。 先走完a覆盖的边，再通过a2走完b覆盖的边，回到a1，不重复点，走遍所有点，所以是hamilton圈。 将梯子图分成两类：对应两点都在顶点覆盖集合中，只有一点在顶点覆盖集合中。第一类两次走完梯子图，第二类一次走完梯子图。 证明(()：hamilton圈的形式一定是： *a1只能到达梯子图的上顶点或下定点。 *从梯子图a-b开始，一定走完点a覆盖的所有边对应的梯子图才能回到a2。 *一个梯子图只能一次走两边，或一次走一边。只有着两种走法。没有别的走法。 *a1与a2之间的顶点一定是梯子图上的点，梯子图上，原来图一个顶点覆盖的所有边所对应的顶点。 比如对应边(a,x)， 同样a2与a1之间的顶点一定是原来图一个顶点覆盖的所有边所对应的顶点，比如(c,y) *只能与顶点覆盖对应。 如果是k呢，怎么构造图。 其中…的部分一定是被一个点覆盖的边对应的通路，经历了k段…，所以，原图可被k个点覆盖所有边。 *说明为什么是多项式变换： G=(V,E)是顶点覆盖的实例，G’=(V’,E’)是构造出来的对应hamilton回路的实例 一条G中的边在G’中对应12个点，14条边 G’中共有点的个数为：|V’|=12|E|+k G’中共有边的个数为：|E’|=14|E|+2|E|-|V|+2k|V| 所以是多项式变换。 要说明的是：上述证明说明，仅仅对梯子图找hamilton回路就是很难解的。在这种类型的实例上找一条hamilton回路不简单于顶点覆盖，因为顶点覆盖是NP-complete，所以hamilton回路是NP-complete。 定理4.5：PAR(NPC 证明：显然PAR(NP 3dm(par 回忆：3dm的实例：w={w1,w2,…,wq}, x={x1, x2,…, xq}, y={y1,y2,…,yq} M(W*X*Y 询问：是否存在M’(M，使M’是完美对集。 PAR表达为： 实例：集合A={a1,a2,…,an}，S(ai)(Z+， 询问：是否存在A的子集A’，使 证明开始规约： 3dm的例子： W={w1,w2,w3},X={x1,x2,x3},Y={y1,y2,y3} M={(w1,x2,y3),(w2,x2,y1),(w2,x1,y1),(w3,x3,y2),(w3,x3,y3)} 1,3,4组成完美对集。 (1)构造对应par实例如下： A={a1,a2,a3,a4,a5,b1,b2}，|M|+2个元素。 其中每个元素的重量定义如下： p==3，每个元素重量均为3pq=27长度的正整数。P的大小是有 S(a1)---(w1,x2,y3) W1 W2 W3 X1 X2 X3 Y1 Y2 Y3 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 S(a2)---(w2,x2,y1) W1 W2 W3 X1 X2 X3 Y1 Y2 Y3 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 S(a3)---(w2,x1,y1) W1 W2 W3 X1 X2 X3 Y1 Y2 Y3 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0