計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第14章

PAGE32第14章 NP完全問題判斷以下各命題對(duì)與錯(cuò)。如果P1NP，那么就不存在多項(xiàng)式算法來判斷一個(gè)圖是否可以3著色。如果P1NP，那么就不存在多項(xiàng)式算法來判斷一個(gè)圖是否含有一個(gè)6-clique。如果P1NP，那么就不存在多項(xiàng)式算法來判斷一個(gè)圖是否有一個(gè)6-cover。如果問題A有多項(xiàng)式算法在(n3)時(shí)間內(nèi)被判定，而問題B在(n3)時(shí)間內(nèi)可歸約為問題A，那么問題B也就可以在(n3)時(shí)間內(nèi)被判定，這里的n指的都是問題的輸入規(guī)模。如果問題A有算法在(2n)時(shí)間內(nèi)被判定，而問題B在多項(xiàng)式時(shí)間內(nèi)可歸約為問題A，那么問題B也就可以在(2n)時(shí)間內(nèi)被判定解：(a)對(duì) (b)錯(cuò) (c)錯(cuò) (d)錯(cuò) (e)錯(cuò)。假設(shè)給你一個(gè)“寶盒子”P，它可以在常數(shù)時(shí)間內(nèi)正確判定一個(gè)有n個(gè)正整數(shù)的集合S是否可以被平分，但它不能給出實(shí)際的平分，它只可以被你的程序調(diào)用并輸出P(S)=1或P(S)=0。請(qǐng)?jiān)O(shè)計(jì)一個(gè)以P為子程序的多項(xiàng)式算法為一個(gè)可平分的集合S作出實(shí)際的平分。解：算法思路如下：設(shè)S={a1,a2,…,an}。如果集合S可被平分為集合A和S-A，那么我們可以用P來檢測a2是否可以與a1分在同一個(gè)集合。辦法是，我們把a(bǔ)1和a2從S中刪去，換之以一個(gè)數(shù)c，其值為(a1+a2)，即SS{c}–{a1,a2}。如果改動(dòng)后的集合S仍然有P(S)=1，則表明新的集合S可以平分，而新集合可以平分則表明原集合可以平分，并且a1和a2可以分在同一個(gè)集合。否則，如果有P(S)=0，則表明a1和a2不可以分在同一個(gè)集合，我們則恢復(fù)原集合。我們用這個(gè)辦法把所有可以與a1分在同一個(gè)集合的整數(shù)都找出來，平分完成。下面?zhèn)未a精確地表達(dá)了這個(gè)算法。Partition(S)ifP(S)=0 //P作為子程序被調(diào)用 thenreturn(Shasnopartition)endifA?{a1}c?a1S’?S{c}–{a1} //c=a1，在S中換一個(gè)符號(hào)而已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這顯然是個(gè)多項(xiàng)式算法。集合復(fù)蓋(set-cover)問題是這樣定義的：假設(shè)F={S1，S2，…，Sn}是含n個(gè)集合的一個(gè)家族(family)，這些集合的并集一共含有m個(gè)不同的元素，即?1≤i≤nSi={a1，a2，…，am}。家族中一部分集合的組合C稱為一個(gè)子家族。如果這m個(gè)元素中每個(gè)元素都出現(xiàn)在子家族C中的某個(gè)集合里，那么C稱為是F的一個(gè)復(fù)蓋，因?yàn)镃復(fù)蓋了F中所有元素，即?Si∈CSi={a1，a2，…，am}。如果C是F的一個(gè)復(fù)蓋并且所含集合數(shù)最少，則稱為一個(gè)最小復(fù)蓋。比如，F(xiàn)={S1，S2，S3}，這里S1={a,b},S2={b,c},S3={a,c,d}，S1èS2èS3={a,b,c,d}。因?yàn)镾1èS3={a,b,c,d}，所以C={S1，S3}就是一個(gè)F的集合復(fù)蓋。因?yàn)樵谶@個(gè)家族F中沒有一個(gè)集合能包含全部4個(gè)元素，所以子家族C={S1，S定義集合復(fù)蓋問題所對(duì)應(yīng)的一個(gè)判斷型問題。證明集合復(fù)蓋問題是NP難問題。解：(a)對(duì)應(yīng)的一個(gè)判斷性問題可定義如下：假設(shè)F={S1，S2，…，Sn}是含n個(gè)集合的一個(gè)家族(family)，這些集合的并集一共含有m個(gè)不同的元素，即?1≤i≤nSi={a1，a2，…，am}。對(duì)一個(gè)給定正整數(shù)k，判斷F中是否有一個(gè)k-復(fù)蓋，即含k證明集合復(fù)蓋問題是NP難問題。我們把頂點(diǎn)復(fù)蓋問題多項(xiàng)式歸約到集合復(fù)蓋問題。假設(shè)一個(gè)頂點(diǎn)復(fù)蓋問題的實(shí)例是圖G(V,E)和整數(shù)k。下面解釋如何由這個(gè)實(shí)例來構(gòu)造一個(gè)集合復(fù)蓋問題的實(shí)例。假設(shè)圖G(V,E)有m條邊，E={e1，e2，…，em}，那么，對(duì)應(yīng)G中每一條邊ei(1im)，我們構(gòu)造一個(gè)元素ai。然后，對(duì)應(yīng)G中每一個(gè)頂點(diǎn)vV，我們構(gòu)造一個(gè)集合Sv，而它所含元素就是與點(diǎn)v關(guān)聯(lián)的邊所對(duì)應(yīng)的元素，即Sv={ai|邊ei與v關(guān)聯(lián)，1im}。設(shè)|V|=n，那么這n個(gè)集合一起就組成了一個(gè)家族F，F(xiàn)={Sv|vV}。下面看一個(gè)例子。假設(shè)頂點(diǎn)復(fù)蓋問題的圖如下。 我們?yōu)?個(gè)頂點(diǎn)構(gòu)造6個(gè)集合如下： Sa={a1,a3,a4}，Sb={a2,a7,a8}，Sc={a3,a5,a7}，Sd={a4,a6,a8}，Se={a5,a6}，Sf={a1,a2}。這些集合組成了集合復(fù)蓋問題中的家族，F(xiàn)={Sa，Sb，Sc，Sd，Se，Sf}。下面我們證明圖G有一個(gè)k-復(fù)蓋當(dāng)且僅當(dāng)構(gòu)造的家族F有一個(gè)k-復(fù)蓋。根據(jù)我們的構(gòu)造，一條邊ei(1im)，與一個(gè)頂點(diǎn)v相關(guān)聯(lián)當(dāng)且僅當(dāng)元素ai屬于集合Sv。所以，S={v1,v2,…,vk}是G的一個(gè)k-復(fù)蓋當(dāng)且僅當(dāng)C={Sv1,Sv2,…,Svk}是F的一個(gè)k假設(shè)我們要舉行一個(gè)學(xué)術(shù)會(huì)議。會(huì)議有m個(gè)議題，T1，T2，…，Tm。對(duì)每一個(gè)議題Ti(1im)有一個(gè)可以審這方面稿件的教授的名單Pi。一個(gè)教授可能為幾個(gè)不同的議題審稿而出現(xiàn)在幾個(gè)名單中?，F(xiàn)在，我們希望從這些名單中選出一些教授來組成一個(gè)審稿委員會(huì)。我們希望委員會(huì)的人數(shù)越少越好，但是保證每一個(gè)議題都有能審稿的委員。請(qǐng)回答以下問題。定義與這個(gè)優(yōu)化型問題對(duì)應(yīng)的一個(gè)判斷型問題。證明這個(gè)判斷型問題屬于NP類。把圖的頂點(diǎn)復(fù)蓋問題多項(xiàng)式歸約到這個(gè)判斷型問題以證明其NP完全性。解：(a) 讓我們稱對(duì)應(yīng)的判斷型問題為審稿委員會(huì)問題。定義如下：假設(shè)我們要舉行一個(gè)學(xué)術(shù)會(huì)議。會(huì)議有m個(gè)議題，T1，T2，…，Tm。對(duì)每一個(gè)議題Ti(1im)有一個(gè)可以審這方面稿件的教授的名單Pi。一個(gè)教授可能為幾個(gè)不同的議題審稿而出現(xiàn)在幾個(gè)名單中。請(qǐng)判斷，能否從這些名單中選出k個(gè)教授來組成一個(gè)審稿委員會(huì)使得每個(gè)議題都至少有一個(gè)委員可以審稿？(b) 我們?yōu)樯厦娴呐袛嘈蛦栴}設(shè)計(jì)一個(gè)NP算法。在下面這個(gè)NP算法中，證書Y是選入委員會(huì)的教授名單。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) 假設(shè)圖G(V,E)和正整數(shù)k是頂點(diǎn)復(fù)蓋問題的一個(gè)實(shí)例，其中V={v1，v2，…，vn}，E={e1，e2，…，em}?，F(xiàn)在我們構(gòu)造一個(gè)審稿委員會(huì)問題的實(shí)例。首先，對(duì)應(yīng)G中每一條邊ei(1im)我們構(gòu)造一個(gè)議題Ti，而對(duì)應(yīng)G中每一個(gè)頂點(diǎn)uV，構(gòu)造一個(gè)教授u。然后，對(duì)每一議題Ti(1im)構(gòu)造一個(gè)可以審稿的教授名單Pi。這個(gè)名單由兩個(gè)教授組成，就是構(gòu)造Ti時(shí)所對(duì)應(yīng)的邊ei的兩個(gè)端點(diǎn)所對(duì)應(yīng)的教授。例如，ei=(u,v)，那么由頂點(diǎn)u和v所構(gòu)造的教授u和v組成Pi，Pi={u,v}。下面看一個(gè)例子。下面的圖是頂點(diǎn)復(fù)蓋的一個(gè)實(shí)例。由上面這個(gè)圖，我們構(gòu)造9個(gè)議題，分別對(duì)應(yīng)這9條邊：T={T1,T2,T3,T4,T5,T6,T7,T8,T9}。然后構(gòu)造5個(gè)教授，分別對(duì)應(yīng)5個(gè)頂點(diǎn):P={a,b,c,d,e}。接下來，為每個(gè)議題構(gòu)造一個(gè)審稿教授名單如下：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è)構(gòu)造算法顯然可以在多項(xiàng)式時(shí)間內(nèi)完成?，F(xiàn)在證明，原來圖G中有一個(gè)k-復(fù)蓋當(dāng)且僅當(dāng)所構(gòu)造的問題中有一個(gè)k人組成的審稿委員會(huì)使得每一個(gè)議題都能有至少一個(gè)可審這方面稿件的教授在委員會(huì)中。假設(shè)圖G中有一個(gè)k-復(fù)蓋，那么由這k個(gè)點(diǎn)對(duì)應(yīng)的k個(gè)教授組成的審稿委員會(huì)一定可以審任何一個(gè)議題的稿件。這是因?yàn)閳D中任何一條邊e都與這個(gè)復(fù)蓋中至少一個(gè)點(diǎn)v相關(guān)聯(lián)，那么對(duì)應(yīng)于e的議題可由對(duì)應(yīng)的教授v審稿，而且教授v在委員會(huì)中。所以任何一個(gè)議題都能有至少一個(gè)可審這方面稿件的教授在委員會(huì)中。假設(shè)所構(gòu)造的問題中有一個(gè)k個(gè)教授組成的審稿委員會(huì)使得每一個(gè)議題都能有至少一個(gè)可審這方面稿件的教授在委員會(huì)中。那么對(duì)應(yīng)于這k個(gè)教授的k個(gè)頂點(diǎn)一定是G的一個(gè)復(fù)蓋。這是因?yàn)閳DG的任一條邊e所對(duì)應(yīng)的議題可由委員會(huì)中一教授v審稿，那么邊e一定與對(duì)應(yīng)于教授v的頂點(diǎn)v相關(guān)聯(lián)而且頂點(diǎn)v被選入復(fù)蓋。所以對(duì)應(yīng)于這k個(gè)教授的k個(gè)頂點(diǎn)一定是G的一個(gè)復(fù)蓋。一個(gè)圖G=(V，E)的頂點(diǎn)子集SíV稱為一個(gè)獨(dú)立集(independentset)，如果E中任何一條邊只與S中最多一個(gè)點(diǎn)有關(guān)聯(lián)。也就是說，如果S中任意兩點(diǎn)之間沒有邊，那么它就是一個(gè)獨(dú)立集。最大獨(dú)立集問題就是要找出圖G的一個(gè)最大的獨(dú)立集。請(qǐng)回答以下問題。定義與這個(gè)優(yōu)化型問題對(duì)應(yīng)的一個(gè)判斷型問題。證明這個(gè)判斷型問題屬于NP類。證明這個(gè)判斷型問題是NP完全問題。解：(a)對(duì)應(yīng)的判斷型問題可定義如下：給定一個(gè)圖G(V，E)以及一個(gè)正整數(shù)k，判斷G是否有一個(gè)含k個(gè)頂點(diǎn)的獨(dú)立集。(b)下面是這個(gè)判斷型問題的一個(gè)NP算法，其中證書Y是k個(gè)頂點(diǎn)的集合。Independent-Set(G(V,E),k,Y)檢查Y中每個(gè)頂點(diǎn)v是否屬于V；檢查E中每條邊(u,v)的兩端點(diǎn)u或v是否至少有一個(gè)不屬于Y；檢查是否有|Y|=k；如果以上檢查都是對(duì)的話，輸出yes，否則no；End顯然這是一個(gè)多項(xiàng)式檢驗(yàn)算法。因?yàn)?b)部分已證明獨(dú)立集問題屬于NP類，我們只需證明它是NP難。我們把clique問題多項(xiàng)式歸約為這個(gè)問題。假設(shè)圖G(V,E)和整數(shù)k是一個(gè)clique問題的實(shí)例，我們構(gòu)造一個(gè)獨(dú)立集問題的實(shí)例如下：從圖G(V,E)我們構(gòu)造其補(bǔ)圖G。這個(gè)構(gòu)造顯然可在多項(xiàng)式時(shí)間內(nèi)完成。顯而易見，如果圖G(V,E)有一個(gè)含k個(gè)頂點(diǎn)的cliqueCV，那么在補(bǔ)圖G中這k個(gè)頂點(diǎn)必定形成一個(gè)獨(dú)立集。反之，如果在補(bǔ)圖G中有一個(gè)含k個(gè)點(diǎn)的獨(dú)立集C，那么在圖G(V,E)中，集合C的k個(gè)點(diǎn)必定形成一個(gè)k-clique。所以獨(dú)立集問題也是NPC問題。*一個(gè)圖G=(V，E)的頂點(diǎn)子集SíV稱為一個(gè)支配集(dominatingset)，如果任何一個(gè)頂點(diǎn)vV都與S中一個(gè)點(diǎn)相鄰。讓我們稱有k個(gè)頂點(diǎn)的支配集為k-支配集。最小支配集問題就是要找出圖G的一個(gè)有最少頂點(diǎn)的支配集。下面圖給出了一個(gè)例子。((a)頂點(diǎn)集合{a,b,c}是一個(gè)支配集但不是最小支配集aabcdefbcdef(b)頂點(diǎn)集合{c,d}是一個(gè)最小支配集請(qǐng)回答以下問題。(a) 定義與這個(gè)優(yōu)化型問題對(duì)應(yīng)的一個(gè)判斷型問題。(b) 證明這個(gè)判斷型問題屬于NP類。(c) 證明支配集問題是NP完全問題。(d) 假設(shè)有一個(gè)多項(xiàng)式算法A解決這個(gè)判斷型問題，請(qǐng)利用這個(gè)算法得到一個(gè)多項(xiàng)式算法來解決對(duì)應(yīng)的優(yōu)化型問題。解：(a) 對(duì)應(yīng)的判斷型問題可定義如下：給定一個(gè)圖G(V,E)以及一個(gè)正整數(shù)k，判斷G是否含有一個(gè)k-支配集。(b) 下面是這個(gè)判斷型問題的一個(gè)NP算法，其中證書Y是k個(gè)頂點(diǎn)的集合。Dominating-set(G(V,E),k,Y)檢查Y中每個(gè)頂點(diǎn)v是否屬于V；檢查V中每個(gè)頂點(diǎn)u是否與Y中某個(gè)頂點(diǎn)相鄰；檢查是否有|Y|=k；如果以上檢查都是對(duì)的話，輸出yes，否則輸出no；End顯然這是一個(gè)多項(xiàng)式檢驗(yàn)算法。(c) 由問題(b)可知k-支配集問題屬于NP類，我們只需證明其NP難。我們把頂點(diǎn)復(fù)蓋問題多項(xiàng)式歸約到k-支配集問題。假設(shè)圖G(V,E)和正整數(shù)k是頂點(diǎn)復(fù)蓋問題的一個(gè)實(shí)例，其中V={v1,v2,…,vn}，E={e1,e2,…,em}。下面是由此構(gòu)造一個(gè)支配集問題實(shí)例的算法。首先，構(gòu)造一個(gè)二部圖G’(U’,V’,E’),這里U’=V={v1，v2，…，vn}，V’={e1，e2，…，em}，也就是說，對(duì)應(yīng)G中每個(gè)頂點(diǎn)和每條邊構(gòu)造G’的一個(gè)頂點(diǎn)。邊的集合E’由兩部分組成。第1部分是E’1={(u,v)|u,vU’，uv}，也就是說，U’中點(diǎn)形成一個(gè)完全圖。第2部分是E’2={(vi,ej)|viU’，ejV’，vi在G中是ej的端點(diǎn)}。下面的圖(a)(b)給出了一個(gè)這樣轉(zhuǎn)換的實(shí)例。((b)圖G’abcde(a)圖Ge1e2e3e4e5e6abcdee1e2e3e4e5e6U’V’顯然，這個(gè)轉(zhuǎn)換算法只需多項(xiàng)式時(shí)間?，F(xiàn)在證明，圖G有一個(gè)k-復(fù)蓋當(dāng)且僅當(dāng)G’有個(gè)k-支配集，kn。假設(shè)G有一個(gè)k-復(fù)蓋。那么這k個(gè)頂點(diǎn)所對(duì)應(yīng)的U’中的k個(gè)頂點(diǎn)是G’的一個(gè)支配集。這是因?yàn)镚中每一條邊都與這k-復(fù)蓋中某個(gè)點(diǎn)關(guān)聯(lián)，所以在G’中V’的每一個(gè)頂點(diǎn)都與U’中的這k個(gè)頂點(diǎn)中某個(gè)點(diǎn)相鄰。再因?yàn)閁’中的n個(gè)點(diǎn)形成一個(gè)完全圖，因此U’中的每個(gè)點(diǎn)都與這k個(gè)頂點(diǎn)的任何一個(gè)相鄰。因此，這k個(gè)頂點(diǎn)是G’的一個(gè)支配集。假設(shè)G’有一個(gè)k-支配集D(kn)，那么G一定有一個(gè)k-復(fù)蓋。這里要說明一點(diǎn)，如果G’有一個(gè)k-支配集，而且k>n，那么一定不會(huì)是最小支配集，因?yàn)閁’中n個(gè)頂點(diǎn)就是一個(gè)支配集，所以可假設(shè)kn。再有，我們可假設(shè)這個(gè)k-支配集中不含V’中點(diǎn)。這是因?yàn)槿绻旤c(diǎn)vV’屬于這個(gè)k-支配集，而頂點(diǎn)uU’與v相鄰，那么把v換為u后，DD{u}–{v}，D仍是一個(gè)k-支配集。(如果u也在k-支配集中，則得到一個(gè)(k-1)-支配集。)總之，如果G’有一個(gè)k-支配集，可假定這k個(gè)頂點(diǎn)都在U’中。顯然，這k個(gè)頂點(diǎn)所對(duì)應(yīng)的G中的k個(gè)點(diǎn)是G中的一個(gè)k-復(fù)蓋，證畢。我們假定有一個(gè)多項(xiàng)式算法A解決這個(gè)判斷型問題，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。我們先確定最小支配集中頂點(diǎn)個(gè)數(shù)k。然后，逐個(gè)檢查集合V中每個(gè)頂點(diǎn)v，并從中選取最小支配集的k個(gè)頂點(diǎn)。一開始，最小支配集D為空，而等待檢查的頂點(diǎn)集合是W=V。如果點(diǎn)v被選上，則把它放在集合D里。檢查過的點(diǎn)從W中刪除。檢查頂點(diǎn)v的步驟如下：在當(dāng)前的圖G(V,E)中，把點(diǎn)v以及它相鄰的點(diǎn)Adj(v)刪除后，如果余下的圖G*有(k-1)個(gè)點(diǎn)的支配集，那么選取點(diǎn)v，DD{v}，更新W為WW–{v}–Adj(v)。下一步的工作是在W中找修改后的圖G*的一個(gè)(k-1)-支配集。如果第(1)步中余下的圖G*沒有(k-1)-支配集，那么恢復(fù)當(dāng)前圖G(V,E)。這不表明點(diǎn)v就一定不屬于k-支配集，但表明圖G的k-支配集一定含有Adj(v)中的點(diǎn)。所以，我們重新構(gòu)造G*。我們把點(diǎn)v從圖G中刪除，然后，如果需要，添加一些邊使得Adj(v)中的點(diǎn)組成一個(gè)完全圖。如果這樣修改后的圖G*有一個(gè)(k-1)-支配集，那么這個(gè)(k-1)-支配集加上點(diǎn)v就是圖G的k-支配集。這是因?yàn)?，這(k-1)-支配集支配Adj(v)以外的所有點(diǎn)，而點(diǎn)v支配Adj(v)中的點(diǎn)。因此，這種情況下，我們選取點(diǎn)v，DD{v}，更新W為WW–{v}。下一步的工作是在W中找修改后的圖G*的一個(gè)(k-1)-支配集。如果第(2)步中修改后的圖G*也沒有(k-1)-支配集。這說明不可選取點(diǎn)v。這種情況下，恢復(fù)當(dāng)前圖G(V,E)，不更新D，但更新W為WW–{v}。這個(gè)多項(xiàng)式算法的偽碼如下。Minimum-Dominating-Set(G(V,E),k)k?1whileA(G(V,E),k）=no k?k+1 //k是最小支配集中頂點(diǎn)數(shù)endwhileD? //支配集開始為空WV //W是可能被選為支配集中點(diǎn)while|D|≠k extractavertexvfromW //從W取一點(diǎn)v V*?V-Adj(v) -{v} //V不變，構(gòu)造V* E*?{(x,y)E|x?V*andy?V*} //V*中頂點(diǎn)之間的邊，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)中點(diǎn) E*E–{(v,y)|y?Adj(v)} //刪除與v關(guān)聯(lián)的邊 E*?E*è{(x,y)|x,y?Adj(v)} //把Adj(v)補(bǔ)為完全圖 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經(jīng)過圖中每個(gè)點(diǎn)恰好一次，那么路徑P稱為一條哈密爾頓路徑。判斷圖G=(V,E)是否有一條哈密爾頓路徑稱為哈密爾頓路徑問題。證明哈密爾頓路徑問題是個(gè)NP難問題。解：我們把哈密爾頓回路問題多項(xiàng)式歸約為哈密爾頓路徑問題。假設(shè)G(V,E)是哈密爾頓回路問題的一個(gè)實(shí)例。在多項(xiàng)式時(shí)間內(nèi)，我們由G(V,E)構(gòu)造一個(gè)哈密爾頓路徑問題的實(shí)例，也就是圖G’(V’,E’)。不失一般性，可假設(shè)G至少有3個(gè)頂點(diǎn)，否則G最多有兩個(gè)點(diǎn)，不可能有回路。這個(gè)構(gòu)造算法的步驟如下：G’(V’,E’)G(V,E)； //先復(fù)制圖G在G中選取一個(gè)頂點(diǎn)a；在G’中加一頂點(diǎn)w和邊(w,a)；在G’中再加上兩頂點(diǎn)x和y，以及邊(x,y)；如果在G中有邊(a,v)，則在G’中加上邊(v,x)。這樣構(gòu)造的圖G’(V’,E’)中，V’=Vè{w,x,y},E’=Eè{(w,a),(x,y)}è{(v,x)|v?Adj(a)}。下面的圖給出了一個(gè)上面構(gòu)造算法的一個(gè)例子。顯然，這是一個(gè)多項(xiàng)式時(shí)間的構(gòu)造算法。aadecbaadecbaw乙xy(a)圖G(b)圖G’現(xiàn)在，我們證明圖G有一條哈密爾頓回路當(dāng)且僅當(dāng)圖G’有一條哈密爾頓路徑。假設(shè)G有一條哈密爾頓回路C，其頂點(diǎn)序列從a開始為<a,u,…,v,a>。那么在圖G’中有一條哈密爾頓路徑P，其頂點(diǎn)序列為<w,a,u,…,v,x,y>。也就是說，P從w到a，然后沿著哈密爾頓回路C走到頂點(diǎn)v。這時(shí)，P不走回到a，而是折向x后終止于y。假設(shè)圖G’中有一條哈密爾頓路徑P，那么P必須以頂點(diǎn)w和點(diǎn)y為起始點(diǎn)?？杉僭O(shè)P的頂點(diǎn)序列為<w,a,u,…,v,x,y>。那么我們可以得到G的一條哈密爾頓回路C，其頂點(diǎn)序列為<a,u,…,v,a>，證畢。假設(shè)在一個(gè)城市里有m個(gè)家庭有小孩要上學(xué)，同時(shí)有n個(gè)學(xué)?？梢员ＷC每個(gè)家庭在150米之內(nèi)至少有一個(gè)學(xué)校。假設(shè)這m個(gè)家庭編號(hào)為Hi(1im)，這n個(gè)學(xué)校編號(hào)為Sj(1jn)?，F(xiàn)在由于經(jīng)費(fèi)短缺，需要關(guān)閉一些學(xué)校以節(jié)省開支，但仍然保證每個(gè)家庭在200米之內(nèi)至少有一個(gè)學(xué)校可以上。經(jīng)過調(diào)查，我們?yōu)槊總€(gè)學(xué)校Sj(1jn)列出在它200米內(nèi)所有家庭的編號(hào)，即Pj={Hi|1im，Hi與Sj相距不超過200米}。一個(gè)優(yōu)化問題是，我們希望在保證每個(gè)家庭有一個(gè)學(xué)校在200米內(nèi)的基礎(chǔ)上，關(guān)閉最多的學(xué)校。請(qǐng)為上述優(yōu)化問題定義一個(gè)對(duì)應(yīng)的判斷型問題。證明該判斷型問題屬于NP類。證明該判斷型問題是NP難問題。解:(a) 對(duì)應(yīng)的判斷型問題可表述為：假設(shè)在一個(gè)城市里有m個(gè)家庭有小孩要上學(xué)，同時(shí)有n個(gè)學(xué)校。假設(shè)這m個(gè)家庭編號(hào)為Hi(1im)，這n個(gè)學(xué)校編號(hào)為Sj(1jn)。經(jīng)過調(diào)查，我們?yōu)槊總€(gè)學(xué)校Sj(1jn)列出在它200米內(nèi)所有家庭的編號(hào)，即Pj={Hi|1im，Hi與Sj相距不超過200米}。請(qǐng)判斷我們是否可以關(guān)閉k個(gè)學(xué)校但仍保證每個(gè)家庭有一個(gè)在200米內(nèi)的學(xué)校不被關(guān)閉。這里，k是一個(gè)正整數(shù)。(b) 我們?yōu)榇嗽O(shè)計(jì)如下的一個(gè)多項(xiàng)式檢驗(yàn)算法。其中，Y是一個(gè)含k個(gè)不同學(xué)校的證書。因此，該判斷型問題屬于NP類。Close-Schools(H[1..m],S[1..n],P[1..n],k,Y)if|Y|k thenreturnnoendifforeachyY //Y中元素必須是n個(gè)學(xué)校之一 forj1ton if(S[j]=nil)or(S[j]y) //S[j]=nil表示該校被關(guān)閉 thenjj+1 ifj>n thenreturnno //y不是學(xué)?；蛑貜?fù)出現(xiàn)于Y endif elseS[j]nil //S[j]=y，該校被關(guān)閉 endif endforendforH //統(tǒng)計(jì)與余下學(xué)校200米距離內(nèi)的所有家庭的集合forj1ton ifS[j]nil thenHHP[j] endifendforfori1tom ifH[i]H thenreturnno endifendforreturnyesEnd(c) 我們把頂點(diǎn)復(fù)蓋問題多項(xiàng)式歸約到這個(gè)問題。假設(shè)圖G(V,E)和正整數(shù)k是頂點(diǎn)復(fù)蓋問題的一個(gè)實(shí)例，其中V={v1,v2,…,vn}，E={e1,e2,…,em}?，F(xiàn)在我們構(gòu)造一個(gè)關(guān)閉學(xué)校問題如下：(1) 為每一個(gè)頂點(diǎn)vj(1jn)構(gòu)造一個(gè)學(xué)校Sj。(2) 為每一條邊ei(1im)構(gòu)造一個(gè)家庭Hi。(3) 為每一個(gè)學(xué)校Sj(1jn)構(gòu)造與其距離小于等于200米的家庭的集合Pj：Pj={Hi|邊ei與點(diǎn)vj關(guān)聯(lián)}。也就是說，如果邊ei與頂點(diǎn)vj關(guān)聯(lián)，那么，由邊ei構(gòu)造的家庭Hi與由頂點(diǎn)vj構(gòu)造的學(xué)校Sj相距小于等于200米。(4) 置k’n-k。 例如，下面的圖是找k-復(fù)蓋的一個(gè)實(shí)例。我們把它轉(zhuǎn)換為學(xué)校關(guān)閉問題的一個(gè)實(shí)例如下：學(xué)校集合為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}。顯然，圖中頂點(diǎn)u復(fù)蓋邊e(即e與u關(guān)聯(lián))當(dāng)且僅當(dāng)u對(duì)應(yīng)的學(xué)校距離e對(duì)應(yīng)的家庭相距小于等于200米。如果圖G(V,E)有個(gè)k-復(fù)蓋，使得任一條邊e關(guān)聯(lián)于這k個(gè)頂點(diǎn)中某個(gè)頂點(diǎn)u，那么由e構(gòu)造的家庭與由點(diǎn)u構(gòu)造的學(xué)校就相距小于等于200米。所以，保留由這k-復(fù)蓋中的k個(gè)頂點(diǎn)構(gòu)造的學(xué)校就可保證每個(gè)家庭與其中一個(gè)學(xué)校相距小于等于200米。這也就是說，我們可以關(guān)閉k’(=n-k)個(gè)學(xué)校。反之，如果我們可以關(guān)閉k’(=n-k)個(gè)學(xué)校，使每個(gè)家庭H與某個(gè)不關(guān)閉的k個(gè)學(xué)校之一，學(xué)校s，相距小于等于200米，那么對(duì)應(yīng)這個(gè)家庭H的邊e就關(guān)聯(lián)于對(duì)應(yīng)這個(gè)學(xué)校s的頂點(diǎn)u。所以，對(duì)應(yīng)這不關(guān)閉的k個(gè)學(xué)校的k個(gè)頂點(diǎn)就是圖G(V,E)的一個(gè)k-復(fù)蓋。所以，圖G(V,E)有k-復(fù)蓋，當(dāng)且僅當(dāng)構(gòu)造的學(xué)校問題可以關(guān)閉k’(=n-k)個(gè)學(xué)校。因?yàn)樯鲜鲛D(zhuǎn)換顯然只需多項(xiàng)式時(shí)間，所以學(xué)校關(guān)閉問題是個(gè)NP難問題。前面習(xí)題7中討論的哈密爾頓路徑問題，以及哈密爾頓回路問題都假定給定的圖G=(V,E)是個(gè)無向圖。請(qǐng)解釋為什么在有向圖中找哈密爾頓路徑或回路也是NP完全問題。解：我們總可以把一無向圖G(V,E)的哈密爾頓路徑或回路問題多項(xiàng)式轉(zhuǎn)換為有向圖的哈密爾頓路徑或回路問題。我們只要把無向圖中每一條邊(u,v)換為一對(duì)有向邊(u,v)和(v,u)。這樣一來，無向圖G(V,E)中有一條哈密爾頓路徑或回路當(dāng)且僅當(dāng)對(duì)應(yīng)的有向圖中有一條哈密爾頓路徑或回路。所以，有向圖中找哈密爾頓路徑或回路也是NP完全問題。給定圖G(V,E)，最長路徑問題就是找一條最長的簡單路徑，也就是找一條路徑P使得所含邊數(shù)最多并且路徑上每個(gè)頂點(diǎn)最多經(jīng)過一次。這里，路徑的起點(diǎn)和終點(diǎn)可任取。請(qǐng)為這個(gè)優(yōu)化型問題定義一個(gè)相應(yīng)的判斷型問題并證明其NP難。解：對(duì)應(yīng)的判斷型問題可定義如下：給定圖G(V,E)和正整數(shù)k，判斷G是否有一條長度至少為k的簡單路徑。我們可以把哈密爾頓路徑問題多項(xiàng)式歸約為這個(gè)問題。假定圖G=(V,E)是哈密爾頓回路問題的實(shí)例，其中|V|=n。我們把它轉(zhuǎn)換為最長路徑問題時(shí)仍用同一個(gè)圖G，但置k=n-1，那么顯然可見，圖G(V,E)有一條哈密爾頓路徑當(dāng)且僅當(dāng)圖G有一條長度至少為n-1的簡單路徑。因此，最長路徑問題是個(gè)NP難問題。在第10章的討論中，我們知道如果一個(gè)加權(quán)的有向圖中含有一個(gè)負(fù)回路，那么Bellman-Ford算法和Dijkstra算法都不能找到兩個(gè)給定頂點(diǎn)間的最短簡單路徑。實(shí)際上，如果圖中邊的權(quán)限制為正整數(shù)或負(fù)整數(shù)，那么找兩個(gè)給定頂點(diǎn)間的最短(簡單)路徑問題也是個(gè)NP難問題。請(qǐng)為這個(gè)優(yōu)化型問題定義一個(gè)對(duì)應(yīng)的判斷型問題并證明它是NP難問題。解：對(duì)應(yīng)的判斷型問題可定義如下：給定一個(gè)加權(quán)有向圖G(V,E)，其中每條邊上的權(quán)可以是一個(gè)正整數(shù)或一個(gè)負(fù)整數(shù)。另外，給定V中兩個(gè)頂點(diǎn)s和t，以及一個(gè)整數(shù)k(可正可負(fù))，判斷G是否有一條從s到t的簡單路徑P使得P的總權(quán)值小于等于k。我們把有向圖的哈密爾頓回路問題多項(xiàng)式歸約為這個(gè)最短路徑問題。假設(shè)簡單有向圖G(V,E)是哈密爾頓回路問題的一個(gè)實(shí)例。我們由G(V,E)構(gòu)造一個(gè)最短路徑問題的實(shí)例G’(V’,E’)。不失一般性，可假設(shè)V至少有3個(gè)頂點(diǎn)，否則不可能有回路。我們構(gòu)造圖G’(V’,E’)如下：G’(V’,E’)G(V,E)。 //復(fù)制圖G在V’中選取一個(gè)頂點(diǎn)a。在V’中加一頂點(diǎn)w和有向邊(w,a)。在V’中再加上兩頂點(diǎn)x和y，以及有向邊(x,y)。如果在E中有邊(v,a)，則在E’中加上邊(v,x)。構(gòu)造的圖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)。下面的圖給出了一個(gè)上面構(gòu)造算法的一個(gè)例子。顯然，這是一個(gè)多項(xiàng)式時(shí)間的構(gòu)造算法。aadecbaadecbaw乙xy(a)圖G(b)圖G’-1-1-1-1-1-1-1-1-1-1-1-1現(xiàn)在，我們證明圖G有一條哈密爾頓回路當(dāng)且僅當(dāng)G’有一條總權(quán)值小于等于k的從點(diǎn)w到點(diǎn)y的路徑。假設(shè)G有一條哈密爾頓回路C，設(shè)其頂點(diǎn)序列從a開始為<a,u,…,v,a>。那么在圖G’中有一條從點(diǎn)w到點(diǎn)y的路徑P，其頂點(diǎn)序列為<w,a,u,…,v,x,y>。也就是說，P從w到a，然后沿著哈密爾頓回路C走到頂點(diǎn)v。這時(shí)，P不走回到a，而是折向x后終止于y。顯然。路徑P的總權(quán)值是k=-(n+2)。假設(shè)圖G’中有一條總權(quán)值小于等于k的從點(diǎn)w到點(diǎn)y的路徑P。那么，路徑P的頂點(diǎn)序列必定是為<w,a,u,…,v,x,y>。又因?yàn)閨P|k=-(n+2)，它必須含有至少(n+2)條邊。所以它的子路徑<a,u,…,v>必定含有至少(n-1)條邊，那么，加上邊(v,a)后，就得到圖G的密爾頓回路C=<a,u,…,v,a>。所以，由本題可見，即使權(quán)值是整數(shù)，有負(fù)回路的圖的最短路徑問題是個(gè)NP難問題。假設(shè)一個(gè)連通圖G(V,E)的每一條邊有一個(gè)非負(fù)整數(shù)的權(quán)，我們希望判斷是否可以找到一個(gè)支撐樹使得樹中所有邊的權(quán)之和正好是k。請(qǐng)證明這個(gè)問題是個(gè)NP難問題。解：我們把子集和問題多項(xiàng)式歸約為這個(gè)支撐樹問題。假定一個(gè)子集和問題的實(shí)例是含n個(gè)正整數(shù)的集合S={a1,a2,…,an}和目標(biāo)值t。我們由此構(gòu)造一個(gè)支撐樹問題的一個(gè)實(shí)例。步驟如下：對(duì)應(yīng)每個(gè)整數(shù)ai(1￡i￡n)，構(gòu)造一個(gè)三角形，(xi,yi,zi)，并且賦以權(quán)值w(xi,yi)=w(yi,zi)=0，w(zi,xi)=ai。在頂點(diǎn)xi和xi+1之間聯(lián)一條邊并賦以權(quán)值w(xi,xi+1)=0(1￡i￡n-1)。置k=t。下面的圖顯示了這樣構(gòu)造的圖。顯然這個(gè)構(gòu)造只需多項(xiàng)式時(shí)間?，F(xiàn)在證明，集合S有子集和為t當(dāng)且僅當(dāng)所構(gòu)造圖有一棵支撐樹，其總權(quán)值為k。假設(shè)S有子集AíS使得ai∈Aai=t。那么，如果aiA，我們?cè)趫D中對(duì)應(yīng)于ai的三角形(xi,yi,zi)中把邊(xi,yi)刪去，否則把(xi,zi)刪去。這樣得到的一棵支撐樹的總權(quán)值顯然等于ai∈A如果所構(gòu)造的圖有一棵支撐樹T，它的總權(quán)值等于k，那么在圖中對(duì)應(yīng)于ai的三角形(xi,yi,zi)中必定有兩條邊屬于T而第3條邊被刪去。從圖的構(gòu)造可知，T的總權(quán)值=(zi,xi)∈Tw(zi,xi)=k。我們可以這樣構(gòu)造集合A：如果邊(zi,xi)屬于T，我們則把a(bǔ)i選入集合A，否則不把a(bǔ)i選入集合A。這樣一來，ai∈Aai=(zi,xi)∈Ta由上面討論可知，本題中的問題是個(gè)NP難問題。給定一個(gè)連通圖G(V,E)，我們希望找到一個(gè)支撐樹使得樹中的葉結(jié)點(diǎn)最少。例如，下面圖(ii)和(iii)都是圖(i)的支撐樹，分別有4個(gè)葉結(jié)點(diǎn)和3個(gè)葉結(jié)點(diǎn)，圖(iii)的解較好。請(qǐng)回答以下問題：為本題的優(yōu)化型問題定義一個(gè)對(duì)應(yīng)的判斷型問題。證明這個(gè)問題是NPC問題。aabcdefg(iii)abcdefg(i)abcdefg(ii)解：(a) 對(duì)應(yīng)的判斷型問題可定義如下： 給定一個(gè)連通圖G(V,E)和一個(gè)正整數(shù)k，判斷G是否含有一個(gè)葉子數(shù)少于等于k的支撐樹。(b) 為證明這個(gè)問題是NPC，我們先證明它屬于NP類。我們用的證書是一棵支撐樹的邊的集合Y。下面的偽碼檢驗(yàn)Y是否是葉子數(shù)少于等于k的支撐樹。Verification-k-Leave-Spanning-Tree(G(V,E),k,Y) //|V|=nV’?V //開始構(gòu)造這個(gè)支撐樹T=G’(V’,E’)foreachvV’ //開始時(shí)，這個(gè)支撐樹G’(V’,E’)沒有邊 Adj(v) deg(v)0 //頂點(diǎn)v的度endforE’?foreachedge(u,v)?Y if(u,v)?E thenreturnno else EE–{(u,v)} //避免下次重復(fù) 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’ //取一頂點(diǎn)sBFS(G’(V’,E’),s) //從s開始作一輪廣度優(yōu)先搜索number-of-leaves?0 //統(tǒng)計(jì)葉子個(gè)數(shù)foreachvinV’ ifcolor(v)=White thenreturnno //存在未訪問的白點(diǎn)，G(V’,E’)不可能是支撐樹 else ifdeg(v)=1 //v是個(gè)葉子 thennumber-of-leaves?number-of-leaves+1 endif endifendfor //G(V’,E’)連通且有n-1條，是支撐樹ifnumber-of-leavesk thenreturnyes elsereturnnoendifEnd現(xiàn)在證明這個(gè)問題是NP難。我們把哈密爾頓路徑問題多項(xiàng)式歸約為這個(gè)問題。假定圖G是哈密爾頓路徑問題的一個(gè)實(shí)例。當(dāng)我們把哈密爾頓路徑問題多項(xiàng)式歸約到支撐樹時(shí)，仍用這個(gè)圖G并置k=2。顯然，圖G有一條哈密爾頓路徑當(dāng)且僅當(dāng)圖G有一個(gè)2個(gè)葉子的支撐樹。所以本題中的問題是NP完全問題。假設(shè)我們有n個(gè)獨(dú)立的任務(wù)，J1,J2,...,Jn，要從時(shí)間t=0開始在兩個(gè)同樣的處理器上執(zhí)行。假設(shè)Ji(1in)需要Ti秒的時(shí)間完成并且一旦開始執(zhí)行，必須不中斷地在同一個(gè)處理器上運(yùn)行直止完成。我們希望找到一個(gè)調(diào)度，即任務(wù)安排，使這n個(gè)任務(wù)可以在最短時(shí)間內(nèi)完成。例如，如果有3個(gè)任務(wù)，其執(zhí)行時(shí)間分別為T1=4秒,T2=5秒,T3=7秒,那么下面圖示的調(diào)度用9秒鐘可以把它們完成。這個(gè)調(diào)度顯然是最好的。請(qǐng)回答下面問題。TT1T2T3處理器1處理器2t=0213456879(a) 為上述調(diào)度問題定義一個(gè)對(duì)應(yīng)的判斷型問題。(b) 證明該調(diào)度問題是個(gè)NP難問題。解：(a) 對(duì)應(yīng)的判斷型問題可定義如下：假設(shè)我們有n個(gè)獨(dú)立的任務(wù)，J1,J2,...,Jn，要從時(shí)間t=0開始在兩個(gè)同樣的處理器上執(zhí)行。假設(shè)Ji(1in)需要Ti秒的時(shí)間完成并且一旦開始執(zhí)行，必須不中斷地在同一個(gè)處理器上運(yùn)行直至完成。判斷是否存在一個(gè)調(diào)度使這n個(gè)任務(wù)可以在k秒內(nèi)完成。(b) 我們把集合平分問題多項(xiàng)式歸約為這個(gè)問題。假設(shè)集合平分問題的一個(gè)實(shí)例中，S={a1,a2,…,an}是n個(gè)正整數(shù)，其和為i=1nai=2m。我們由此構(gòu)造一個(gè)調(diào)度問題的實(shí)例如下。我們?yōu)槊總€(gè)整數(shù)ai構(gòu)造一個(gè)對(duì)應(yīng)的獨(dú)立任務(wù)Ji，并置它的執(zhí)行時(shí)間為Ti=ai(1≤i≤n)。另外，置k=m我們用P1和P2分別表示調(diào)度問題中的兩個(gè)處理器，也表示調(diào)度給它們執(zhí)行的任務(wù)的集合。下面我們證明，如上構(gòu)造的n個(gè)任務(wù)，J1,J2,...,Jn，可以在P1和P2上在k秒內(nèi)完成當(dāng)且僅當(dāng)這個(gè)集合S可被平分。假設(shè)集合S可被平分，即存在子集AS使得ai∈Aai=ai∈S-Aai=m。那么，我們可設(shè)計(jì)任務(wù)調(diào)度如下：我們把對(duì)應(yīng)于集合A中整數(shù)的任務(wù)分配給P1，而把對(duì)應(yīng)于集合S-A中整數(shù)的任務(wù)分配給P2，即P1={Ji|aiA(1≤i≤n)}，P2={Ji|aiS–A(1≤i≤n)}。在各處理器中的任務(wù)從t=0開始一個(gè)接一個(gè)順序完成。這樣一來，因?yàn)門i=ai(1≤i≤n)，所以P1完成所有任務(wù)的時(shí)間是Ji∈P1Ti=ai∈Aai=m=如果所構(gòu)造的n個(gè)任務(wù)，J1,J2,...,Jn，可以在P1和P2上在k秒內(nèi)完成，即Ji∈P1Ti=Ji∈P2Ti=k，那么我們可以把集合S平分如下：A={ai|JiP1(1≤i≤n)}，即把對(duì)應(yīng)于P1所執(zhí)行的任務(wù)的整數(shù)選入子集A。這樣，子集A中的整數(shù)之和為ai∈Aai=Ji∈P1Ti=k=m。而子集S–A因此，我們證明了集合平分問題可多項(xiàng)式歸約為本題的調(diào)度問題。因?yàn)榧掀椒謫栴}是個(gè)NPC問題，所以本題的調(diào)度問題是NP難。假設(shè)計(jì)算機(jī)中有n個(gè)文件，f1,f2,…,fn，需要存入兩張光盤中。這n個(gè)文件所需的空間分別是s1,s2,…,sn(以千字節(jié)KB為單位)，而每張光盤的容量都是M(KB)。假設(shè)存入一個(gè)文件不需要額外的空間開銷，并且所有文件所需的空間總和不超過2M，即i=1nsi2M。我們需要判斷這兩張光盤是否有足夠的空間存入這n個(gè)文件。請(qǐng)證明這個(gè)判斷解：如果我們把文件fi看為任務(wù)Ji，si視為執(zhí)行時(shí)間Ti，把二張光盤1和2看為處理器P1和P2，把文件fi存入光盤1看為把任務(wù)分配給P1，把文件fi存入光盤2看為把任務(wù)分配給P2，那么用類似第14題中的證明可以證明這個(gè)判斷問題是個(gè)NP難問題，或者把任務(wù)調(diào)度問題多項(xiàng)式歸約到這個(gè)問題來證明這個(gè)判斷問題是個(gè)NP難問題。裝箱問題(binpacking)是說有n個(gè)物體，O1,O2,…,On，需要裝箱。這n個(gè)物體分別有體積si并且滿足0<si￡1(1in)。假定每個(gè)箱子的容積是1，我們希望用最少的箱子把它們裝入。我們假定任何一組物體，只要它們的總體積不超過1，都可以裝入一個(gè)箱子之中?；卮鹣旅鎲栴}。為這個(gè)優(yōu)化型問題定義一個(gè)對(duì)應(yīng)的判斷型問題。證明這個(gè)判斷型問題是NP難問題。解：(a) 這個(gè)對(duì)應(yīng)的判斷型問題可定義如下：有n個(gè)物體，O1,O2,…,On，需要裝箱。這n個(gè)物體分別有體積si，并且滿足0<si￡1(1in)。假定有k個(gè)箱子，而每個(gè)箱子的容積是1，并且假定任何一組物體，只要它們的總體積不超過1，都可以裝入一個(gè)箱子之中，判斷這n個(gè)物體是否可以裝入這k個(gè)箱子之中。(b) 我們把集合平分問題多項(xiàng)式歸約到這個(gè)裝箱問題。假設(shè)集合平分問題的實(shí)例中，S={a1,a2,…,an}是n個(gè)非負(fù)整數(shù)的集合，其和為i=1nai=2m。我們可假定ai≤m(1≤i≤n)，否則S不可平分，那我們只需構(gòu)造一個(gè)不可能事件即可，例如讓k=1，s1=0.8,s2=0.8。假定ai≤m(1≤i≤n)，那么我們構(gòu)造一個(gè)k=2的裝箱問題如下：為每一個(gè)整數(shù)ai(1≤i≤n)，構(gòu)造一個(gè)物體Oi，并且賦以體積si=aim≤1。顯然，這是一個(gè)多項(xiàng)式時(shí)間的轉(zhuǎn)換算法。下面證明，這樣構(gòu)造的(1) 假如構(gòu)造的n個(gè)物體可裝入兩個(gè)箱子B1和B2中，那么必定有Oi∈B1si1，Oi∈B2si1。但是因?yàn)镺i∈B1si+Oi∈B2si=i=1nsi=i=1naim=1mi=1nai=2mm=2，所以必有Oi∈B1si=Oi∈B2si=1。我們可以相應(yīng)地把集合S平分如下：我們把裝入B1中的物體所對(duì)應(yīng)的整數(shù)組成S的子集A，即A={ai(2) 假如集合S可平分，即存在一個(gè)子集A，使得ai∈Aai=ai∈S-Aai=m。那么我們可以把A中整數(shù)對(duì)應(yīng)的物體組成集合B1，即B1={Oi|aiA}。因?yàn)閍i∈Aai=m，所以B1中物體的體積之和為Oi∈B1si=Oi∈B1aim=1mOi∈B因此，我們證明了集合平分問題可多項(xiàng)式歸約為本題的裝箱問題。因?yàn)榧掀椒謫栴}是個(gè)NPC問題，所以本題的裝箱問題是NP難。(兩條點(diǎn)不相交路徑問題) 證明下面的判斷型問題是NP難問題：給定一個(gè)加權(quán)的有向圖G(V，E)和V中兩個(gè)頂點(diǎn)s和t，以及正數(shù)k，判斷圖G是否有兩條頂點(diǎn)不相交的從s到t的簡單路徑使得每條長度均不大于k？這里“不相交”是指除了起點(diǎn)s和終點(diǎn)t以外，兩條路徑上所有頂點(diǎn)都不同。這個(gè)問題在網(wǎng)絡(luò)的路由問題中有實(shí)際應(yīng)用的背景。提示：把集合平分問題多項(xiàng)式歸約到這個(gè)問題。假設(shè)集合平分問題的一個(gè)實(shí)例中，S={a1,a2,…,an}是n個(gè)非負(fù)整數(shù)，其和為i=1nai解：我們把集合平分問題多項(xiàng)式歸約到這個(gè)問題。假設(shè)集合平分問題的一個(gè)實(shí)例中，S={a1,a2,…,an}是n個(gè)非負(fù)整數(shù)，其和為i=1nai=2m。我們構(gòu)造一加權(quán)的有向圖G如提示中圖所示，并置k=m。顯然，這是一個(gè)多項(xiàng)式時(shí)間的轉(zhuǎn)換?，F(xiàn)在證明，S可平分當(dāng)且僅當(dāng)圖G中有兩條頂點(diǎn)不相交的從s到t假如S可平分，即存在一個(gè)子集A，使得ai∈Aai=ai∈S-Aai=m。那么，我們可以構(gòu)造一條對(duì)應(yīng)集合A中整數(shù)的路徑P1如下：從s開始到頂點(diǎn)u1，然后，如果a1A，那么P1到達(dá)的下一個(gè)頂點(diǎn)是v2，否則是u2。往下，類似地決定P1要到達(dá)的下一個(gè)點(diǎn)。原則是，如果P1到達(dá)的當(dāng)前頂點(diǎn)是ui或vi時(shí)(i1)，如果aiA，那么下一個(gè)到達(dá)的點(diǎn)是vi+1，否則是ui+1。當(dāng)?shù)竭_(dá)頂點(diǎn)un+1或者vn+1后，下一步到達(dá)終點(diǎn)t。因?yàn)閺膇=1開始，每一條到達(dá)vi+1的邊有權(quán)ai，而到達(dá)ui+1的邊的權(quán)為0，因此這條路徑的長度為w(P1)=vi+1∈P1ai=ai∈Aai=m=k?，F(xiàn)在我們構(gòu)造另一條路徑P2如下：從s開始到頂點(diǎn)v1。然后，決定P2要到達(dá)的下一個(gè)點(diǎn)。原則是，如果P2到達(dá)的當(dāng)前頂點(diǎn)是ui或vi時(shí)(i1)，如果aiS-A，那么下一個(gè)到達(dá)的點(diǎn)是vi+1，否則是ui+1。當(dāng)?shù)竭_(dá)頂點(diǎn)un+1或者vn+1后，下一步到達(dá)終點(diǎn)t。顯然，如果P1經(jīng)過頂點(diǎn)ui+1那么P2則經(jīng)過頂點(diǎn)vi+1，反之，如果P1經(jīng)過頂點(diǎn)vi+1那么P2則經(jīng)過頂點(diǎn)ui+1，所以P1和P2是兩條頂點(diǎn)不相交的從s到t的簡單路徑。另外，P假如所構(gòu)造的圖G有兩條頂點(diǎn)不相交的從s到t的簡單路徑，P1和P2，每條長度不大于k。不失一般性，可假定P1經(jīng)過點(diǎn)u1而P2經(jīng)過點(diǎn)v1。我們可如下平分S：如果P1經(jīng)過點(diǎn)vi+1(1in)，則把a(bǔ)i選入子集A中。這樣一來，子集A中整數(shù)和為ai∈Aai=vi+1∈P1ai=w(P1)k=m。類似的，如果P2經(jīng)過點(diǎn)vi+1，則把a(bǔ)i選入子集S–A中。子集S-A中整數(shù)和為ai∈S-Aai=vi+1∈P2ai=w(P2)k=m。因?yàn)轫旤c(diǎn)vi+1(1in)必定被兩條路徑之一經(jīng)過，所以有w(P1)+w(P2)=i=1nai=2m。因此，w(P1)=因此，我們證明了集合平分問題可多項(xiàng)式歸約為本題的頂點(diǎn)不相交的路徑問題。因?yàn)榧掀椒謫栴}是個(gè)NPC問題，所以本題的頂點(diǎn)不相交的路徑問題是NP難。0/1背包的優(yōu)化問題(0/1knapsackoptimizationproblem)定義如下：設(shè)U={O1,O2,…,On}是n個(gè)物體的集合。物體Oi的體積和它的價(jià)值分別為wi>0和vi>0(1￡i￡n)。另外，有一個(gè)容積為W的背包。任意一組物體，只要它們的體積總和不超過W就可以裝入這個(gè)背包。我們希望從集合U中選出一個(gè)子集Q使子集中物體的體積總和不超過W，但是它的總價(jià)值最大。我們稱這個(gè)問題為0/1背包的優(yōu)化問題是因?yàn)樗辉试S一個(gè)物體被切下一部分來放入背包。請(qǐng)回答下面問題。為0/1背包的優(yōu)化問題定義一個(gè)對(duì)應(yīng)的判斷型問題。證明這個(gè)0/1背包問題是NP難問題。解：(a) 0/1背包的判斷型問題可定義如下：設(shè)U={O1,O2,…,On}是n個(gè)物體的集合。物體Oi的體積和它的價(jià)值分別為wi>0和vi>0(1￡i￡n)。另外，給定一個(gè)容積為W的背包和一個(gè)稱為“價(jià)值期望”的正數(shù)k，判斷是否存在U的一個(gè)子集Q使得子集Q中所有物體的體積總和不超過W而它們的價(jià)值總和大于等于k？(b) 我們把集合平分問題多項(xiàng)式歸約為這個(gè)問題。假設(shè)集合平分問題的一個(gè)實(shí)例中，集合S={a1,a2,…,an}含n個(gè)非負(fù)整數(shù)，其和為i=1nai=2m。我們構(gòu)造一個(gè)0/1背包問題的實(shí)例如下：對(duì)應(yīng)S中每個(gè)整數(shù)ai(1￡i￡n)，構(gòu)造一個(gè)物體Oi并賦以wi=vi=ai。這n個(gè)物體組成集合U。另外，置這個(gè)背包的容積為W=m和價(jià)值期望k=m。顯然，這個(gè)構(gòu)造可在多項(xiàng)式時(shí)間內(nèi)完成。下面證明，這樣構(gòu)造的0/1背包問題有yes(1) 假設(shè)集合S可平分，即存在一個(gè)子集A，使得ai∈Aai=ai∈S-Aai=m。那么，我們把子集A中整數(shù)所對(duì)應(yīng)的物體選入子集Q中，即Q={Oi|aiA}。這樣選出的子集Q中所有物體的總的體積和是V=Oi∈Qwi=ai∈Aai=m=W，而它們的總價(jià)值為Z=Oi∈Q(2) 假設(shè)在構(gòu)造的0/1背包問題中，存在一個(gè)物體的集合Q使得它們的總體積小于等于背包容積W，而它們的總價(jià)值大于等于價(jià)值期望k。那么，我們可以在集合S找出一個(gè)子集A如下：如果物體Oi被選在集合Q中，那么Oi對(duì)應(yīng)的整數(shù)ai屬于子集A，即A={ai|OiQ}。這樣的話，A中所有整數(shù)之和是ai∈Aai=Oi∈QwiW=m。但由于Q中物體的總值價(jià)大于等于價(jià)值期望k，我們有ai∈Aai=Oi∈Qvik=m，因此有a因此，我們證明了集合平分問題可多項(xiàng)式歸約為本題的0/1背包的問題。因?yàn)榧掀椒謫栴}是個(gè)NPC問題，所以本題的0/1背包的問題是NP難。(推廣的貨郎擔(dān)問題）假定G(V,E)是一個(gè)加權(quán)的連通圖，其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。推廣的貨郎擔(dān)問題就是在G中找一條經(jīng)過每個(gè)頂點(diǎn)至少一次的回路C，使得它的所有邊的總權(quán)值最小。如果我們把每個(gè)頂點(diǎn)看作一個(gè)城市，把一條邊看作一條航線，而邊上的權(quán)看為航線距離的話，那么這個(gè)回路就是一個(gè)貨郎擔(dān)周游每個(gè)城市后回到原地的路線圖，而且該路線圖的總路程最小。注意，這個(gè)問題與原貨郎擔(dān)問題的不同在于它不要求G是個(gè)完全圖并允許貨郎擔(dān)經(jīng)過一個(gè)城市多次，只要總路程最小即可。另外要注意的是，一條經(jīng)過每個(gè)點(diǎn)正好一次的回路不一定比經(jīng)過多次的這條推廣的貨郎擔(dān)回路的總路程短。下面的圖給出了一個(gè)例子。aa一1111111bcdef100100經(jīng)過每個(gè)頂點(diǎn)正好一次的回路，<a,b,f,e,d,c,a>,的總權(quán)值為105。推廣的貨郎擔(dān)回路，<a,b,f,e,a,d,c,a>,的總權(quán)值為7。顯然，一個(gè)連通圖一定有經(jīng)過每個(gè)點(diǎn)的回路，但不一定是簡單回路。請(qǐng)證明，判斷一個(gè)連通圖G是否有總長小于等于k的推廣的貨郎擔(dān)回路是個(gè)NP難問題，這里k是一個(gè)給定的正數(shù)。解：我們把哈密爾頓回路問題多項(xiàng)式歸約到這個(gè)問題。設(shè)圖G(V,E)是哈密爾頓回路問題的一個(gè)實(shí)例。如果G(V,E)是個(gè)非連通圖，則不存在哈密爾頓回路，我們可隨便構(gòu)造一個(gè)無解的推廣的貨郎擔(dān)問題即可，例如構(gòu)造一個(gè)有3個(gè)點(diǎn)的三角形并使每條邊權(quán)值為2，但置k=1。所以，我們可假定G(V,E)是個(gè)連通圖。我們?cè)跇?gòu)造對(duì)應(yīng)的推廣的貨郎擔(dān)問題的圖G’(V’,E’)時(shí)，用同樣的頂點(diǎn)集合和邊的集合，即V’=V,E’=E。另外，賦以每條邊的權(quán)值為1，并置k=|V|?？梢宰C明圖G有一條哈密爾頓回路當(dāng)且僅當(dāng)G’有一條推廣的貨郎擔(dān)回路并且總權(quán)值小于等于k。如果圖G有一條哈密爾頓回路，那么，在G’中這條回路對(duì)應(yīng)于一條推廣的貨郎擔(dān)回路。由于每條邊權(quán)值為1，那么這條回路總權(quán)值為|V|=k。如果圖G’有一條推廣的貨郎擔(dān)回路并且總權(quán)值小于等于k，由于每條邊權(quán)值為1，那么這條回路最多有k=|V|條邊。又因?yàn)槊總€(gè)頂點(diǎn)必須經(jīng)過至少一次，那么這條回路必定至少有|V|條邊。但是，這條回路的邊數(shù)又不能大于|V|=k條邊，否則總權(quán)值會(huì)大于k。因此，這個(gè)回路必定經(jīng)過每個(gè)點(diǎn)正好一次。那么，這個(gè)回路對(duì)應(yīng)G中的一條哈密爾頓回路。因此，我們證明了，哈密爾頓回路問題可多項(xiàng)式歸約到這個(gè)推廣的貨郎擔(dān)問題。因?yàn)楣軤栴D回路問題是個(gè)NPC問題，所以本題的推廣的貨郎擔(dān)問題是個(gè)NP難問題。我們知道圖的k-著色問題是個(gè)NPC問題。其實(shí)，圖的3-著色問題就已經(jīng)是個(gè)NP難問題了。下面，我們把3-SAT問題多項(xiàng)式歸約為這個(gè)問題。假設(shè)是一個(gè)3-CNF的表達(dá)式，它含有n個(gè)變量，x1,x2,…,xn，和m個(gè)子句，=C1C2…Cm。我們構(gòu)造一個(gè)3-著色的實(shí)例，也就是一個(gè)圖G=(V,E)如下：我們?yōu)楸磉_(dá)式中每一個(gè)變量xi和它的非xi各構(gòu)造一個(gè)頂點(diǎn)，并標(biāo)以xi和xi。構(gòu)造3個(gè)特殊的頂點(diǎn)并分別標(biāo)以真、假、空，并把它們聯(lián)結(jié)為一個(gè)三角形。為每一個(gè)子句，Cj(1jm)，如下圖(a)構(gòu)造5個(gè)新頂點(diǎn)，a,b,c,d,e。然后，把Cj中3個(gè)文字對(duì)應(yīng)的3個(gè)頂點(diǎn)，5個(gè)新頂點(diǎn)，以及頂點(diǎn)“真”，一共9個(gè)頂點(diǎn)按下面圖(a)聯(lián)成一個(gè)子圖。圖中x、y、z表示子句Cj中的文字。(a)(a)(b)xyz真空假zxyz真abcdeabcde如圖(b)所示，把每一對(duì)點(diǎn)xi和xi(1jn)，以及特殊點(diǎn)“空”之間連成一個(gè)三角形。為清晰起見，圖(b)中只顯示了一對(duì)點(diǎn)z和z。實(shí)際構(gòu)造時(shí)應(yīng)為每一個(gè)變量xi構(gòu)造一個(gè)三角形?，F(xiàn)在，圖構(gòu)造好了，證明這是個(gè)多項(xiàng)式歸約，所以3-著色問題是個(gè)NP難問題。解：以上構(gòu)造顯然只需多項(xiàng)式時(shí)間。我們只需證明，這樣構(gòu)造的圖可以3-著色當(dāng)且僅當(dāng)表達(dá)式可以被滿足。證明如下：假設(shè)構(gòu)造的圖可以3-著色，我們假定用真、假、空三種顏色，并可假定這三個(gè)特殊頂點(diǎn)分別著以真、假、空，三色。那么在3-著色中，因?yàn)槿魏挝淖謱?duì)應(yīng)的頂點(diǎn)與標(biāo)為“空”的點(diǎn)相鄰，它們對(duì)應(yīng)的頂點(diǎn)必然是著色為真或假。如果一個(gè)文字對(duì)應(yīng)的頂點(diǎn)是著色為真，我們就把表達(dá)式中的這一文字賦值為1，否則是0。這么賦值是合法的，因?yàn)樽兞縳i和它的非(xi)之間有邊，它們對(duì)應(yīng)的頂點(diǎn)著色不同。所以，必然是一個(gè)賦值為1，另一個(gè)是0。我們要證明每個(gè)子句中必定有一個(gè)文字賦值為1，也就是要證明每個(gè)子句中必定有一個(gè)文字對(duì)應(yīng)的頂點(diǎn)著色為真。如若不然，為用反證法設(shè)某子句中三個(gè)文字對(duì)應(yīng)的頂點(diǎn)x、y、z均著色為假，那么，如下圖所示，按a、b、c、d、e順序簡單的推理可知，頂點(diǎn)a和b必定著色為空和真，頂點(diǎn)c必定著色為假，頂點(diǎn)d必定著色為空。那么頂點(diǎn)e必須著色為假。這與頂點(diǎn)z的著色矛盾，所以這個(gè)子句的子圖不可能被三著色。因此，每個(gè)子句中必定有一個(gè)文字賦值為1，從而表達(dá)式可以被滿足。xxyz真假假假必須=假，與z矛盾假(只能空或真)假(只能空或真)必須=假必須=空abcde(2) 假設(shè)表達(dá)式可以被滿足，那么我們對(duì)構(gòu)造的圖3-著色如下：首先把三個(gè)特殊頂點(diǎn)分別著以真、假、空，三色，與其標(biāo)記一致。然后，如果一個(gè)文字賦值為1，則將它對(duì)應(yīng)的頂點(diǎn)著色為“真”否則為“假”。最后，我們把對(duì)應(yīng)每個(gè)子句(xyz)的子圖中5個(gè)未著色頂點(diǎn)著色如下。我們分兩種情況討論。(2.1) 如果子圖中與點(diǎn)e相連的點(diǎn)z著色為“真”，那么其余點(diǎn)可如下面圖(c)所示著色。圖中，我們用

