算法分析与设计2007第8讲(同名22020)

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

1、第八讲上次内容：(1)限制技术，局部替换技术，分支技术证明NPC。(2)划分三角形，多任务排工，区间排工，最小迟序排工，是NPC。(3)NPC问题子问题是NPC吗？是多项式时间可解的吗，具体问题看。(4)Sat,3Sat,3DM,par,vc,VI,CL,HC,X3C,MC,PIT,Scedule1,Schedule2,Schedule3,§2SAT问题属于P类正面结果促进较大，反面结果否定。矛盾的两个方面，寻找规律。实例：U={u1,u2,…,un}，C={C1,…,Cm}，CiÍUÈ{,…,}，

2、Ci

3、=2。

4、询问：是否存在U的真值指派使C满足。C1Ù…ÙCm=1。要考虑怎样解：通过例子U={u1,u2,u3,u4,u5,u6}C={(u1,)，(u2,u5)，(,u5)，(,u4)，(,u6)，(,)}根据上述实例构造有向图：规则，(x,y)®u1u2u3u4u5u6112第八讲存在一条从u1到的通路，u1赋值1肯定不行。引理：在2SAT项图中，若存在uj®的通路，则uj≠1。即uj=0才可能使所有项满足。就是只能赋值0。证明：uj®w1®w2®…®wk®，则有如下项：(,w1)，(,w2)，…，(,)。若uj=1，

5、则必有一个项不能满足。说明一下。引理：若在2sat项图中，存在路径®uj，则uj¹0，必须uj¬1才可能使所有项满足。证明：设路径为：®z1®z2®…®zl-1®zl®uj，则该路径对应如下项：(uj,z1),(,z2),(,z3),…,(,zl),(,uj)，矛盾。定理：若存在uj，在2sat项图中，存在通路：®uj，uj®，则不存在真值指派，使所有项均满足。定理：若对任意：uj，j=1,…,n，通路P(®uj)和P(uj®)不同时存在，则一定存在U的真值指派使所有项满足。证明：只要设计出算法就可以了，就是当下述

6、条件成立时：通路P(®uj)和P(uj®)不同时存在时，设计出给每个uj赋值的算法。(1)找通路，先赋值，对于uj,j=1,…,n112第八讲若uj®,则uj=0；若®uj，则uj=1。(2)扩展赋值，两种情况。ui=1,xÎ{uj,}。存在边ui®x，则x=1。x=uj，则uj¬1；x=，则uj¬0。ui=0，xÎ{uj,}。存在边x®ui，则x=0。x=uj，则uj¬0；x=，则uj¬1。证明不会出现矛盾：112第八讲(3)剩余变量赋值，怎么赋值？其余赋予相同的值(0或1)。实际上根本用不着第2步。112第八讲

7、请证明正确性。自己完成。§5.2一类NPC问题在三角化图上的解三角化图的了解。(1)几个概念，讲这个内容告诉大家很多知识，常识也很有用。G=(V,E)w(G):团数，G的最大完全子图定点个数，c(G):色数，G中定点着色所需最小色数，图三着色是NPC，图k着色是NPC，平面图：(1)图三着色是NPC。以后证明。(2)4112第八讲着色未知，已经用计算机证明出来了，大概现在研究这个问题的人很少。(3)5着色是多项式时间可解的，容易证明。平面图。a(G)：G的独立数，G的最大独立集的顶点个数，k(G)：G的团覆盖数，覆

8、盖G的所有顶点所需要的完全子图最小个数。团覆盖问题。团覆盖也有很多应用，在很多方面。结论：w(G)£c(G)//w(G):团数，G的最大完全子图定点个数，//c(G):色数，G中定点着色所需最小色数，a(G)£k(G)(2)什么是三角化图：任意四边形以上的多边形中都有一条弦。首先举个例子：说明什么是完美顶点删除方案。我所见过的应用，完美进化树，当时不知怎么回事。单纯顶点：与v临接的点在图中是完全子图，任意u1,u2ÎAdj(v)，(u1,u2)ÎE，则v是单纯顶点。完美顶点删除方案：存在一个顶点序列v1,v2,…,

9、vn，使vk在G(vk+1,…,vn)中是单纯顶点，则顶点序列称为完美顶点删除方案。112第八讲k=1,2,…,n-1，G(vk+1,…,vn)称为由vk+1,…,vn导出的子图。三角化图的定义：若图G存在完美顶点删除方案，则G是三角化图。以下就用这个判断。举例子：1，5，2，3，4，6，7，8，9结论：(1)可以多项式时间判断三角化图。(2)在三角化图上，团问题，着色问题，独立集问题，团划分问题都可多项式时间解决。5.2.2用字典续广度优先搜索判断三角化图Tarjan的算法,最有名的工作是判断平面图,例子说明：判

10、断三角化图很显然是多项式时间可解的。112第八讲adj(a)={b,e}adj(b)={a,c,d,e}adj(c)={b,d}adj(d)={b,c,e}adj(e)={a,b,d}开始任意选择顶点aivabcde0LabelfffffNumber-----1Labelf{5}ff{5}Number5----2Labelf{5}{4}{4}{5,4}Num