计算机算法基础 第2版 习题及答案 第14章

PAGE32第14章 NP完全问题判断以下各命题对与错。如果P¹NP，那么就不存在多项式算法来判断一个图是否可以3着色。如果P¹NP，那么就不存在多项式算法来判断一个图是否含有一个6-clique。如果P¹NP，那么就不存在多项式算法来判断一个图是否有一个6-cover。如果问题A有多项式算法在(n3)时间内被判定，而问题B在(n3)时间内可归约为问题A，那么问题B也就可以在(n3)时间内被判定，这里的n指的都是问题的输入规模。如果问题A有算法在(2n)时间内被判定，而问题B在多项式时间内可归约为问题A，那么问题B也就可以在(2n)时间内被判定解：(a)对 (b)错 (c)错 (d)错 (e)错。假设给你一个“宝盒子”P，它可以在常数时间内正确判定一个有n个正整数的集合S是否可以被平分，但它不能给出实际的平分，它只可以被你的程序调用并输出P(S)=1或P(S)=0。请设计一个以P为子程序的多项式算法为一个可平分的集合S作出实际的平分。解：算法思路如下：设S={a1,a2,…,an}。如果集合S可被平分为集合A和S-A，那么我们可以用P来检测a2是否可以与a1分在同一个集合。办法是，我们把a1和a2从S中刪去，换之以一个数c，其值为(a1+a2)，即SS{c}–{a1,a2}。如果改动后的集合S仍然有P(S)=1，则表明新的集合S可以平分，而新集合可以平分则表明原集合可以平分，并且a1和a2可以分在同一个集合。否则，如果有P(S)=0，则表明a1和a2不可以分在同一个集合，我们则恢复原集合。我们用这个办法把所有可以与a1分在同一个集合的整数都找出来，平分完成。下面伪码精确地表达了这个算法。Partition(S)ifP(S)=0 //P作为子程序被调用 thenreturn(Shasnopartition)endifA¬{a1}c¬a1S’¬S{c}–{a1} //c=a1，在S中换一个符号而已fori¬2ton c¬c+ai S’¬S’–{ai} ifP(S’)=1 then A¬AÈ{ai} else c¬c-ai S’¬S’È{ai} endifendforreturnA,S-AEnd这显然是个多项式算法。集合复盖(set-cover)问题是这样定义的：假设F={S1，S2，…，Sn}是含n个集合的一个家族(family)，这些集合的并集一共含有m个不同的元素，即⋃1≤i≤nSi={a1，a2，…，am}。家族中一部分集合的组合C称为一个子家族。如果这m个元素中每个元素都出现在子家族C中的某个集合里，那么C称为是F的一个复盖，因为C复盖了F中所有元素，即⋃Si∈CSi={a1，a2，…，am}。如果C是F的一个复盖并且所含集合数最少，则称为一个最小复盖。比如，F={S1，S2，S3}，这里S1={a,b},S2={b,c},S3={a,c,d}，S1ÈS2ÈS3={a,b,c,d}。因为S1ÈS3={a,b,c,d}，所以C={S1，S3}就是一个F的集合复盖。因为在这个家族F中没有一个集合能包含全部4个元素，所以子家族C={S1，S定义集合复盖问题所对应的一个判断型问题。证明集合复盖问题是NP难问题。解：(a)对应的一个判断性问题可定义如下：假设F={S1，S2，…，Sn}是含n个集合的一个家族(family)，这些集合的并集一共含有m个不同的元素，即⋃1≤i≤nSi={a1，a2，…，am}。对一个给定正整数k，判断F中是否有一个k-复盖，即含k证明集合复盖问题是NP难问题。我们把顶点复盖问题多项式归约到集合复盖问题。假设一个顶点复盖问题的实例是图G(V,E)和整数k。下面解释如何由这个实例来构造一个集合复盖问题的实例。假设图G(V,E)有m条边，E={e1，e2，…，em}，那么，对应G中每一条边ei(1im)，我们构造一个元素ai。然后，对应G中每一个顶点vV，我们构造一个集合Sv，而它所含元素就是与点v关联的边所对应的元素，即Sv={ai|边ei与v关联，1im}。设|V|=n，那么这n个集合一起就组成了一个家族F，F={Sv|vV}。下面看一个例子。假设顶点复盖问题的图如下。 我们为6个顶点构造6个集合如下： Sa={a1,a3,a4}，Sb={a2,a7,a8}，Sc={a3,a5,a7}，Sd={a4,a6,a8}，Se={a5,a6}，Sf={a1,a2}。这些集合组成了集合复盖问题中的家族，F={Sa，Sb，Sc，Sd，Se，Sf}。下面我们证明图G有一个k-复盖当且仅当构造的家族F有一个k-复盖。根据我们的构造，一条边ei(1im)，与一个顶点v相关联当且仅当元素ai属于集合Sv。所以，S={v1,v2,…,vk}是G的一个k-复盖当且仅当C={Sv1,Sv2,…,Svk}是F的一个k假设我们要举行一个学术会议。会议有m个议题，T1，T2，…，Tm。对每一个议题Ti(1im)有一个可以审这方面稿件的教授的名单Pi。一个教授可能为几个不同的议题审稿而出现在几个名单中。现在，我们希望从这些名单中选出一些教授来组成一个审稿委员会。我们希望委员会的人数越少越好，但是保证每一个议题都有能审稿的委员。请回答以下问题。定义与这个优化型问题对应的一个判断型问题。证明这个判断型问题属于NP类。把图的顶点复盖问题多项式归约到这个判断型问题以证明其NP完全性。解：(a) 让我们称对应的判断型问题为审稿委员会问题。定义如下：假设我们要举行一个学术会议。会议有m个议题，T1，T2，…，Tm。对每一个议题Ti(1im)有一个可以审这方面稿件的教授的名单Pi。一个教授可能为几个不同的议题审稿而出现在几个名单中。请判断，能否从这些名单中选出k个教授来组成一个审稿委员会使得每个议题都至少有一个委员可以审稿？(b) 我们为上面的判断型问题设计一个NP算法。在下面这个NP算法中，证书Y是选入委员会的教授名单。k-committee(P[1..m],k,Y)T¬{1,2,3,…,m} //需要审稿的议题集合S¬⋃1≤i≤mP[i] foreachpÎY ifpS thenreturnno //证书中不能有S之外的教授 endif fori1tom ifpÎP[i] thenT¬T–{i} //议题Ti有教授可审 endif endforendforif|Y|=kandT=Æ thenreturnyes elsereturnnoendifEnd(c) 假设图G(V,E)和正整数k是顶点复盖问题的一个实例，其中V={v1，v2，…，vn}，E={e1，e2，…，em}。现在我们构造一个审稿委员会问题的实例。首先，对应G中每一条边ei(1im)我们构造一个议题Ti，而对应G中每一个顶点uV，构造一个教授u。然后，对每一议题Ti(1im)构造一个可以审稿的教授名单Pi。这个名单由两个教授组成，就是构造Ti时所对应的边ei的两个端点所对应的教授。例如，ei=(u,v)，那么由顶点u和v所构造的教授u和v组成Pi，Pi={u,v}。下面看一个例子。下面的图是顶点复盖的一个实例。由上面这个图，我们构造9个议题，分别对应这9条边：T={T1,T2,T3,T4,T5,T6,T7,T8,T9}。然后构造5个教授，分别对应5个顶点:P={a,b,c,d,e}。接下来，为每个议题构造一个审稿教授名单如下：P1={a,b},P2={a,c},P3={a,e},P4={a,d},P5={c,e},P6={d,e},P7={b,c},P8={b,d},P9={b,e}。这个构造算法显然可以在多项式时间内完成。现在证明，原来图G中有一个k-复盖当且仅当所构造的问题中有一个k人组成的审稿委员会使得每一个议题都能有至少一个可审这方面稿件的教授在委员会中。假设图G中有一个k-复盖，那么由这k个点对应的k个教授组成的审稿委员会一定可以审任何一个议题的稿件。这是因为图中任何一条边e都与这个复盖中至少一个点v相关联，那么对应于e的议题可由对应的教授v审稿，而且教授v在委员会中。所以任何一个议题都能有至少一个可审这方面稿件的教授在委员会中。假设所构造的问题中有一个k个教授组成的审稿委员会使得每一个议题都能有至少一个可审这方面稿件的教授在委员会中。那么对应于这k个教授的k个顶点一定是G的一个复盖。这是因为图G的任一条边e所对应的议题可由委员会中一教授v审稿，那么边e一定与对应于教授v的顶点v相关联而且顶点v被选入复盖。所以对应于这k个教授的k个顶点一定是G的一个复盖。一个图G=(V，E)的顶点子集SÍV称为一个独立集(independentset)，如果E中任何一条边只与S中最多一个点有关联。也就是说，如果S中任意两点之间没有边，那么它就是一个独立集。最大独立集问题就是要找出图G的一个最大的独立集。请回答以下问题。定义与这个优化型问题对应的一个判断型问题。证明这个判断型问题属于NP类。证明这个判断型问题是NP完全问题。解：(a)对应的判断型问题可定义如下：给定一个图G(V，E)以及一个正整数k，判断G是否有一个含k个顶点的独立集。(b)下面是这个判断型问题的一个NP算法，其中证书Y是k个顶点的集合。Independent-Set(G(V,E),k,Y)检查Y中每个顶点v是否属于V；检查E中每条边(u,v)的两端点u或v是否至少有一个不属于Y；检查是否有|Y|=k；如果以上检查都是对的话，输出yes，否则no；End显然这是一个多项式检验算法。因为(b)部分已证明独立集问题属于NP类，我们只需证明它是NP难。我们把clique问题多项式归约为这个问题。假设图G(V,E)和整数k是一个clique问题的实例，我们构造一个独立集问题的实例如下：从图G(V,E)我们构造其补图G。这个构造显然可在多项式时间内完成。显而易见，如果图G(V,E)有一个含k个顶点的cliqueCV，那么在补图G中这k个顶点必定形成一个独立集。反之，如果在补图G中有一个含k个点的独立集C，那么在图G(V,E)中，集合C的k个点必定形成一个k-clique。所以独立集问题也是NPC问题。*一个图G=(V，E)的顶点子集SÍV称为一个支配集(dominatingset)，如果任何一个顶点vV都与S中一个点相邻。让我们称有k个顶点的支配集为k-支配集。最小支配集问题就是要找出图G的一个有最少顶点的支配集。下面图给出了一个例子。((a)顶点集合{a,b,c}是一个支配集但不是最小支配集aabcdefbcdef(b)顶点集合{c,d}是一个最小支配集请回答以下问题。(a) 定义与这个优化型问题对应的一个判断型问题。(b) 证明这个判断型问题属于NP类。(c) 证明支配集问题是NP完全问题。(d) 假设有一个多项式算法A解决这个判断型问题，请利用这个算法得到一个多项式算法来解决对应的优化型问题。解：(a) 对应的判断型问题可定义如下：给定一个图G(V,E)以及一个正整数k，判断G是否含有一个k-支配集。(b) 下面是这个判断型问题的一个NP算法，其中证书Y是k个顶点的集合。Dominating-set(G(V,E),k,Y)检查Y中每个顶点v是否属于V；检查V中每个顶点u是否与Y中某个顶点相邻；检查是否有|Y|=k；如果以上检查都是对的话，输出yes，否则输出no；End显然这是一个多项式检验算法。(c) 由问题(b)可知k-支配集问题属于NP类，我们只需证明其NP难。我们把顶点复盖问题多项式归约到k-支配集问题。假设图G(V,E)和正整数k是顶点复盖问题的一个实例，其中V={v1,v2,…,vn}，E={e1,e2,…,em}。下面是由此构造一个支配集问题实例的算法。首先，构造一个二部图G’(U’,V’,E’),这里U’=V={v1，v2，…，vn}，V’={e1，e2，…，em}，也就是说，对应G中每个顶点和每条边构造G’的一个顶点。边的集合E’由两部分组成。第1部分是E’1={(u,v)|u,vU’，uv}，也就是说，U’中点形成一个完全图。第2部分是E’2={(vi,ej)|viU’，ejV’，vi在G中是ej的端点}。下面的图(a)(b)给出了一个这样转换的实例。((b)图G’abcde(a)图Ge1e2e3e4e5e6abcdee1e2e3e4e5e6U’V’显然，这个转换算法只需多项式时间。现在证明，图G有一个k-复盖当且仅当G’有个k-支配集，kn。假设G有一个k-复盖。那么这k个顶点所对应的U’中的k个顶点是G’的一个支配集。这是因为G中每一条边都与这k-复盖中某个点关联，所以在G’中V’的每一个顶点都与U’中的这k个顶点中某个点相邻。再因为U’中的n个点形成一个完全图，因此U’中的每个点都与这k个顶点的任何一个相邻。因此，这k个顶点是G’的一个支配集。假设G’有一个k-支配集D(kn)，那么G一定有一个k-复盖。这里要说明一点，如果G’有一个k-支配集，而且k>n，那么一定不会是最小支配集，因为U’中n个顶点就是一个支配集，所以可假设kn。再有，我们可假设这个k-支配集中不含V’中点。这是因为如果顶点vV’属于这个k-支配集，而顶点uU’与v相邻，那么把v换为u后，DD{u}–{v}，D仍是一个k-支配集。(如果u也在k-支配集中，则得到一个(k-1)-支配集。)总之，如果G’有一个k-支配集，可假定这k个顶点都在U’中。显然，这k个顶点所对应的G中的k个点是G中的一个k-复盖，证毕。我们假定有一个多项式算法A解决这个判断型问题，A(G(V,E),k)=yes表示算法A判断G(V,E)有k-支配集，否则，A(G(V,E),k)=no。我们约定，如果图G(V,E)中V=，k=0，那么A(G(V,E),0)=yes。我们先确定最小支配集中顶点个数k。然后，逐个检查集合V中每个顶点v，并从中选取最小支配集的k个顶点。一开始，最小支配集D为空，而等待检查的顶点集合是W=V。如果点v被选上，则把它放在集合D里。检查过的点从W中删除。检查顶点v的步骤如下：在当前的图G(V,E)中，把点v以及它相邻的点Adj(v)删除后，如果余下的图G*有(k-1)个点的支配集，那么选取点v，DD{v}，更新W为WW–{v}–Adj(v)。下一步的工作是在W中找修改后的图G*的一个(k-1)-支配集。如果第(1)步中余下的图G*没有(k-1)-支配集，那么恢复当前图G(V,E)。这不表明点v就一定不属于k-支配集，但表明图G的k-支配集一定含有Adj(v)中的点。所以，我们重新构造G*。我们把点v从图G中删除，然后，如果需要，添加一些边使得Adj(v)中的点组成一个完全图。如果这样修改后的图G*有一个(k-1)-支配集，那么这个(k-1)-支配集加上点v就是图G的k-支配集。这是因为，这(k-1)-支配集支配Adj(v)以外的所有点，而点v支配Adj(v)中的点。因此，这种情况下，我们选取点v，DD{v}，更新W为WW–{v}。下一步的工作是在W中找修改后的图G*的一个(k-1)-支配集。如果第(2)步中修改后的图G*也没有(k-1)-支配集。这说明不可选取点v。这种情况下，恢复当前图G(V,E)，不更新D，但更新W为WW–{v}。这个多项式算法的伪码如下。Minimum-Dominating-Set(G(V,E),k)k¬1whileA(G(V,E),k）=no k¬k+1 //k是最小支配集中顶点数endwhileD¬ //支配集开始为空WV //W是可能被选为支配集中点while|D|≠k extractavertexvfromW //从W取一点v V*¬V-Adj(v) -{v} //V不变，构造V* E*¬{(x,y)E|xÎV*andyÎV*} //V*中顶点之间的边，E不变 ifA(G*(V*,E*,k-1)=yes //G*是余下的图 then D¬DÈ{v} G(V,E)¬G*(V*,E*) //下一步搜索G* k¬k-1 WW–Adj(v) //更新W else V*V–{v} //支配集中含Adj(v)中点 E*E–{(v,y)|yÎAdj(v)} //删除与v关联的边 E*¬E*È{(x,y)|x,yÎAdj(v)} //把Adj(v)补为完全图 ifA(G*(V*,E*,k-1)=yes then D¬DÈ{v} G(V,E)¬G*(V*,E*) k¬k-1 endif //否则，v不可取并已从W中删去，D不变 endifendwhilereturnDEnd如果图G=(V,E)的一条路径P经过图中每个点恰好一次，那么路径P称为一条哈密尔顿路径。判断图G=(V,E)是否有一条哈密尔顿路径称为哈密尔顿路径问题。证明哈密尔顿路径问题是个NP难问题。解：我们把哈密尔顿回路问题多项式归约为哈密尔顿路径问题。假设G(V,E)是哈密尔顿回路问题的一个实例。在多项式时间内，我们由G(V,E)构造一个哈密尔顿路径问题的实例，也就是图G’(V’,E’)。不失一般性，可假设G至少有3个顶点，否则G最多有两个点，不可能有回路。这个构造算法的步骤如下：G’(V’,E’)G(V,E)； //先复制图G在G中选取一个顶点a；在G’中加一顶点w和边(w,a)；在G’中再加上两顶点x和y，以及边(x,y)；如果在G中有边(a,v)，则在G’中加上边(v,x)。这样构造的图G’(V’,E’)中，V’=VÈ{w,x,y},E’=EÈ{(w,a),(x,y)}È{(v,x)|vÎAdj(a)}。下面的图给出了一个上面构造算法的一个例子。显然，这是一个多项式时间的构造算法。aadecbaadecbaw乙xy(a)图G(b)图G’现在，我们证明图G有一条哈密尔顿回路当且仅当图G’有一条哈密尔顿路径。假设G有一条哈密尔顿回路C，其顶点序列从a开始为<a,u,…,v,a>。那么在图G’中有一条哈密尔顿路径P，其顶点序列为<w,a,u,…,v,x,y>。也就是说，P从w到a，然后沿着哈密尔顿回路C走到顶点v。这时，P不走回到a，而是折向x后终止于y。假设图G’中有一条哈密尔顿路径P，那么P必须以顶点w和点y为起始点。可假设P的顶点序列为<w,a,u,…,v,x,y>。那么我们可以得到G的一条哈密尔顿回路C，其顶点序列为<a,u,…,v,a>，证毕。假设在一个城市里有m个家庭有小孩要上学，同时有n个学校可以保证每个家庭在150米之内至少有一个学校。假设这m个家庭编号为Hi(1im)，这n个学校编号为Sj(1jn)。现在由于经费短缺，需要关闭一些学校以节省开支，但仍然保证每个家庭在200米之内至少有一个学校可以上。经过调查，我们为每个学校Sj(1jn)列出在它200米内所有家庭的编号，即Pj={Hi|1im，Hi与Sj相距不超过200米}。一个优化问题是，我们希望在保证每个家庭有一个学校在200米内的基础上，关闭最多的学校。请为上述优化问题定义一个对应的判断型问题。证明该判断型问题属于NP类。证明该判断型问题是NP难问题。解:(a) 对应的判断型问题可表述为：假设在一个城市里有m个家庭有小孩要上学，同时有n个学校。假设这m个家庭编号为Hi(1im)，这n个学校编号为Sj(1jn)。经过调查，我们为每个学校Sj(1jn)列出在它200米内所有家庭的编号，即Pj={Hi|1im，Hi与Sj相距不超过200米}。请判断我们是否可以关闭k个学校但仍保证每个家庭有一个在200米内的学校不被关闭。这里，k是一个正整数。(b) 我们为此设计如下的一个多项式检验算法。其中，Y是一个含k个不同学校的证书。因此，该判断型问题属于NP类。Close-Schools(H[1..m],S[1..n],P[1..n],k,Y)if|Y|k thenreturnnoendifforeachyY //Y中元素必须是n个学校之一 forj1ton if(S[j]=nil)or(S[j]y) //S[j]=nil表示该校被关闭 thenjj+1 ifj>n thenreturnno //y不是学校或重复出现于Y endif elseS[j]nil //S[j]=y，该校被关闭 endif endforendforH //统计与余下学校200米距离内的所有家庭的集合forj1ton ifS[j]nil thenHHP[j] endifendforfori1tom ifH[i]H thenreturnno endifendforreturnyesEnd(c) 我们把顶点复盖问题多项式归约到这个问题。假设图G(V,E)和正整数k是顶点复盖问题的一个实例，其中V={v1,v2,…,vn}，E={e1,e2,…,em}。现在我们构造一个关闭学校问题如下：(1) 为每一个顶点vj(1jn)构造一个学校Sj。(2) 为每一条边ei(1im)构造一个家庭Hi。(3) 为每一个学校Sj(1jn)构造与其距离小于等于200米的家庭的集合Pj：Pj={Hi|边ei与点vj关联}。也就是说，如果边ei与顶点vj关联，那么，由边ei构造的家庭Hi与由顶点vj构造的学校Sj相距小于等于200米。(4) 置k’n-k。 例如，下面的图是找k-复盖的一个实例。我们把它转换为学校关闭问题的一个实例如下：学校集合为S={a,b,c,d,e,f}。家庭集合为H={e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}。Pa={e1,e2,e8,e9},Pb={e1,e6},Pc={e5,e6,e7,e10},Pd={e4,e5,e8},Pe={e3,e4,e9,e10},Pf={e2,e3,e7}。显然，图中顶点u复盖边e(即e与u关联)当且仅当u对应的学校距离e对应的家庭相距小于等于200米。如果图G(V,E)有个k-复盖，使得任一条边e关联于这k个顶点中某个顶点u，那么由e构造的家庭与由点u构造的学校就相距小于等于200米。所以，保留由这k-复盖中的k个顶点构造的学校就可保证每个家庭与其中一个学校相距小于等于200米。这也就是说，我们可以关闭k’(=n-k)个学校。反之，如果我们可以关闭k’(=n-k)个学校，使每个家庭H与某个不关闭的k个学校之一，学校s，相距小于等于200米，那么对应这个家庭H的边e就关联于对应这个学校s的顶点u。所以，对应这不关闭的k个学校的k个顶点就是图G(V,E)的一个k-复盖。所以，图G(V,E)有k-复盖，当且仅当构造的学校问题可以关闭k’(=n-k)个学校。因为上述转换显然只需多项式时间，所以学校关闭问题是个NP难问题。前面习题7中讨论的哈密尔顿路径问题，以及哈密尔顿回路问题都假定给定的图G=(V,E)是个无向图。请解释为什么在有向图中找哈密尔顿路径或回路也是NP完全问题。解：我们总可以把一无向图G(V,E)的哈密尔顿路径或回路问题多项式转换为有向图的哈密尔顿路径或回路问题。我们只要把无向图中每一条边(u,v)换为一对有向边(u,v)和(v,u)。这样一来，无向图G(V,E)中有一条哈密尔顿路径或回路当且仅当对应的有向图中有一条哈密尔顿路径或回路。所以，有向图中找哈密尔顿路径或回路也是NP完全问题。给定图G(V,E)，最长路径问题就是找一条最长的简单路径，也就是找一条路径P使得所含边数最多并且路径上每个顶点最多经过一次。这里，路径的起点和终点可任取。请为这个优化型问题定义一个相应的判断型问题并证明其NP难。解：对应的判断型问题可定义如下：给定图G(V,E)和正整数k，判断G是否有一条长度至少为k的简单路径。我们可以把哈密尔顿路径问题多项式归约为这个问题。假定图G=(V,E)是哈密尔顿回路问题的实例，其中|V|=n。我们把它转换为最长路径问题时仍用同一个图G，但置k=n-1，那么显然可见，图G(V,E)有一条哈密尔顿路径当且仅当图G有一条长度至少为n-1的简单路径。因此，最长路径问题是个NP难问题。在第10章的讨论中，我们知道如果一个加权的有向图中含有一个负回路，那么Bellman-Ford算法和Dijkstra算法都不能找到两个给定顶点间的最短简单路径。实际上，如果图中边的权限制为正整数或负整数，那么找两个给定顶点间的最短(简单)路径问题也是个NP难问题。请为这个优化型问题定义一个对应的判断型问题并证明它是NP难问题。解：对应的判断型问题可定义如下：给定一个加权有向图G(V,E)，其中每条边上的权可以是一个正整数或一个负整数。另外，给定V中两个顶点s和t，以及一个整数k(可正可负)，判断G是否有一条从s到t的简单路径P使得P的总权值小于等于k。我们把有向图的哈密尔顿回路问题多项式归约为这个最短路径问题。假设简单有向图G(V,E)是哈密尔顿回路问题的一个实例。我们由G(V,E)构造一个最短路径问题的实例G’(V’,E’)。不失一般性，可假设V至少有3个顶点，否则不可能有回路。我们构造图G’(V’,E’)如下：G’(V’,E’)G(V,E)。 //复制图G在V’中选取一个顶点a。在V’中加一顶点w和有向边(w,a)。在V’中再加上两顶点x和y，以及有向边(x,y)。如果在E中有边(v,a)，则在E’中加上边(v,x)。构造的图G’(V’,E’)中，V’=VÈ{w,x,y},E’=EÈ{(w,a),(x,y)}È{(v,x)|(v,a)ÎE}。给E’中每一条边(u,v)赋值为-1，即w(u,v)=-1。置k=-(n+2)。下面的图给出了一个上面构造算法的一个例子。显然，这是一个多项式时间的构造算法。aadecbaadecbaw乙xy(a)图G(b)图G’-1-1-1-1-1-1-1-1-1-1-1-1现在，我们证明图G有一条哈密尔顿回路当且仅当G’有一条总权值小于等于k的从点w到点y的路径。假设G有一条哈密尔顿回路C，设其顶点序列从a开始为<a,u,…,v,a>。那么在图G’中有一条从点w到点y的路径P，其顶点序列为<w,a,u,…,v,x,y>。也就是说，P从w到a，然后沿着哈密尔顿回路C走到顶点v。这时，P不走回到a，而是折向x后终止于y。显然。路径P的总权值是k=-(n+2)。假设图G’中有一条总权值小于等于k的从点w到点y的路径P。那么，路径P的顶点序列必定是为<w,a,u,…,v,x,y>。又因为|P|k=-(n+2)，它必须含有至少(n+2)条边。所以它的子路径<a,u,…,v>必定含有至少(n-1)条边，那么，加上边(v,a)后，就得到图G的密尔顿回路C=<a,u,…,v,a>。所以，由本题可见，即使权值是整数，有负回路的图的最短路径问题是个NP难问题。假设一个连通图G(V,E)的每一条边有一个非负整数的权，我们希望判断是否可以找到一个支撑树使得树中所有边的权之和正好是k。请证明这个问题是个NP难问题。解：我们把子集和问题多项式归约为这个支撑树问题。假定一个子集和问题的实例是含n个正整数的集合S={a1,a2,…,an}和目标值t。我们由此构造一个支撑树问题的一个实例。步骤如下：对应每个整数ai(1£i£n)，构造一个三角形，(xi,yi,zi)，并且赋以权值w(xi,yi)=w(yi,zi)=0，w(zi,xi)=ai。在顶点xi和xi+1之间联一条边并赋以权值w(xi,xi+1)=0(1£i£n-1)。置k=t。下面的图显示了这样构造的图。显然这个构造只需多项式时间。现在证明，集合S有子集和为t当且仅当所构造图有一棵支撑树，其总权值为k。假设S有子集AÍS使得ai∈Aai=t。那么，如果aiA，我们在图中对应于ai的三角形(xi,yi,zi)中把边(xi,yi)删去，否则把(xi,zi)删去。这样得到的一棵支撑树的总权值显然等于ai∈A如果所构造的图有一棵支撑树T，它的总权值等于k，那么在图中对应于ai的三角形(xi,yi,zi)中必定有两条边属于T而第3条边被刪去。从图的构造可知，T的总权值=(zi,xi)∈Tw(zi,xi)=k。我们可以这样构造集合A：如果边(zi,xi)属于T，我们则把ai选入集合A，否则不把ai选入集合A。这样一来，ai∈Aai=(zi,xi)∈Ta由上面讨论可知，本题中的问题是个NP难问题。给定一个连通图G(V,E)，我们希望找到一个支撑树使得树中的叶结点最少。例如，下面图(ii)和(iii)都是图(i)的支撑树，分别有4个叶结点和3个叶结点，图(iii)的解较好。请回答以下问题：为本题的优化型问题定义一个对应的判断型问题。证明这个问题是NPC问题。aabcdefg(iii)abcdefg(i)abcdefg(ii)解：(a) 对应的判断型问题可定义如下： 给定一个连通图G(V,E)和一个正整数k，判断G是否含有一个叶子数少于等于k的支撑树。(b) 为证明这个问题是NPC，我们先证明它属于NP类。我们用的证书是一棵支撑树的边的集合Y。下面的伪码检验Y是否是叶子数少于等于k的支撑树。Verification-k-Leave-Spanning-Tree(G(V,E),k,Y) //|V|=nV’¬V //开始构造这个支撑树T=G’(V’,E’)foreachvV’ //开始时，这个支撑树G’(V’,E’)没有边 Adj(v) deg(v)0 //顶点v的度endforE’¬foreachedge(u,v)ÎY if(u,v)ÏE thenreturnno else EE–{(u,v)} //避免下次重复 E’¬E’{(u,v)} Adj(u)Adj(u){v} Adj(v)Adj(v){u} deg(u)deg(u)+1 deg(v)deg(v)+1 endifendfor //支撑树T=G’(V’,E’)完成if|E’|n-1 //支撑树必须正好有n-1条边 thenreturnnoendifselectavertexsÎV’ //取一顶点sBFS(G’(V’,E’),s) //从s开始作一轮广度优先搜索number-of-leaves¬0 //统计叶子个数foreachvinV’ ifcolor(v)=White thenreturnno //存在未访问的白点，G(V’,E’)不可能是支撑树 else ifdeg(v)=1 //v是个叶子 thennumber-of-leaves¬number-of-leaves+1 endif endifendfor //G(V’,E’)连通且有n-1条，是支撑树ifnumber-of-leavesk thenreturnyes elsereturnnoendifEnd现在证明这个问题是NP难。我们把哈密尔顿路径问题多项式归约为这个问题。假定图G是哈密尔顿路径问题的一个实例。当我们把哈密尔顿路径问题多项式归约到支撑树时，仍用这个图G并置k=2。显然，图G有一条哈密尔顿路径当且仅当图G有一个2个叶子的支撑树。所以本题中的问题是NP完全问题。假设我们有n个独立的任务，J1,J2,...,Jn，要从时间t=0开始在两个同样的处理器上执行。假设Ji(1in)需要Ti秒的时间完成并且一旦开始执行，必须不中断地在同一个处理器上运行直止完成。我们希望找到一个调度，即任务安排，使这n个任务可以在最短时间内完成。例如，如果有3个任务，其执行时间分别为T1=4秒,T2=5秒,T3=7秒,那么下面图示的调度用9秒钟可以把它们完成。这个调度显然是最好的。请回答下面问题。TT1T2T3处理器1处理器2t=0213456879(a) 为上述调度问题定义一个对应的判断型问题。(b) 证明该调度问题是个NP难问题。解：(a) 对应的判断型问题可定义如下：假设我们有n个独立的任务，J1,J2,...,Jn，要从时间t=0开始在两个同样的处理器上执行。假设Ji(1in)需要Ti秒的时间完成并且一旦开始执行，必须不中断地在同一个处理器上运行直至完成。判断是否存在一个调度使这n个任务可以在k秒内完成。(b) 我们把集合平分问题多项式归约为这个问题。假设集合平分问题的一个实例中，S={a1,a2,…,an}是n个正整数，其和为i=1nai=2m。我们由此构造一个调度问题的实例如下。我们为每个整数ai构造一个对应的独立任务Ji，并置它的执行时间为Ti=ai(1≤i≤n)。另外，置k=m我们用P1和P2分别表示调度问题中的两个处理器，也表示调度给它们执行的任务的集合。下面我们证明，如上构造的n个任务，J1,J2,...,Jn，可以在P1和P2上在k秒内完成当且仅当这个集合S可被平分。假设集合S可被平分，即存在子集AS使得ai∈Aai=ai∈S-Aai=m。那么，我们可设计任务调度如下：我们把对应于集合A中整数的任务分配给P1，而把对应于集合S-A中整数的任务分配给P2，即P1={Ji|aiA(1≤i≤n)}，P2={Ji|aiS–A(1≤i≤n)}。在各处理器中的任务从t=0开始一个接一个顺序完成。这样一来，因为Ti=ai(1≤i≤n)，所以P1完成所有任务的时间是Ji∈P1Ti=ai∈Aai=m=如果所构造的n个任务，J1,J2,...,Jn，可以在P1和P2上在k秒内完成，即Ji∈P1Ti=Ji∈P2Ti=k，那么我们可以把集合S平分如下：A={ai|JiP1(1≤i≤n)}，即把对应于P1所执行的任务的整数选入子集A。这样，子集A中的整数之和为ai∈Aai=Ji∈P1Ti=k=m。而子集S–A因此，我们证明了集合平分问题可多项式归约为本题的调度问题。因为集合平分问题是个NPC问题，所以本题的调度问题是NP难。假设计算机中有n个文件，f1,f2,…,fn，需要存入两张光盘中。这n个文件所需的空间分别是s1,s2,…,sn(以千字节KB为单位)，而每张光盘的容量都是M(KB)。假设存入一个文件不需要额外的空间开销，并且所有文件所需的空间总和不超过2M，即i=1nsi2M。我们需要判断这两张光盘是否有足够的空间存入这n个文件。请证明这个判断解：如果我们把文件fi看为任务Ji，si视为执行时间Ti，把二张光盘1和2看为处理器P1和P2，把文件fi存入光盘1看为把任务分配给P1，把文件fi存入光盘2看为把任务分配给P2，那么用类似第14题中的证明可以证明这个判断问题是个NP难问题，或者把任务调度问题多项式归约到这个问题来证明这个判断问题是个NP难问题。装箱问题(binpacking)是说有n个物体，O1,O2,…,On，需要装箱。这n个物体分别有体积si并且满足0<si£1(1in)。假定每个箱子的容积是1，我们希望用最少的箱子把它们装入。我们假定任何一组物体，只要它们的总体积不超过1，都可以装入一个箱子之中。回答下面问题。为这个优化型问题定义一个对应的判断型问题。证明这个判断型问题是NP难问题。解：(a) 这个对应的判断型问题可定义如下：有n个物体，O1,O2,…,On，需要装箱。这n个物体分别有体积si，并且满足0<si£1(1in)。假定有k个箱子，而每个箱子的容积是1，并且假定任何一组物体，只要它们的总体积不超过1，都可以装入一个箱子之中，判断这n个物体是否可以装入这k个箱子之中。(b) 我们把集合平分问题多项式归约到这个装箱问题。假设集合平分问题的实例中，S={a1,a2,…,an}是n个非负整数的集合，其和为i=1nai=2m。我们可假定ai≤m(1≤i≤n)，否则S不可平分，那我们只需构造一个不可能事件即可，例如让k=1，s1=0.8,s2=0.8。假定ai≤m(1≤i≤n)，那么我们构造一个k=2的装箱问题如下：为每一个整数ai(1≤i≤n)，构造一个物体Oi，并且赋以体积si=aim≤1。显然，这是一个多项式时间的转换算法。下面证明，这样构造的(1) 假如构造的n个物体可装入两个箱子B1和B2中，那么必定有Oi∈B1si1，Oi∈B2si1。但是因为Oi∈B1si+Oi∈B2si=i=1nsi=i=1naim=1mi=1nai=2mm=2，所以必有Oi∈B1si=Oi∈B2si=1。我们可以相应地把集合S平分如下：我们把装入B1中的物体所对应的整数组成S的子集A，即A={ai(2) 假如集合S可平分，即存在一个子集A，使得ai∈Aai=ai∈S-Aai=m。那么我们可以把A中整数对应的物体组成集合B1，即B1={Oi|aiA}。因为ai∈Aai=m，所以B1中物体的体积之和为Oi∈B1si=Oi∈B1aim=1mOi∈B因此，我们证明了集合平分问题可多项式归约为本题的装箱问题。因为集合平分问题是个NPC问题，所以本题的装箱问题是NP难。(两条点不相交路径问题) 证明下面的判断型问题是NP难问题：给定一个加权的有向图G(V，E)和V中两个顶点s和t，以及正数k，判断图G是否有两条顶点不相交的从s到t的简单路径使得每条长度均不大于k？这里“不相交”是指除了起点s和终点t以外，两条路径上所有顶点都不同。这个问题在网络的路由问题中有实际应用的背景。提示：把集合平分问题多项式归约到这个问题。假设集合平分问题的一个实例中，S={a1,a2,…,an}是n个非负整数，其和为i=1nai解：我们把集合平分问题多项式归约到这个问题。假设集合平分问题的一个实例中，S={a1,a2,…,an}是n个非负整数，其和为i=1nai=2m。我们构造一加权的有向图G如提示中图所示，并置k=m。显然，这是一个多项式时间的转换。现在证明，S可平分当且仅当图G中有两条顶点不相交的从s到t假如S可平分，即存在一个子集A，使得ai∈Aai=ai∈S-Aai=m。那么，我们可以构造一条对应集合A中整数的路径P1如下：从s开始到顶点u1，然后，如果a1A，那么P1到达的下一个顶点是v2，否则是u2。往下，类似地决定P1要到达的下一个点。原则是，如果P1到达的当前顶点是ui或vi时(i1)，如果aiA，那么下一个到达的点是vi+1，否则是ui+1。当到达顶点un+1或者vn+1后，下一步到达终点t。因为从i=1开始，每一条到达vi+1的边有权ai，而到达ui+1的边的权为0，因此这条路径的长度为w(P1)=vi+1∈P1ai=ai∈Aai=m=k。现在我们构造另一条路径P2如下：从s开始到顶点v1。然后，决定P2要到达的下一个点。原则是，如果P2到达的当前顶点是ui或vi时(i1)，如果aiS-A，那么下一个到达的点是vi+1，否则是ui+1。当到达顶点un+1或者vn+1后，下一步到达终点t。显然，如果P1经过顶点ui+1那么P2则经过顶点vi+1，反之，如果P1经过顶点vi+1那么P2则经过顶点ui+1，所以P1和P2是两条顶点不相交的从s到t的简单路径。另外，P假如所构造的图G有两条顶点不相交的从s到t的简单路径，P1和P2，每条长度不大于k。不失一般性，可假定P1经过点u1而P2经过点v1。我们可如下平分S：如果P1经过点vi+1(1in)，则把ai选入子集A中。这样一来，子集A中整数和为ai∈Aai=vi+1∈P1ai=w(P1)k=m。类似的，如果P2经过点vi+1，则把ai选入子集S–A中。子集S-A中整数和为ai∈S-Aai=vi+1∈P2ai=w(P2)k=m。因为顶点vi+1(1in)必定被两条路径之一经过，所以有w(P1)+w(P2)=i=1nai=2m。因此，w(P1)=因此，我们证明了集合平分问题可多项式归约为本题的顶点不相交的路径问题。因为集合平分问题是个NPC问题，所以本题的顶点不相交的路径问题是NP难。0/1背包的优化问题(0/1knapsackoptimizationproblem)定义如下：设U={O1,O2,…,On}是n个物体的集合。物体Oi的体积和它的价值分别为wi>0和vi>0(1£i£n)。另外，有一个容积为W的背包。任意一组物体，只要它们的体积总和不超过W就可以装入这个背包。我们希望从集合U中选出一个子集Q使子集中物体的体积总和不超过W，但是它的总价值最大。我们称这个问题为0/1背包的优化问题是因为它不允许一个物体被切下一部分来放入背包。请回答下面问题。为0/1背包的优化问题定义一个对应的判断型问题。证明这个0/1背包问题是NP难问题。解：(a) 0/1背包的判断型问题可定义如下：设U={O1,O2,…,On}是n个物体的集合。物体Oi的体积和它的价值分别为wi>0和vi>0(1£i£n)。另外，给定一个容积为W的背包和一个称为“价值期望”的正数k，判断是否存在U的一个子集Q使得子集Q中所有物体的体积总和不超过W而它们的价值总和大于等于k？(b) 我们把集合平分问题多项式归约为这个问题。假设集合平分问题的一个实例中，集合S={a1,a2,…,an}含n个非负整数，其和为i=1nai=2m。我们构造一个0/1背包问题的实例如下：对应S中每个整数ai(1£i£n)，构造一个物体Oi并赋以wi=vi=ai。这n个物体组成集合U。另外，置这个背包的容积为W=m和价值期望k=m。显然，这个构造可在多项式时间内完成。下面证明，这样构造的0/1背包问题有yes(1) 假设集合S可平分，即存在一个子集A，使得ai∈Aai=ai∈S-Aai=m。那么，我们把子集A中整数所对应的物体选入子集Q中，即Q={Oi|aiA}。这样选出的子集Q中所有物体的总的体积和是V=Oi∈Qwi=ai∈Aai=m=W，而它们的总价值为Z=Oi∈Q(2) 假设在构造的0/1背包问题中，存在一个物体的集合Q使得它们的总体积小于等于背包容积W，而它们的总价值大于等于价值期望k。那么，我们可以在集合S找出一个子集A如下：如果物体Oi被选在集合Q中，那么Oi对应的整数ai属于子集A，即A={ai|OiQ}。这样的话，A中所有整数之和是ai∈Aai=Oi∈QwiW=m。但由于Q中物体的总值价大于等于价值期望k，我们有ai∈Aai=Oi∈Qvik=m，因此有a因此，我们证明了集合平分问题可多项式归约为本题的0/1背包的问题。因为集合平分问题是个NPC问题，所以本题的0/1背包的问题是NP难。(推广的货郎担问题）假定G(V,E)是一个加权的连通图，其中每条边的权是一个非负实数。推广的货郎担问题就是在G中找一条经过每个顶点至少一次的回路C，使得它的所有边的总权值最小。如果我们把每个顶点看作一个城市，把一条边看作一条航线，而边上的权看为航线距离的话，那么这个回路就是一个货郎担周游每个城市后回到原地的路线图，而且该路线图的总路程最小。注意，这个问题与原货郎担问题的不同在于它不要求G是个完全图并允许货郎担经过一个城市多次，只要总路程最小即可。另外要注意的是，一条经过每个点正好一次的回路不一定比经过多次的这条推广的货郎担回路的总路程短。下面的图给出了一个例子。aa一1111111bcdef100100经过每个顶点正好一次的回路，<a,b,f,e,d,c,a>,的总权值为105。推广的货郎担回路，<a,b,f,e,a,d,c,a>,的总权值为7。显然，一个连通图一定有经过每个点的回路，但不一定是简单回路。请证明，判断一个连通图G是否有总长小于等于k的推广的货郎担回路是个NP难问题，这里k是一个给定的正数。解：我们把哈密尔顿回路问题多项式归约到这个问题。设图G(V,E)是哈密尔顿回路问题的一个实例。如果G(V,E)是个非连通图，则不存在哈密尔顿回路，我们可随便构造一个无解的推广的货郎担问题即可，例如构造一个有3个点的三角形并使每条边权值为2，但置k=1。所以，我们可假定G(V,E)是个连通图。我们在构造对应的推广的货郎担问题的图G’(V’,E’)时，用同样的顶点集合和边的集合，即V’=V,E’=E。另外，赋以每条边的权值为1，并置k=|V|。可以证明图G有一条哈密尔顿回路当且仅当G’有一条推广的货郎担回路并且总权值小于等于k。如果图G有一条哈密尔顿回路，那么，在G’中这条回路对应于一条推广的货郎担回路。由于每条边权值为1，那么这条回路总权值为|V|=k。如果图G’有一条推广的货郎担回路并且总权值小于等于k，由于每条边权值为1，那么这条回路最多有k=|V|条边。又因为每个顶点必须经过至少一次，那么这条回路必定至少有|V|条边。但是，这条回路的边数又不能大于|V|=k条边，否则总权值会大于k。因此，这个回路必定经过每个点正好一次。那么，这个回路对应G中的一条哈密尔顿回路。因此，我们证明了，哈密尔顿回路问题可多项式归约到这个推广的货郎担问题。因为哈密尔顿回路问题是个NPC问题，所以本题的推广的货郎担问题是个NP难问题。我们知道图的k-着色问题是个NPC问题。其实，图的3-着色问题就已经是个NP难问题了。下面，我们把3-SAT问题多项式归约为这个问题。假设是一个3-CNF的表达式，它含有n个变量，x1,x2,…,xn，和m个子句，=C1C2…Cm。我们构造一个3-着色的实例，也就是一个图G=(V,E)如下：我们为表达式中每一个变量xi和它的非xi各构造一个顶点，并标以xi和xi。构造3个特殊的顶点并分别标以真、假、空，并把它们联结为一个三角形。为每一个子句，Cj(1jm)，如下图(a)构造5个新顶点，a,b,c,d,e。然后，把Cj中3个文字对应的3个顶点，5个新顶点，以及顶点“真”，一共9个顶点按下面图(a)联成一个子图。图中x、y、z表示子句Cj中的文字。(a)(a)(b)xyz真空假zxyz真abcdeabcde如图(b)所示，把每一对点xi和xi(1jn)，以及特殊点“空”之间连成一个三角形。为清晰起见，图(b)中只显示了一对点z和z。实际构造时应为每一个变量xi构造一个三角形。现在，图构造好了，证明这是个多项式归约，所以3-着色问题是个NP难问题。解：以上构造显然只需多项式时间。我们只需证明，这样构造的图可以3-着色当且仅当表达式可以被满足。证明如下：假设构造的图可以3-着色，我们假定用真、假、空三种颜色，并可假定这三个特殊顶点分别着以真、假、空，三色。那么在3-着色中，因为任何文字对应的顶点与标为“空”的点相邻，它们对应的顶点必然是着色为真或假。如果一个文字对应的顶点是着色为真，我们就把表达式中的这一文字賦值为1，否则是0。这么賦值是合法的，因为变量xi和它的非(xi)之间有边，它们对应的顶点着色不同。所以，必然是一个賦值为1，另一个是0。我们要证明每个子句中必定有一个文字赋值为1，也就是要证明每个子句中必定有一个文字对应的顶点着色为真。如若不然，为用反证法设某子句中三个文字对应的顶点x、y、z均着色为假，那么，如下图所示，按a、b、c、d、e顺序简单的推理可知，顶点a和b必定着色为空和真，顶点c必定着色为假，顶点d必定着色为空。那么顶点e必须着色为假。这与顶点z的着色矛盾，所以这个子句的子图不可能被三着色。因此，每个子句中必定有一个文字赋值为1，从而表达式可以被满足。xxyz真假假假必须=假，与z矛盾假(只能空或真)假(只能空或真)必须=假必须=空abcde(2) 假设表达式可以被满足，那么我们对构造的图3-着色如下：首先把三个特殊顶点分别着以真、假、空，三色，与其标记一致。然后，如果一个文字赋值为1，则将它对应的顶点着色为“真”否则为“假”。最后，我们把对应每个子句(xyz)的子图中5个未着色顶点着色如下。我们分两种情况讨论。(2.1) 如果子图中与点e相连的点z着色为“真”，那么其余点可如下面图(c)所示着色。图中，我们用

