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

PAGE12第15章 近似算法找出一类图的例子说明近似算法Approx-Vertex-Cover始终得不到它的最佳解。解： 有奇数个顶点的一根直线就是这类图的例子。如下图所示，设这根线的顶点数为2k+1，那么最佳解是k个不相邻的顶点。但是近似算法Approx-Vertex-Cover每次取两个相邻点，也就是取一系列的边，而且所取的相邻的两条边中间最多可间隔一个点，所以取最少边的做法是，如下图所示，从一头开始，取第2条边。然后，隔一个点取一条边，直到无边可取。这时，如果还剩2个点，则必须再取一条边，否则算法停止。经过简单分析可知，这个最佳解一共取了2k3条边，也就是2×2k3个顶点。因为2×2k34k3>11234最佳解是C={2,4,6,8}567891234近似算法Approx-Vertex-Cover最好解是C={2,3,5,6,8,9}56789证明算法Approx-Vertex-Cover选出的边的集合是一个局部最大(maximal)匹配。局部最大是指不能够再加一条边到这个集合中而仍能形成匹配。证明： 因为算法Approx-Vertex-Cover每选出一条边之后，这条边的两个顶点就从图里删去，后面选出的边不可能与这条边共顶点，所以所有选出的边都是两两不相交的，因此算法Approx-Vertex-Cover选出的边的集合是一个匹配。又因为这个集合中顶点形成一个顶点复盖，因此图里剩下的每条边必定与这个集合中某顶点关联，所以这个匹配不可能再扩大了。在证明图的顶点复盖问题是NPC问题时，我们把clique问题归约到图的顶点复盖问题，并证明图G(V,E)有一个k-clique当且仅当其补图G有一个(n-k)的顶点复盖，这里n=|V|。因为顶点复盖问题有近似度为2的多项式算法，那么，是否可以利用这个关系，使得clique问题也有近似度为常数的多项式算法呢？解： 虽然G(V,E)的最大clique对应G的最小顶点复盖，Clique问题不能由此得到近似度为常数的多项式算法。假设我们用顶点复盖的近似算法求图G(V,E)的团如下：构造G(V,E)的补图G。用近似度为2的顶点复盖算法求G的顶点复盖C。由C得到原图的clique=V–C。假设上面算法产生的顶点复盖C有|C|=k个顶点，而最小顶点复盖C*有k*<k个顶点，k/k*2。如果我们用顶点复盖C得到G中一个有(n-k)个顶点的clique，因为最大clique有n-k*个点，那么这个近似解有近似度(n-k*)/(n-k)=1+(k-k*)/(n-k)。这个比例不能保证小于某常数。如果k接近n，而且k约等于2k*，这个比例会趋向无穷大。我们看个例子。如果G是如下图(a)所示的有2m+1个顶点的图。如果我们用近似度为2的算法求顶点复盖，可能取m条垂直边，得到如图(a)所示的2m个点的顶点复盖C。如果用这个C在原图中找一个clique，我们得到只有一个顶点的clique，而G的最小顶点复盖，如图(b)所示，只需m个点，原图G的最大的clique有(m+1)个顶点。上述算法对这个例子得到的近似度是m+1112345678911121314近似算法Approx-Vertex-Cover最坏解是C={1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19}151617181910112345678911121314最小复盖是C*={1,3,5,7,9,12,14,16,18}151617181910某教授提出了下面这个求顶点复盖的启发式算法：找到图中一个有最大度数(degree)的顶点，把这个点选入顶点复盖，然后把这个点以及与该点关联的边从图中刪去。然后，不断重复这一过程直到图中不再有边为止。证明这个算法不能保证近似度2。(提示：构造一个二部图使左边的点在算法执行中不被删去，而右边的点逐步被刪去，并使右边的点的个数大于左边点的个数一倍。)解： 让我们构造一个二部图使左边的点在算法执行中不被删去，而右边的点逐步被刪去，并使右边的点的个数大于左边点的个数一倍。让我们构造一个具体例子加以说明。为简单起见，我们假定，如果两个顶点，分别在左右两边，并有相同的最大度数时，算法取右边的顶点。如下图(a)所示，先左右各构造6个点和6条不相交的边。对这个图而言，这个启发式算法会选取右边6个点。我们在(a)的基础上，在右边加上3个点得到图(b)，其中每个新加的点与左边两个点相连。这样一来，启发式算法需要刪去9个点了。再往下，在(b)的基础上，把左边6个点分为2组，每组3个点。然后在右边加上2个新的顶点，分别与左边两组中点相连得到图(c)。根据算法，对图(c)，我们需要刪去11个点。再往下，在(c)的基础上，我们在右边加一个点，并把它与左边的4个点相连得到图(d)。显然，算法会刪去图(d)中12个点。最后一步，我们在(d)的基础上在右边加一个点，并把它与左边的5个点相连得到图(e)。显然，算法会刪去图(e)中13个点。而最佳解是6个顶点，即左边6个顶点。因为13/6>2，所以这个算法不能保证近似度2。从构造过程看，这个算法不可能有常数倍的近似度。如果一开始左右各构造n个点和n条不相交的边，那么，我们在右边可以顺序加n2个点，n3个点，n4个点，…，nn个点。这导致这个启发式算法得到的顶点复盖的顶点个数是n+n2+n3+n4+…+nnnlnn。因为这个图的最小复盖只含左边(a)(a)(b)(c)(d)(e)考虑下面这个求货郎担回路的近似算法。我们假定完全图G(V,E)中边上的权满足三角不等式。算法从任一点rV开始。Closest-Point-TSP(G(V,E),r)Sr //S中顶点将顺序组成一个回路，开始时含一个点rwhileSV findedge(u,v)suchthatw(u,v)=min{w(u,v)|uS,vV-S} //找出集合S和V-S之间有最小权值的边(u,v)， SS{v}，并且把v插在u后面。endwhilereturnSEnd请证明算法Closest-Point-TSP是个近似度为2的算法。证明： 我们考虑回路S在插入一个点后总长会增加多少。算法循环开始前其总长W(S)=0。每当循环找到集合S和V-S之间最小权值的边(u,v)并把v插入时，总长会增加多少呢？当第一条边(u,v)=(r,v)被选取时，总权值是w(r,v)+w(v,r)=2w(r,v)。在以后的每一步中，假设在插入v之前，回路中顶点u后面的点是z，那么插入后总长增加的值应该是=w(u,v)+w(v,z)-w(u,z)。根据三角不等式，w(v,z)w(v,u)+w(u,z)，所以有=w(u,v)+w(v,z)-w(u,z)w(u,v)+[w(v,u)+w(u,z)]-w(u,z)=2w(u,v)。因此，当算法结束时，回路总长小于等于所有选取的边(u,v)的总权值的2倍。我们注意到，集合S和V-S形成顶点V的一个割，而且这个割不会切到前面已选中的边，所以算法找到的边的集合实际上组成了一个最小支撑树(MST)。所以，当算法结束时，回路总长小于等于最小支撑树的总权值的2倍。因为最小支撑树的总权值小于等于任一个货郎担回路的总权值，所以算法Closest-Point-TSP是个近似度为2的算法。这个算法可以这样理解:从点r开始，用Prim算法计算MST，每当边(u,v)被选入MST时，把v插入到S形成的回路中点u的后面。假设货郎担问题中的顶点是二维平面中的点，而每两点之间的边的权值就是这两点之间在二维平面中的直线距离(亦称欧基里得距离，或欧氏距离)。请证明，任何一条最小货郎担回路不会自身相交。证明： 我们用反证法证明。假设有一条最小货郎担回路自身相交于一点x，并假设相交于x的两条边是(a,b)和(u,v)。如下图(a)所示，这个回路可由4段路径组成，边(a,b)，路径b到u,边(u,v)，和路径v到a。那么，如图(b)所示，我们可以得到另外一个更小权值的货郎担回路如下：边(a,u)，路径u到b,边(b,v)，和路径v到a，这里路径u到b是把原路径b到u反向得到。这个回路有更小权值是因为：新回路的权值=原回路的权值+w(v,b)+w(a,u)–(w(u,v)+w(a,b))=原回路的权值+w(v,b)+w(a,u)–(w(u,x)+w(x,v)+w(a,x)+w(x,b))。但由于欧氏距离满足三角不等式，我们有w(v,b)w(v,x)+w(x,b) //如果相等，必有v=x，或b=x。w(a,u)w(a,x)+w(x,u) //如果相等，必有a=x，或u=x。显然，上面两个不等式不可能同时成为等式，否则，必有v=a，或u=b。这样的话，这个回路经过点a或点b两次，不可能是货郎担回路。因此，必有：新回路的权值<原回路的权值。这与原回路为最小货郎担回路矛盾。aabuv(a)xabuv(b)x定理15.4的一个弱化形式是|C||C*|max{|S||SF}。给出这一弱化形式的简单证明。证明： 假设最优解C*选中的集合为S1，S2，…，Sh*，这里h*=|C*|。再假设a1，a2，…，ah*是这些集合依次复盖新元素的个数。显然有a1+a2+…+ah*=m,这里m是F中所有集合所包含的不同元素的个数，即m=|SεFS|。设k=max{|S||SF}，因为aimax{|S||SF}=k，我们有m≤kh*。再看近似算法的解C。因为近似算法每选一个集合，该集合都会复盖至少一个新元素，所以|C|m。因此有|C|m≤kh*=k|C*|=|C*|max{|S||SF}。图G(V,E)的一个割(cut)就是一个顶点的划分(S,V-S)，即把V分为两个集合S和V-S。所有穿越边的集合称为这个割的边的集合，记为C(S,V-S)={(u,v)E|uS，vV–S}。假设图G(V,E)的边有正权值，C(S,V-S)中所有边的总权值称为这个割的权值，记为W(S,V-S)。图G(V,E)的最大割(MAX-CUT)问题就是找出有最大权值的割。考虑下面随机化的近似算法。Randomized-MAX-CUT(G(V,E)) S //S初始化为空集foreachvV vrandomnumber(0or1) //产生0或1的随机数，各占50%槪率 ifv=1 thenSS{v} endifendforreturrnSEnd请证明算法Randomized-MAX-CUT有随机近似度2。证明： 我们假定图G有n个顶点和m条边。每个顶点有1/2的概率被选入S。我们假定每个顶点的选择是独立的。因此，每条边(u,v)成为割的边的概率是：Prob(uS)Prob(vV-S)+Prob(vS)Prob(uV-S)=0.50.5+0.50.5=0.5。所以算法产生的割的权值的期望值是：E[W(S,V-S)]=(u,v)∈E=(u,v)∈E=0.5(u,v)∈E因为最佳解中割的总权值不会大于所有边的权值之和，所以算法的随机近似度是E((n,m))(u,v)∈Ewu,v/[0.5(u,v)∈E第14章习题16中讲到装箱问题(bin-packing)如下。假设有n个物体，O1,O2,…,On，需要装箱。这n个物体分别有体积si，并且满足0<si£1(1in)。假定每个箱子的容积是1，我们希望用最少的箱子把它们装入。我们假定任何一组物体，只要它们的总体积不超过1，都可以装入一个箱子之中。我们已在这个习题中证明了，这个问题的判断型问题是NP难问题。假设S=i=1nFirst-Fit(S[1..n]) //S[i](1in)代表物体Oi，也代表其体积sim1 //到目前为止已启用的箱子数C[1]1 //箱子1所余容积B[1] //箱子1已装物体的集合，开始是空的fori1ton //逐个检查物体S[i]，并决定放入哪个箱子 j1 //从箱子1顺序检查每个箱子 whileS[i]>C[j] //箱子j所余容积不够 jj+1 //顺序检查下一个箱子 endwhile ifj>m //已启用的箱子中没有一个可容纳S[i]，j=m+1 then mm+1 //开一个新箱子，现在m=j了 C[m]1 B[m] endif B[j]B[j]{S[i]} //把物体Oi放入箱子j中 C[j]C[j]–S[i] //更新箱子j的剩余容积endforreturnm,B[1..m] //用了m个箱子，B[1]到B[m]是各箱子中所装物体的集合End证明最佳解至少用S个箱子。证明算法First-Fit结束时，最多有一个箱子有大于或等于0.5的剩余容积，其它箱子所装物体总容积一定大于0.5。证明算法First-Fit是一个近似度2的近似算法。解：(a) 因为S=i=1nsi是所有物体的总容积，所用箱子的总容积必须大于或等于S。因为每个箱子的容积是1，所以至少要用用反证法证明。为此，假设有两个箱子Bi和Bj(1≤i<jm)在算法First-Fit结束时，有ci>0.5和cj>0.5。显然，B1到Bm各箱子中至少有一个物体，否则不会被启用。又假设最后放入箱子Bj中的物体是Ok，那么其容积必有sk<0.5，否则Bj的剩余容积不可能大于0.5。那么，根据算法，在把Ok放入Bj之前，算法一定先检查过箱子Bi。因为在算法First-Fit结束时，有ci>0.5，那么在算法为Ok检查箱子Bi时，也必定有ci>0.5。这时，根据算法，应该把Ok放入Bi中，而不应放入Bj中。这是一个矛盾。所以，算法First-Fit结束时，最多有一个箱子有大于或等于0.5的容积为空。由(a)知最佳解C*需要至少S个箱子，即|C*|S。由(b)知，算法First-Fit使用的箱子数m满足关系0.5(m-1)<S。所以有m<2S+12S+1。因为m是整数，所以有m2S。这也就是说，算法First-Fit的近似度是(n)2S/|C*|2S/S=2。在14章习题14中曾考虑过两个处理器调度问题。现在考虑m2个处理器的调度问题。我们把这个优化问题再叙述一遍。假设我们有n个独立的任务，J1，J2，...，Jn，要从时间t=0开始在m(2)个同样的处理器上执行(mn)。假设Ji(1in)需要Ti(>0)秒的时间完成并且一旦开始执行，必须不中断地在同一个处理器上运行直至完成。我们希望找到一个调度，即任务安排，使这n个任务可以在最短时间内完成，即从t=0开始到任务全部完成的时间跨度(makespan)最小。让我们用M1，M2，...，Mm表示这m个处理器。假设我们按以下方法顺序安排J1，J2，...，Jn：当我们安排Ji时(1in)，我们顺序检查处理器M1，M2，...，Mm，找到一个有最早空闲时刻的处理器Mk时，把Ji分配给它，并更新它的下一个空闲时刻。一开始，所有处理器的空闲时刻为0。请给出这个调度的伪码，并使之有复杂度O(nlgm)。证明上面的调度算法是近似度为2的多项式算法。解：(a) 为方便起见，我们用M[k]表示分配给处理器Mk的任务集合，用A[k]表示其下一个最早空闲时刻，即可用时刻。输出变量T是所有任务完成的时刻。Multiprocessor-Scheduling(M[1..m],J[1..n],T[1..n])fork1tom M[k] //开始时，各处理器任务为空集 A[k]0 //处理器Mk的初始可用时刻为0endfor //初始化完成H[1..m]A[1..m]Build-Min-Heap(H[1..m],1) //H是个最小堆，H[i]的关键字是它指向的A[i]fori1ton //逐个检查任务，并分配它一个处理器 ifH[1]=A[k] then M[k]M[k]{J[i]} //把任务J[i]分配给Mk A[k]A[k]+T[i] //更新Mk的可用时刻 Min-Heapify(H[1..m],1) //把堆修复 endifTA[1] //找出所有任务完成的时刻fork2tom ifA[k]>T thenTA[k] endifendforreturnT,M[1..m]End算法的主要部分是循环，一共n次，而每次的主要工作是堆的修复。因为堆的修复需要O(lgm)时间，因此算法的复杂度是O(nlgm)。(b) 现在证明上面的调度算法是近似度为2的多项式算法。我们注意到，分配给任一个处理器的任务会从t=0开始，一个接一个地被顺序执行，所以任一个处理器不会有中间停顿后再工作的情况。假设最后一个完成的任务是Ji(1in)它在时刻T完成。假设任务Ji被分配给处理器Mk。那么它在t’=T–Ti时刻开始执行Ji。我们可断定，在t=0到t=t’这段时间内，每个处理器都是在工作的，否则Ji应该会分配给更早结束任务的处理器。因此任何一个最优解需要至少t’时间完成所有任务。另外，任何最优解需要Ti时间完成任务Ji，因此最优解需要至少max(t’,Ti)时间完成所有任务。因为上面算法需要的时间是T=t’+Ti，所以有近似度(n,m)(t’+Ti)/max(t’,Ti)2。假设G(V,E)是一个无向图。对每个正整数k，我们可以定义一个新的图G(k)(V(k),E(k))，其中顶点集合V(k)是所有V中顶点的k元组，即V(k)={(v1,v2,...,vk)|viV，1ik}。注意，这里同一顶点可多次出现。集合V(k)中两点，(v1,v2,...,vk)和(w1,w2,...,wk)之间有边当且仅当vi=wi或者(vi,wi)E(1ik)。证明G(k)中最大团所含顶点数是G中最大团所含顶点数的k次方。证明，如果有近似度为常数的多项式算法求最大团，那么就有多项式机制求最大团。证明：(a) 如果G中最大团C所含顶点数是c，那么，由C中顶点组成的所有k元组之间必定有边，因此这些k元组组成G(k)中一个团。这样的k元组个数为ck，所以G(k)至少含有一个团，它所含顶点数是G中最大团所含顶点数的k次方。反之，如果G(k)有一个最大团C’，那么，把它的顶点的k元组中的k个顶点看为k个分量的话，团C’中每个分量中顶点必定组成G中一个团。因为C’是最大团，所以每个分量组成的团必定相等，否则不会最大。另外，这个由分量组成的G中团必定是G中最大的，否则，用G中最大的团作分量，可以得到G(k)中比C’更大的团。如果有近似度为常数1+c(c>0)的多项式算法A求最大团。我们可以有如下多项式机制求最大团。Max-Clique(G(V,E),)kc/构造G(k)(V(k),E(k))调用多项式算法A求G(k)最大团C’取C’中一分量中顶点集合CreturnCEnd我们证明C的近似度是1+。设最佳解为C*。根据(a)，G(k)的最大团有顶点|C*|k个。因为A的近似度为1+c，所以有|C*|k|C'|1+c。由(a)部分证明知，|C’|=|C|k，我们得到|C*|k|C|k1+c。因此Max-Clique有近似度|C*||C|(1+c)1/k。因为(1+)k>1+k=1+c/1+c，我们有(1+c)1/k1+。因此Max-Clique有近似度1+。另外，Max-Clique的时间复杂度可分析如下。设算法A有多项式时间P(n)=O(nh)。这里，n是图中顶点个数，h>0是多项式的阶。因为G(k)的顶点数|V(k)|=nk，算法中第2步和第3步的时间为T(n)=O(nkh)。因为k=c/<c/+1，T(n*如果在第10题中的m个处理器和n个任务的调度算法执行之前先把n个任务按所需时间递减排序，则可使其近似度更好。请证明如果有T1T2...Tn，那么这个算法有近似度43-13m。这个算法称为LPT(LongestProcessingTime)算法。(提示：假设最佳解需要总共t*时间，而近似算法产生的调度中最后一个完成的任务是Jk，其处理时间为Tk。讨论两种情形，Tkt*/3和Tk>t*/3证明： 假设最佳解需要总共t*时间，而近似算法产生的调度中最后一个完成的任务是Jk，其处理时间为Tk。因为序号大于k的任务不影响近似解的时间跨度，我们可以刪去不考虑。设近似解中Jk开始执行的时刻为sk，那么从t=0到t=sk，所有处理器都是在不停工作中，所以除Jk外的总工作量应大于msk，即mski=1kTi-Tk，也就是sk(i=1kTi)/m-Tk/m。因为任何解，包括最优解，其时间跨度必大于或等于(i=1kTi)/m，下面分两种情况：如果Tkt*/3，那么近似解的时间跨度是t=sk+Tk(t*-Tk/m)+Tk=t*+Tk(1-1/m)t*+t*/3-t*/3=4t*/3-t*/3m所以，近似度为(n,m)=t/t*4/3-1/3m。如果Tk>t*/3，那么在最优解里面，每个处理器只能承担一个或两个任务，这是因为最小的任务Tk>t*/3。进一步，存在一个最优解满足如下条件：如果一个处理器顺序执行两个任务，分别需时a和b，我们可假定先处理时间较长的，即ab。如果有一个处理器只执行一个任务，需时c，那么c比有两个任务的处理器中a和b都要大或相等，即cab，否则，可将a和c对调得更优解。如果一个处理器顺序执行两个任务，分别需时ab，而另一个处理器顺序执行两个任务，分别需时cd，并且有ac，那么，必有bd。否则把b和d对调后得更优解。不难看出，满足以上条件的最优解与近似算法产生的解相同，因此，如果Tk>t*/3，那么t/t*=14/3-1/3m。*重新考虑15.8.2节中任务均匀分配问题。我们把问题改一下，这次，我们不限定个人最多可分配的工作量，但要求一个人最少分到的工作量最大。这是个最大化问题。证明这个问题没有近似度小于2的多项式近似算法，除非P=NP。证明： 我们可以类似地证明。我们把3-SAT问题多项式鸿沟归约到这个最大化问题。这个任务均匀分配问题的构造与15.8.2节中完全一样。只不过，在这之上再加一步构造。我们以=(xyz)(xyz)(xyz)为例解释如何把3-SAT问题的一个实例多项式鸿沟归约到这个最大化的任务均匀分配问题的一个实例。第一步，构造与15.8.2节中完全一样的任务均匀分配问题。下面图(a)描述了对上面实例进行这一步多项式鸿沟归约后的实例。=(xyz)(xyz)(xyz)C3x1x2x2x1ax1ax2bx2bx11122y1y2y2y11122ay1ay2by2by1z1z2z2z11122az1az2bz2bz1C11C211(a)用二部图表示的部分构造好的任务分配问题在这一步构造中，如果变量x出现k次，则有k对任务(xi，xi)被构造(1ik)。假设一共有N对这样的任务，那么这样的任务一共有2N个。显然，如果每个变量x和它的非x出现相同次数，那么任务的个数2N就正好等于文字的个数，2N=3m，否则，2N>3m。这些任务中，N个有工作量2，N个有工作量1。加上为m个子句构造的任务C1，C2，…，Cm，任务总量是3N+m。在这一步中，我们还构造了2N个工人。第二步，为了使每个工人正好平均能分到工作量2，我们再加上4N-(3N+m)=N-m个任务，每个任务的工作量为1，并且使每个工人都能胜任这些新加的任务。如果用二部图来表示，这一步的构造是在代表任务这一侧加上p=N-m个任务顶点，每个顶点有权值1，并与另一侧代表工人的所有点相连。我们用1，2，…，p来表示这些任务或顶点。显然，上面的构造算法只需多项式时间。现在我们证明：这个3-SAT的实例可被满足当且仅当所构造的任务可分配给工人使每人工作量至少为2。如果这个3-SAT的实例不可被满足，那么无论怎样分配构造的任务，至少有一人工作量小于等于1。证明：(A) 先证明(1)。假设这个3-SAT的实例可被满足，我们可以这样分配任务：如果变量x=1，那么把任务xi分配给axi，把任务xi分配给bxi(1ik)。每个axi的工作量是1，而每个bxi的工作量是2(1ik)。反之，如果变量x=0(x=1)，那么把任务xi分配给axi，把任务xi+1分配给bxi(1ik-1)，然后把任务x1分配给bxk。这时，每个axi的工作量是2，而每个bxi的工作量是1(1ik)。总之，中赋值为另外，因为每一子句C中至少有一文字赋值为1，可把任务C分配给对应这一文字的工人，使其总工作量为2。因此，所有任务可分配完毕使得每人的工作量是1或2。因为有m个子句，所以有N+m个工人拿到2个工作量，有p=N-m个工人拿到1个工作量，我们可以把1，2，…，p分配给这p个人，使每人正好有工作量2。现在假设构造的任务可分配完毕使得每人的工作量至少为2，我们证明原3-SAT实例可满足。因为每人的工作量至少2，而总量是4N，所以每个人必须正好有工作量2。由图(a)知，在为变量x构造的2k个工人中，每人必须正好得到一个，除子句对应的任务外，的任务。这相当于书中图15-3中二部图的一个完美匹配。而且，从图15-3看出，为每个变量构造的图中，只有两种完美匹配，要么每个axi的工作量是1，而每个bxi的工作量是2(1ik)，或相反。如果每个axi的工作量是1，我们可以在中赋值x=1，否则为0。这个赋值可满足这个3-SAT实例，这是因为每个子句C对应的任务一定分配给了一个工人，他的工作量，除C外，在图15.3中是1。因为(B) 现在证明(2)。如果这个3-SAT的实例不可被满足，由上面证明可知，任何一种任务的分配中都会有至少一个工人的工作量小于2，否则每人的工作量必定为2。那么，由(1)得出，这个3-SAT的实例可被满足，从而矛盾。因为工作量必须是整数，那么必定有一个工人的工作量等于0或等于1。根据鸿沟定理，这个任务均匀分配问题不存在小于2近似度的多项式算法，除非P=NP。给定一个加权的连通图G(V,E)，最小-最大(min-max)2-树支撑森林的问题是找出一个2-树支撑森林，T1和T2，使得max{W(T1),W(T2)}在所有2-树支撑森林中是最小的。在第14章习题23中我们证明了最小-最大2-树支撑森林的问题是个NP难问题。请证明以下简单快捷的多项式算法是这个问题的一个近似度为2的近似算法。Min-Max-2-Tree-Spanning-Forest(G(V,E))用Kruskal或Prim算法计算G(V,E)的一个最小支撑树T找出T中有最大权值的边eFT–{e}returnFEnd(请注意，这个算法也是第9章习题14(a)中的算法。它产生的解不仅是本题的一个近似度为2的解，同时也是一个最小2-树支撑森林。)证明： 由第9章习题14(a)知，最小支撑数MST的权值等于最小2-树支撑森林F的权值加上最大边，即W(MST)=W(F)+w(最大边)=W(T1)+W(T2)+w(最大边)。这里的最大边指的是MST中的权值最大的边。假设最小-最大2-树支撑森林的最佳解是{T*1，T*2}。我们有如下关系：max{W(T1),W(T2)}W(T1)+W(T2)W(T*1)+W(T*2)2max{W(T*1),W(T*2)}。所以，算法Min-Max-2-Tree-Spanning-Forest是最小-最大2-树支撑森林问题的一个近似算法，并有近似度2。图G1(V1,E1)与图G2(V2,E2)的复合(composition)得到一个新的图G(V,E)，记为G=G1[G2]。其中V=V1V2，即V={(u,v)|uV1,vV2}。另外，V中两点(u1,v1)，(u2,v2)之间有边，当且仅当(u1,u2)E1或者(u1=u2并且有(v1,v2)E2)。注意，图G中顶点(u,v)是个无序对，(u,v)=(v,u)，但是图的复合有顺序，G1[G2]G2[G1]。下面是一个例子的图示。uu1u2v1v2v3G1G2G1[G2](u1,v1)(u1,v2)(u1,v3)(u2,v1)(u2,v2)(u2,v3)(u1,v1)(u1,v2)(u1,v3)(u2,v1)(u2,v2)(u2,v3)G2[G1]证明，如果图G1是一个有h个顶点的完全图，那么图G2可以k-着色，当且仅当图G1[G