算法分析与设计2007第6讲

《算法分析与设计2007第6讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六讲上次内容：(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圈：走遍所有点，点不重复的圈。游戏。例子：下面的实例，是顶点覆盖的实

2、例，k=2,是否存在两个点的顶点集合，覆盖所有边。证明：(1)先讲一个图，称为检测覆盖子图，第9页第六讲14条边，12个点，检测怎样走遍所有点但不重复。两种方法。a®a’b®b’一遍走完所有点，怎么走？从点a开始，a’结束；或b开始b’结束。两遍走完所有点，怎么走？分别从点a,b开始。梯子怎样走完，只能一次走完或两次走完。一次走完则走完两边，两次走完则一次走完一边。,K=2第9页第六讲*每条边对应一个检测子图，形成

3、V

4、条通路。*ai与每条通路的头和尾相连接。证明(®)：若G有顶点覆盖V’ÍV，

5、V

6、=k，在该例中，{a,c}是顶点覆盖。则，hamilton圈为：a1-a*b-…a*-

7、…-a*d-a2-*c-…c*b-…-c*d-…a1。先走完a覆盖的边，再通过a2走完b覆盖的边，回到a1，不重复点，走遍所有点，所以是hamilton圈。将梯子图分成两类：对应两点都在顶点覆盖集合中，只有一点在顶点覆盖集合中。第一类两次走完梯子图，第二类一次走完梯子图。证明(¬)：hamilton圈的形式一定是：*a1只能到达梯子图的上顶点或下定点。*从梯子图a-b开始，一定走完点a覆盖的所有边对应的梯子图才能回到a2。*一个梯子图只能一次走两边，或一次走一边。只有着两种走法。没有别的走法。*a1与a2之间的顶点一定是梯子图上的点，梯子图上，原来图一个顶点覆盖的所有边所对应的顶点。比

8、如对应边(a,x)，第9页第六讲同样a2与a1之间的顶点一定是原来图一个顶点覆盖的所有边所对应的顶点，比如(c,y)*只能与顶点覆盖对应。如果是k呢，怎么构造图。其中…的部分一定是被一个点覆盖的边对应的通路，经历了k段…，所以，原图可被k个点覆盖所有边。*说明为什么是多项式变换：G=(V,E)是顶点覆盖的实例，G’=(V’,E’)是构造出来的对应hamilton回路的实例一条G中的边在G’中对应12个点，14条边G’中共有点的个数为：

9、V’

10、=12

11、E

12、+kG’中共有边的个数为：

13、E’

14、=14

15、E

16、+2

17、E

18、-

19、V

20、+2k

21、V

22、所以是多项式变换。要说明的是：上述证明说明，仅仅对梯子图找

23、hamilton回路就是很难解的。在这种类型的实例上找一条hamilton回路不简单于顶点覆盖，因为顶点覆盖是NP-complete，所以hamilton回路是NP-complete。定理4.5：PARÎNPC证明：显然PARÎNP3dmµ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+，第9页第六讲询问：是否存在A的子集A’，使证明开始规约：3dm的例子：W={w1,w2,w3},X={x1,x

24、2,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}，

25、M

26、+2个元素。其中每个元素的重量定义如下：p==3，每个元素重量均为3pq=27长度的正整数。P的大小是有S(a1)---(w1,x2,y3)W1W2W3X1X2X3Y1Y2Y3001000000000001000000000001S(a2)---(w2,x2,y1)W1W2W3X1X2X3Y1Y2Y30000010000000

27、01000001000000S(a3)---(w2,x1,y1)W1W2W3X1X2X3Y1Y2Y3000001000001000000001000000S(a4)---(w3,x3,y2)W1W2W3X1X2X3Y1Y2Y3000000001000000001000001000S(a5)---(w3,x3,y3)第9页第六讲W1W2W3X1X2X3Y1Y2Y3000000001000000001000000001若M’为完美对集，则在M’中的