色(x)表示著與x相同的顏色(同為“真”或同為“假”，而色(x)表示著與x相反的顏色。)(2.2) 如果子圖中與點(diǎn)e相連的點(diǎn)z著色為“假”，那么，其余兩個(gè)文字對(duì)應(yīng)的頂點(diǎn)之一必定著色為“真”。不失一般性，設(shè)色(x)=“真”，那么子圖中其余點(diǎn)可如下圖(d)所示著色。顯然，這個(gè)著色是個(gè)合法的3著色。因此，我們證明了，3-SAT問題可多項(xiàng)式歸約為3-著色問題。因?yàn)?-SAT問題是個(gè)NPC問題，所以3-著色問題是個(gè)NP難問題。真真xyz真假色(x)空空abcde色(x)(c)xyz真假空假空假abcde真(d)真假設(shè)我們需要把某煤礦的煤用卡車一次性運(yùn)往兩個(gè)地方。又假設(shè)我們有n部卡車，其裝載量只有兩種，一種是5噸的卡車，另一種是8噸的卡車。假設(shè)我們有a部5噸的卡車，b部8噸的卡車，a+b=n。我們希望把這些卡車分成兩組，各組負(fù)責(zé)送一個(gè)地方，并且使得兩個(gè)地方獲得相等重量的煤。我們假定煤礦有足夠的煤供運(yùn)輸并且每輛車必須滿載。如果不能使兩地獲得正好相等的煤，那我們希望兩者差別越小越好。你認(rèn)為這問題是NP完全問題嗎？如果不是，請(qǐng)給出一個(gè)多項(xiàng)式算法，否則，請(qǐng)證明這是一個(gè)NP完全問題。解：這不是NP完全問題。它的一個(gè)多項(xiàng)式算法如下: Truck-Partition(a,b)M5a+8b //總的運(yùn)輸量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這個(gè)算法窮舉所有可能的組合，并且從中找出最佳的解，所以算法正確。又因?yàn)樗锌赡艿慕M合不超過(a+1)(b+1)=O(n2)，這是一個(gè)多項(xiàng)式算法。假設(shè)我們需要把某煤礦的煤用卡車一次性運(yùn)往三個(gè)地方。又假設(shè)我們有n>3部卡車，其裝載量分別是c1，c2，…，cn，且都是以整數(shù)公斤為單位。我們希望把這些卡車分成三組，各組負(fù)責(zé)送一個(gè)地方，并且使得三個(gè)地方獲得相等重量的煤。我們假定煤礦有足夠的煤供運(yùn)輸并且每輛車必須滿載。請(qǐng)證明判斷這個(gè)分組問題是否有解是個(gè)NP難問題。證明：我們把集合平分問題歸約到這個(gè)問題。設(shè)集合平分問題中集合是S={a1，a2，…，an}(n>2)。我們構(gòu)造分組問題如下：計(jì)算M=i=1n可假定M是個(gè)偶數(shù)，M=2k。否則，集合劃分問題無解，我們可以構(gòu)造一個(gè)無解的運(yùn)輸分組問題。構(gòu)造(n+1)部卡車，其中頭n部卡車的裝載量分別是c1=a1，c2=a2，…，cn=an，第(n+1)部卡車有裝載量k=M/2。顯然，集合劃分問題有解當(dāng)且僅當(dāng)這個(gè)構(gòu)造的分組問題有解。因?yàn)闃?gòu)造這分組問題只需多項(xiàng)式時(shí)間，所以集合劃分問題可多項(xiàng)式歸約到這個(gè)卡車分組問題。所以這個(gè)卡車分組問題是個(gè)NP難問題。在第9章習(xí)題14中我們討論過2-樹支撐森林的問題。這里我們考慮最小-最大(min-max)2-樹支撐森林的問題。給定一個(gè)加權(quán)的連通圖G(V,E)，最小-最大(min-max)2-樹支撐森林的問題是找出一個(gè)2-樹支撐森林，T1和T2，使得有較大權(quán)值的樹的權(quán)，即max{W(T1),W(T2)}，在所有2-樹支撐森林中是最小的?；卮鹨韵聠栴}。定義與這個(gè)優(yōu)化型問題對(duì)應(yīng)的一個(gè)判斷型問題。證明這個(gè)判斷型問題是個(gè)NP難問題。解：(a) 以下是對(duì)應(yīng)的一個(gè)判斷型問題：給定一個(gè)加權(quán)的連通圖G(V,E)和一個(gè)實(shí)數(shù)k，判斷是否存在一個(gè)2-樹支撐森林，T1和T2，使得max{W(T1),W(T2)}k?(b) 我們把集合平分問題多項(xiàng)式歸約到這個(gè)問題。假設(shè)集合平分問題的一個(gè)實(shí)例中，S={a1,a2,…,an}是n個(gè)正整數(shù)的集合，其和為i=1nai=2m。我們假設(shè)aim(1) 構(gòu)建兩個(gè)頂點(diǎn)，p和q。(2) 為每一個(gè)數(shù)字ai(1≤i≤n)，構(gòu)建一個(gè)頂點(diǎn)vi和兩條邊，(p,vi)和(q,vi)。它們的權(quán)值為w(p,vi)=w(q,vi)=ai。(3) 置k=m。顯然，這個(gè)構(gòu)造算法是個(gè)多項(xiàng)式算法，下圖給出一個(gè)例子。集合集合S={5,8,11,7,6,9,2}總和2m=48v1v2v3v4v5v6v75588111177669922pq由集合S構(gòu)造的圖G，k=24 現(xiàn)在我們證明，所構(gòu)造的圖G有一個(gè)2-樹支撐森林，T1和T2，使得max{W(T1),W(T2)}k當(dāng)且僅當(dāng)集合S可平分。假設(shè)集合S可平分為A和S-A，使得ai∈Aai=ai∈S-Aai=m。我們可以如下構(gòu)建T1={(p,vi)|aiA}。T2={(q,vj)|ajS-A}。因?yàn)槊總€(gè)頂點(diǎn)vi(1≤i≤n)與點(diǎn)p或q相連，且T1和T2沒有交點(diǎn)，T1和T2形成一個(gè)2-樹支撐森林。又因?yàn)閣(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假設(shè)所構(gòu)造的有向圖G有一個(gè)2-樹支撐森林，T1和T2，使得max{W(T1),W(T2)}k，那么集合S可如下平分為A和S-A。我們分三種情況：(2.1)點(diǎn)p和q同屬T1。這時(shí)，T2中的點(diǎn)不可以與p和q相鄰，只能以孤立點(diǎn)出現(xiàn)(度數(shù)為0)。因此，T2沒有邊，且只含一個(gè)點(diǎn)。這時(shí)，在T1中的每個(gè)點(diǎn)vi(1≤i≤n)必須與點(diǎn)p或點(diǎn)q相鄰。另外，至少有一個(gè)點(diǎn)vi(1≤i≤n)與點(diǎn)p和點(diǎn)q都相鄰，否則點(diǎn)p和點(diǎn)q不連通。這使得W(T1)>m=k，所以這種情況不可能出現(xiàn)。(2.2)點(diǎn)p和q同屬T2。與情況(2.1)類似，這種情況不可能出現(xiàn)。(2.3)點(diǎn)p和q分屬于T1和T2。不失一般性，設(shè)pT1，qT2。這樣的話，任一其它頂點(diǎn)vi(1≤i≤n)必定屬于T1或T2。如果vi屬于T1，那么，邊(p,vi)必定包含在T1中，而邊(q,vi)必定被排除在T1和T2之外。所以，我們有：W(T1)=vi∈T1W(T2)=vj∈T2因此，如果頂點(diǎn)vi屬于T1，我們把集合S中對(duì)應(yīng)于vi的數(shù)ai放入集合A中，否則放入集合S-A中，即A={ai|vi屬于T1}，S-A={aj|vj屬于T2}。因?yàn)閣(p,vi)=ai，故有ai∈Aai=vi∈T1w(p,vi)≤k=m。類似地，aj∈S-Aaj=vj∈T2w(q,vj)≤k=m。因?yàn)閍i∈Aai+因此，我們證明了，集合平分問題可多項(xiàng)式歸約到這個(gè)最小-最大2-樹支撐森林問題。因?yàn)榧掀椒謫栴}是個(gè)NPC問題，所以最小-最大2-樹支撐森問題是個(gè)NP難問題?？紤]以下活動(dòng)選擇問題。假設(shè)禮堂從時(shí)刻t=0到t=T>0這一段可以安排活動(dòng)。假設(shè)時(shí)間單位都以分鐘計(jì)算。現(xiàn)在有n個(gè)活動(dòng)，a1，a2，…，an，申請(qǐng)使用禮堂。每個(gè)活動(dòng)ai(1in)需要連續(xù)占用禮堂ti分鐘，并且必須安排在時(shí)刻si(0≤si)或早于時(shí)刻si開始。當(dāng)然，在任何時(shí)刻，只能允許一個(gè)活動(dòng)占用禮堂，并且所有被選取的活動(dòng)要在時(shí)刻T之前完成。我們希望選出一個(gè)活動(dòng)的集合A使得禮堂被使用的時(shí)間，即ai∈At定義與這個(gè)優(yōu)化型問題對(duì)應(yīng)的一個(gè)判斷型問題。證明這個(gè)判斷型問題是個(gè)NP難問題。解：(a) 以下是對(duì)應(yīng)的一個(gè)判斷型問題：假設(shè)禮堂從時(shí)刻t=0到t=T>0這一段可以安排活動(dòng)。假設(shè)時(shí)間單位都以分鐘計(jì)算。現(xiàn)在有n個(gè)活動(dòng)，a1，a2，…，an，申請(qǐng)使用禮堂。每個(gè)活動(dòng)ai(1in)需要連續(xù)占用禮堂ti分鐘，并且要求在si(0)或早于si開始。被選中的活動(dòng)必須能安排在t=T之前完成。在任何時(shí)刻，只能允許一個(gè)活動(dòng)占用禮堂。請(qǐng)判斷是否存在一個(gè)滿足上述要求的互相兼容的活動(dòng)的集合A使得禮堂被使用的時(shí)間大于或等于k，即ai∈Ati(b) 我們把子集和問題多項(xiàng)式歸約到這個(gè)問題。假設(shè)子集和問題的一個(gè)實(shí)例中，S={v1,v2,…,vn}是n個(gè)正整數(shù)的集合，另有一個(gè)目標(biāo)值t>0。子集和問題要求判斷是否有一個(gè)S的子集V,VS，使得vi∈Vvi=t。我們把這個(gè)(1)置T=t(目標(biāo)值)。禮堂從時(shí)刻t=0到T>0這一段可以安排活動(dòng)。(2)為每一個(gè)S中數(shù)vi(1≤i≤n)，構(gòu)建一個(gè)活動(dòng)ai使得ti=vi，si=T-ti。(3)置k=t。顯然這個(gè)轉(zhuǎn)換只需多項(xiàng)式時(shí)間。下面證明，如果集合S有子集V,VS，使得Vi∈Vvi=t，那么，所構(gòu)造的活動(dòng)中存在一個(gè)集合A假設(shè)集合S有子集V,VS，使得vi∈Vvi=t=T。我們可以如下選出活動(dòng)的集合A：如果數(shù)字vi在子集V中，viV，那么，對(duì)應(yīng)于vi所構(gòu)造的活動(dòng)ai入選，即A={ai|viV}。因?yàn)関i∈Vvi=t，而ti=vi，故有ai∈Ati=vi∈Vvi=T=t=k。又因?yàn)閟i=T-ti和假設(shè)所構(gòu)造的活動(dòng)中存在一個(gè)集合A使得禮堂被使用的時(shí)間大于或等于k，ai∈Ati≥k。我們可以如下找出子集V：如果aiA，那么我們從集合S中把構(gòu)造ai時(shí)所用的數(shù)字vi放在子集V中，即V={vi|aiA}。因?yàn)槎Y堂可用的時(shí)間不會(huì)超過T，即ai∈AtiT=t=k，所以ai∈Ati≥k意味著ai∈Ati=T=t。那么，因?yàn)閠i=vi，我們有vi∈Vvi=因此，我們證明了，子集和問題可多項(xiàng)式歸約到這個(gè)活動(dòng)選擇問題。因?yàn)樽蛹蛦栴}是個(gè)NPC問題，所以這個(gè)活動(dòng)選擇問題是個(gè)NP難問題?？紤]以下活動(dòng)選擇問題。假設(shè)我們有兩個(gè)禮堂可以從時(shí)刻t=0安排活動(dòng)。假設(shè)時(shí)間單位都以分鐘計(jì)算?，F(xiàn)在有n個(gè)活動(dòng)，a1，a2，…，an，要求使用一個(gè)禮堂，兩個(gè)禮堂中任一個(gè)都行?；顒?dòng)ai(1in)必須安排在時(shí)刻si(0≤si)或早于時(shí)刻si開始，但一旦開始，需要連續(xù)占用該禮堂ti分鐘。當(dāng)然，在任何時(shí)刻，任一個(gè)禮堂只能允許一個(gè)活動(dòng)占用。我們希望選出一個(gè)有最多活動(dòng)的集合A使得這些活動(dòng)可以互相兼容地使用這兩個(gè)禮堂?；卮鹨韵聠栴}。定義與這個(gè)優(yōu)化型問題對(duì)應(yīng)的一個(gè)判斷型問題。證明這個(gè)判斷型問題是個(gè)NP難問題。解：(a)對(duì)應(yīng)的一個(gè)判斷型問題可定義如下：假設(shè)我們有兩個(gè)禮堂可以從時(shí)刻t=0安排活動(dòng)。假設(shè)時(shí)間單位都以分鐘計(jì)算?，F(xiàn)在有n個(gè)活動(dòng)，a1，a2，…，an，要求使用一個(gè)禮堂，兩個(gè)禮堂中任一個(gè)都行?；顒?dòng)ai(1in)可以安排在時(shí)刻si(0≤si)或早于時(shí)刻si開始，但一旦開始，需要連續(xù)占用該禮堂ti分鐘。當(dāng)然，在任何時(shí)刻，任一個(gè)禮堂只能允許一個(gè)活動(dòng)占用。請(qǐng)判斷，我們能否選出有至少k個(gè)活動(dòng)的集合A使得這些活動(dòng)可以互相兼容地使用這兩個(gè)禮堂？這里，kn是一個(gè)正整數(shù)。(b)我們把集合平分問題多項(xiàng)式歸約到這個(gè)活動(dòng)選擇問題。假設(shè)集合平分問題的一個(gè)實(shí)例中，S={v1,v2,…,vn}是n個(gè)正整數(shù)的集合，其和Vi∈Svi=2m(m是正整數(shù))。我們假設(shè)vi為S中每一個(gè)數(shù)vi構(gòu)造一個(gè)活動(dòng)ai，它需要占用禮堂的時(shí)間是ti=vi，它的開始時(shí)刻是si=m-vi或早于si。置k=n。這顯然是個(gè)多項(xiàng)式時(shí)間的轉(zhuǎn)換算法。我們證明集合S可平分當(dāng)且僅當(dāng)我們構(gòu)造的n個(gè)活動(dòng)可以互相兼容地使用這兩個(gè)禮堂。假設(shè)集合S可平分為子集A和S-A，使得vi∈Avi=vi∈S-Avi=m。那么，我們可以為第一個(gè)禮堂選擇活動(dòng)如下：H1={ai|viA}，也就是選取由子集A中數(shù)字所構(gòu)造的所有活動(dòng)。因?yàn)閠i=vi，我們有ti∈H1ti=vi∈Avi=m。因?yàn)樗鼈兊拈_始時(shí)刻只要是si=m-vi或更早即可，所以我們只需把它們一個(gè)接一個(gè)地安排在第一個(gè)禮堂，便可以互相兼容地使用這個(gè)禮堂。同理，其余的活動(dòng)是由集合S-A中數(shù)字所構(gòu)造的活動(dòng)，我們可以把它們安排在第二個(gè)禮堂，H2={ai|viS-A}。因?yàn)榧僭O(shè)我們構(gòu)造的n個(gè)活動(dòng)可以互相兼容地使用這兩個(gè)禮堂。設(shè)H1是安排在第一個(gè)禮堂的活動(dòng)，H2是安排在第二個(gè)禮堂的活動(dòng)。那么，我們可以平分集合S如下：A={vi|aiH1}，也就是構(gòu)造H1中活動(dòng)所用的數(shù)字的集合。顯然，由余下的數(shù)字S-A構(gòu)造的活動(dòng)必定安排在第二個(gè)禮堂，即S-A={vi|aiH2}。因?yàn)閠i∈H1ti≤m，ti∈H2ti≤m，而ti∈H1ti+ti∈H2ti=vi∈Avi+v∈S-Avi=vi∈Svi=2