色(x)表示着与x相同的颜色(同为“真”或同为“假”，而色(x)表示着与x相反的颜色。)(2.2) 如果子图中与点e相连的点z着色为“假”，那么，其余两个文字对应的顶点之一必定着色为“真”。不失一般性，设色(x)=“真”，那么子图中其余点可如下图(d)所示着色。显然，这个着色是个合法的3着色。因此，我们证明了，3-SAT问题可多项式归约为3-着色问题。因为3-SAT问题是个NPC问题，所以3-着色问题是个NP难问题。真真xyz真假色(x)空空abcde色(x)(c)xyz真假空假空假abcde真(d)真假设我们需要把某煤矿的煤用卡车一次性运往两个地方。又假设我们有n部卡车，其装载量只有两种，一种是5吨的卡车，另一种是8吨的卡车。假设我们有a部5吨的卡车，b部8吨的卡车，a+b=n。我们希望把这些卡车分成两组，各组负责送一个地方，并且使得两个地方获得相等重量的煤。我们假定煤矿有足够的煤供运输并且每辆车必须满载。如果不能使两地获得正好相等的煤，那我们希望两者差别越小越好。你认为这问题是NP完全问题吗？如果不是，请给出一个多项式算法，否则，请证明这是一个NP完全问题。解：这不是NP完全问题。它的一个多项式算法如下: Truck-Partition(a,b)M5a+8b //总的运输量L0 //L是第一组的总装载量，初始为0fori0toa //为第一组寻找卡车组合，使总的装载量不超过，但最接近M/2 forj0tob P5i+8j ifP>LandPM/2 then LP ki hj endif endforendforreturn(k,h,L)//分给第一组k部5吨卡车和h部8吨卡单。总共装载量是L吨。End这个算法穷举所有可能的组合，并且从中找出最佳的解，所以算法正确。又因为所有可能的组合不超过(a+1)(b+1)=O(n2)，这是一个多项式算法。假设我们需要把某煤矿的煤用卡车一次性运往三个地方。又假设我们有n>3部卡车，其装载量分別是c1，c2，…，cn，且都是以整数公斤为单位。我们希望把这些卡车分成三组，各组负责送一个地方，并且使得三个地方获得相等重量的煤。我们假定煤矿有足够的煤供运输并且每辆车必须满载。请证明判断这个分组问题是否有解是个NP难问题。证明：我们把集合平分问题归约到这个问题。设集合平分问题中集合是S={a1，a2，…，an}(n>2)。我们构造分组问题如下：计算M=i=1n可假定M是个偶数，M=2k。否则，集合划分问题无解，我们可以构造一个无解的运输分组问题。构造(n+1)部卡车，其中头n部卡车的装载量分別是c1=a1，c2=a2，…，cn=an，第(n+1)部卡车有装载量k=M/2。显然，集合划分问题有解当且仅当这个构造的分组问题有解。因为构造这分组问题只需多项式时间，所以集合划分问题可多项式归约到这个卡车分组问题。所以这个卡车分组问题是个NP难问题。在第9章习题14中我们討论过2-树支撑森林的问题。这里我们考虑最小-最大(min-max)2-树支撑森林的问题。给定一个加权的连通图G(V,E)，最小-最大(min-max)2-树支撑森林的问题是找出一个2-树支撑森林，T1和T2，使得有较大权值的树的权，即max{W(T1),W(T2)}，在所有2-树支撑森林中是最小的。回答以下问题。定义与这个优化型问题对应的一个判断型问题。证明这个判断型问题是个NP难问题。解：(a) 以下是对应的一个判断型问题：给定一个加权的连通图G(V,E)和一个实数k，判断是否存在一个2-树支撑森林，T1和T2，使得max{W(T1),W(T2)}k?(b) 我们把集合平分问题多项式归约到这个问题。假设集合平分问题的一个实例中，S={a1,a2,…,an}是n个正整数的集合，其和为i=1nai=2m。我们假设aim(1) 构建两个顶点，p和q。(2) 为每一个数字ai(1≤i≤n)，构建一个顶点vi和两条边，(p,vi)和(q,vi)。它们的权值为w(p,vi)=w(q,vi)=ai。(3) 置k=m。显然，这个构造算法是个多项式算法，下图给出一个例子。集合集合S={5,8,11,7,6,9,2}总和2m=48v1v2v3v4v5v6v75588111177669922pq由集合S构造的图G，k=24 现在我们证明，所构造的图G有一个2-树支撑森林，T1和T2，使得max{W(T1),W(T2)}k当且仅当集合S可平分。假设集合S可平分为A和S-A，使得ai∈Aai=ai∈S-Aai=m。我们可以如下构建T1={(p,vi)|aiA}。T2={(q,vj)|ajS-A}。因为每个顶点vi(1≤i≤n)与点p或q相连，且T1和T2没有交点，T1和T2形成一个2-树支撑森林。又因为w(p,vi)=ai，我们有W(T1)=ai∈Aw(p,vi)=ai∈Aai=m=k。类似地，W(T2)=aj∈S-Aw(q,vj)=aj∈S-Aaj=m=k假设所构造的有向图G有一个2-树支撑森林，T1和T2，使得max{W(T1),W(T2)}k，那么集合S可如下平分为A和S-A。我们分三种情况：(2.1)点p和q同属T1。这时，T2中的点不可以与p和q相邻，只能以孤立点出现(度数为0)。因此，T2没有边，且只含一个点。这时，在T1中的每个点vi(1≤i≤n)必须与点p或点q相邻。另外，至少有一个点vi(1≤i≤n)与点p和点q都相邻，否则点p和点q不连通。这使得W(T1)>m=k，所以这种情况不可能出现。(2.2)点p和q同属T2。与情况(2.1)类似，这种情况不可能出现。(2.3)点p和q分属于T1和T2。不失一般性，设pT1，qT2。这样的话，任一其它顶点vi(1≤i≤n)必定属于T1或T2。如果vi属于T1，那么，边(p,vi)必定包含在T1中，而边(q,vi)必定被排除在T1和T2之外。所以，我们有：W(T1)=vi∈T1W(T2)=vj∈T2因此，如果顶点vi属于T1，我们把集合S中对应于vi的数ai放入集合A中，否则放入集合S-A中，即A={ai|vi属于T1}，S-A={aj|vj属于T2}。因为w(p,vi)=ai，故有ai∈Aai=vi∈T1w(p,vi)≤k=m。类似地，aj∈S-Aaj=vj∈T2w(q,vj)≤k=m。因为ai∈Aai+因此，我们证明了，集合平分问题可多项式归约到这个最小-最大2-树支撑森林问题。因为集合平分问题是个NPC问题，所以最小-最大2-树支撑森问题是个NP难问题。考虑以下活动选择问题。假设礼堂从时刻t=0到t=T>0这一段可以安排活动。假设时间单位都以分钟计算。现在有n个活动，a1，a2，…，an，申请使用礼堂。每个活动ai(1in)需要连续占用礼堂ti分钟，并且必须安排在时刻si(0≤si)或早于时刻si开始。当然，在任何时刻，只能允许一个活动占用礼堂，并且所有被选取的活动要在时刻T之前完成。我们希望选出一个活动的集合A使得礼堂被使用的时间，即ai∈At定义与这个优化型问题对应的一个判断型问题。证明这个判断型问题是个NP难问题。解：(a) 以下是对应的一个判断型问题：假设礼堂从时刻t=0到t=T>0这一段可以安排活动。假设时间单位都以分钟计算。现在有n个活动，a1，a2，…，an，申请使用礼堂。每个活动ai(1in)需要连续占用礼堂ti分钟，并且要求在si(0)或早于si开始。被选中的活动必须能安排在t=T之前完成。在任何时刻，只能允许一个活动占用礼堂。请判断是否存在一个满足上述要求的互相兼容的活动的集合A使得礼堂被使用的时间大于或等于k，即ai∈Ati(b) 我们把子集和问题多项式归约到这个问题。假设子集和问题的一个实例中，S={v1,v2,…,vn}是n个正整数的集合，另有一个目标值t>0。子集和问题要求判断是否有一个S的子集V,VS，使得vi∈Vvi=t。我们把这个(1)置T=t(目标值)。礼堂从时刻t=0到T>0这一段可以安排活动。(2)为每一个S中数vi(1≤i≤n)，构建一个活动ai使得ti=vi，si=T-ti。(3)置k=t。显然这个转换只需多项式时间。下面证明，如果集合S有子集V,VS，使得Vi∈Vvi=t，那么，所构造的活动中存在一个集合A假设集合S有子集V,VS，使得vi∈Vvi=t=T。我们可以如下选出活动的集合A：如果数字vi在子集V中，viV，那么，对应于vi所构造的活动ai入选，即A={ai|viV}。因为vi∈Vvi=t，而ti=vi，故有ai∈Ati=vi∈Vvi=T=t=k。又因为si=T-ti和假设所构造的活动中存在一个集合A使得礼堂被使用的时间大于或等于k，ai∈Ati≥k。我们可以如下找出子集V：如果aiA，那么我们从集合S中把构造ai时所用的数字vi放在子集V中，即V={vi|aiA}。因为礼堂可用的时间不会超过T，即ai∈AtiT=t=k，所以ai∈Ati≥k意味着ai∈Ati=T=t。那么，因为ti=vi，我们有vi∈Vvi=因此，我们证明了，子集和问题可多项式归约到这个活动选择问题。因为子集和问题是个NPC问题，所以这个活动选择问题是个NP难问题。考虑以下活动选择问题。假设我们有两个礼堂可以从时刻t=0安排活动。假设时间单位都以分钟计算。现在有n个活动，a1，a2，…，an，要求使用一个礼堂，两个礼堂中任一个都行。活动ai(1in)必须安排在时刻si(0≤si)或早于时刻si开始，但一旦开始，需要连续占用该礼堂ti分钟。当然，在任何时刻，任一个礼堂只能允许一个活动占用。我们希望选出一个有最多活动的集合A使得这些活动可以互相兼容地使用这两个礼堂。回答以下问题。定义与这个优化型问题对应的一个判断型问题。证明这个判断型问题是个NP难问题。解：(a)对应的一个判断型问题可定义如下：假设我们有两个礼堂可以从时刻t=0安排活动。假设时间单位都以分钟计算。现在有n个活动，a1，a2，…，an，要求使用一个礼堂，两个礼堂中任一个都行。活动ai(1in)可以安排在时刻si(0≤si)或早于时刻si开始，但一旦开始，需要连续占用该礼堂ti分钟。当然，在任何时刻，任一个礼堂只能允许一个活动占用。请判断，我们能否选出有至少k个活动的集合A使得这些活动可以互相兼容地使用这两个礼堂？这里，kn是一个正整数。(b)我们把集合平分问题多项式归约到这个活动选择问题。假设集合平分问题的一个实例中，S={v1,v2,…,vn}是n个正整数的集合，其和Vi∈Svi=2m(m是正整数)。我们假设vi为S中每一个数vi构造一个活动ai，它需要占用礼堂的时间是ti=vi，它的开始时刻是si=m-vi或早于si。置k=n。这显然是个多项式时间的转换算法。我们证明集合S可平分当且仅当我们构造的n个活动可以互相兼容地使用这两个礼堂。假设集合S可平分为子集A和S-A，使得vi∈Avi=vi∈S-Avi=m。那么，我们可以为第一个礼堂选择活动如下：H1={ai|viA}，也就是选取由子集A中数字所构造的所有活动。因为ti=vi，我们有ti∈H1ti=vi∈Avi=m。因为它们的开始时刻只要是si=m-vi或更早即可，所以我们只需把它们一个接一个地安排在第一个礼堂，便可以互相兼容地使用这个礼堂。同理，其余的活动是由集合S-A中数字所构造的活动，我们可以把它们安排在第二个礼堂，H2={ai|viS-A}。因为假设我们构造的n个活动可以互相兼容地使用这两个礼堂。设H1是安排在第一个礼堂的活动，H2是安排在第二个礼堂的活动。那么，我们可以平分集合S如下：A={vi|aiH1}，也就是构造H1中活动所用的数字的集合。显然，由余下的数字S-A构造的活动必定安排在第二个礼堂，即S-A={vi|aiH2}。因为ti∈H1ti≤m，ti∈H2ti≤m，而ti∈H1ti+ti∈H2ti=vi∈Avi+v∈S-Avi=vi∈Svi=2