計算機算法基礎 第2版 習題及答案 第14章

PAGE32第14章 NP完全問題判斷以下各命題對與錯。如果P1NP，那么就不存在多項式算法來判斷一個圖是否可以3著色。如果P1NP，那么就不存在多項式算法來判斷一個圖是否含有一個6-clique。如果P1NP，那么就不存在多項式算法來判斷一個圖是否有一個6-cover。如果問題A有多項式算法在(n3)時間內(nèi)被判定，而問題B在(n3)時間內(nèi)可歸約為問題A，那么問題B也就可以在(n3)時間內(nèi)被判定，這里的n指的都是問題的輸入規(guī)模。如果問題A有算法在(2n)時間內(nèi)被判定，而問題B在多項式時間內(nèi)可歸約為問題A，那么問題B也就可以在(2n)時間內(nèi)被判定解：(a)對 (b)錯 (c)錯 (d)錯 (e)錯。假設給你一個“寶盒子”P，它可以在常數(shù)時間內(nèi)正確判定一個有n個正整數(shù)的集合S是否可以被平分，但它不能給出實際的平分，它只可以被你的程序調(diào)用并輸出P(S)=1或P(S)=0。請設計一個以P為子程序的多項式算法為一個可平分的集合S作出實際的平分。解：算法思路如下：設S={a1,a2,…,an}。如果集合S可被平分為集合A和S-A，那么我們可以用P來檢測a2是否可以與a1分在同一個集合。辦法是，我們把a1和a2從S中刪去，換之以一個數(shù)c，其值為(a1+a2)，即SS{c}–{a1,a2}。如果改動后的集合S仍然有P(S)=1，則表明新的集合S可以平分，而新集合可以平分則表明原集合可以平分，并且a1和a2可以分在同一個集合。否則，如果有P(S)=0，則表明a1和a2不可以分在同一個集合，我們則恢復原集合。我們用這個辦法把所有可以與a1分在同一個集合的整數(shù)都找出來，平分完成。下面?zhèn)未a精確地表達了這個算法。Partition(S)ifP(S)=0 //P作為子程序被調(diào)用 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個元素中每個元素都出現(xiàn)在子家族C中的某個集合里，那么C稱為是F的一個復蓋，因為C復蓋了F中所有元素，即?Si∈CSi={a1，a2，…，am}。如果C是F的一個復蓋并且所含集合數(shù)最少，則稱為一個最小復蓋。比如，F(xiàn)={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}。對一個給定正整數(shù)k，判斷F中是否有一個k-復蓋，即含k證明集合復蓋問題是NP難問題。我們把頂點復蓋問題多項式歸約到集合復蓋問題。假設一個頂點復蓋問題的實例是圖G(V,E)和整數(shù)k。下面解釋如何由這個實例來構(gòu)造一個集合復蓋問題的實例。假設圖G(V,E)有m條邊，E={e1，e2，…，em}，那么，對應G中每一條邊ei(1im)，我們構(gòu)造一個元素ai。然后，對應G中每一個頂點vV，我們構(gòu)造一個集合Sv，而它所含元素就是與點v關(guān)聯(lián)的邊所對應的元素，即Sv={ai|邊ei與v關(guān)聯(lián)，1im}。設|V|=n，那么這n個集合一起就組成了一個家族F，F(xiàn)={Sv|vV}。下面看一個例子。假設頂點復蓋問題的圖如下。 我們?yōu)?個頂點構(gòu)造6個集合如下： Sa={a1,a3,a4}，Sb={a2,a7,a8}，Sc={a3,a5,a7}，Sd={a4,a6,a8}，Se={a5,a6}，Sf={a1,a2}。這些集合組成了集合復蓋問題中的家族，F(xiàn)={Sa，Sb，Sc，Sd，Se，Sf}。下面我們證明圖G有一個k-復蓋當且僅當構(gòu)造的家族F有一個k-復蓋。根據(jù)我們的構(gòu)造，一條邊ei(1im)，與一個頂點v相關(guān)聯(lián)當且僅當元素ai屬于集合Sv。所以，S={v1,v2,…,vk}是G的一個k-復蓋當且僅當C={Sv1,Sv2,…,Svk}是F的一個k假設我們要舉行一個學術(shù)會議。會議有m個議題，T1，T2，…，Tm。對每一個議題Ti(1im)有一個可以審這方面稿件的教授的名單Pi。一個教授可能為幾個不同的議題審稿而出現(xiàn)在幾個名單中?，F(xiàn)在，我們希望從這些名單中選出一些教授來組成一個審稿委員會。我們希望委員會的人數(shù)越少越好，但是保證每一個議題都有能審稿的委員。請回答以下問題。定義與這個優(yōu)化型問題對應的一個判斷型問題。證明這個判斷型問題屬于NP類。把圖的頂點復蓋問題多項式歸約到這個判斷型問題以證明其NP完全性。解：(a) 讓我們稱對應的判斷型問題為審稿委員會問題。定義如下：假設我們要舉行一個學術(shù)會議。會議有m個議題，T1，T2，…，Tm。對每一個議題Ti(1im)有一個可以審這方面稿件的教授的名單Pi。一個教授可能為幾個不同的議題審稿而出現(xiàn)在幾個名單中。請判斷，能否從這些名單中選出k個教授來組成一個審稿委員會使得每個議題都至少有一個委員可以審稿？(b) 我們?yōu)樯厦娴呐袛嘈蛦栴}設計一個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)和正整數(shù)k是頂點復蓋問題的一個實例，其中V={v1，v2，…，vn}，E={e1，e2，…，em}?，F(xiàn)在我們構(gòu)造一個審稿委員會問題的實例。首先，對應G中每一條邊ei(1im)我們構(gòu)造一個議題Ti，而對應G中每一個頂點uV，構(gòu)造一個教授u。然后，對每一議題Ti(1im)構(gòu)造一個可以審稿的教授名單Pi。這個名單由兩個教授組成，就是構(gòu)造Ti時所對應的邊ei的兩個端點所對應的教授。例如，ei=(u,v)，那么由頂點u和v所構(gòu)造的教授u和v組成Pi，Pi={u,v}。下面看一個例子。下面的圖是頂點復蓋的一個實例。由上面這個圖，我們構(gòu)造9個議題，分別對應這9條邊：T={T1,T2,T3,T4,T5,T6,T7,T8,T9}。然后構(gòu)造5個教授，分別對應5個頂點:P={a,b,c,d,e}。接下來，為每個議題構(gòu)造一個審稿教授名單如下：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òu)造算法顯然可以在多項式時間內(nèi)完成。現(xiàn)在證明，原來圖G中有一個k-復蓋當且僅當所構(gòu)造的問題中有一個k人組成的審稿委員會使得每一個議題都能有至少一個可審這方面稿件的教授在委員會中。假設圖G中有一個k-復蓋，那么由這k個點對應的k個教授組成的審稿委員會一定可以審任何一個議題的稿件。這是因為圖中任何一條邊e都與這個復蓋中至少一個點v相關(guān)聯(lián)，那么對應于e的議題可由對應的教授v審稿，而且教授v在委員會中。所以任何一個議題都能有至少一個可審這方面稿件的教授在委員會中。假設所構(gòu)造的問題中有一個k個教授組成的審稿委員會使得每一個議題都能有至少一個可審這方面稿件的教授在委員會中。那么對應于這k個教授的k個頂點一定是G的一個復蓋。這是因為圖G的任一條邊e所對應的議題可由委員會中一教授v審稿，那么邊e一定與對應于教授v的頂點v相關(guān)聯(lián)而且頂點v被選入復蓋。所以對應于這k個教授的k個頂點一定是G的一個復蓋。一個圖G=(V，E)的頂點子集SíV稱為一個獨立集(independentset)，如果E中任何一條邊只與S中最多一個點有關(guān)聯(lián)。也就是說，如果S中任意兩點之間沒有邊，那么它就是一個獨立集。最大獨立集問題就是要找出圖G的一個最大的獨立集。請回答以下問題。定義與這個優(yōu)化型問題對應的一個判斷型問題。證明這個判斷型問題屬于NP類。證明這個判斷型問題是NP完全問題。解：(a)對應的判斷型問題可定義如下：給定一個圖G(V，E)以及一個正整數(shù)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)和整數(shù)k是一個clique問題的實例，我們構(gòu)造一個獨立集問題的實例如下：從圖G(V,E)我們構(gòu)造其補圖G。這個構(gòu)造顯然可在多項式時間內(nèi)完成。顯而易見，如果圖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) 定義與這個優(yōu)化型問題對應的一個判斷型問題。(b) 證明這個判斷型問題屬于NP類。(c) 證明支配集問題是NP完全問題。(d) 假設有一個多項式算法A解決這個判斷型問題，請利用這個算法得到一個多項式算法來解決對應的優(yōu)化型問題。解：(a) 對應的判斷型問題可定義如下：給定一個圖G(V,E)以及一個正整數(shù)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)和正整數(shù)k是頂點復蓋問題的一個實例，其中V={v1,v2,…,vn}，E={e1,e2,…,em}。下面是由此構(gòu)造一個支配集問題實例的算法。首先，構(gòu)造一個二部圖G’(U’,V’,E’),這里U’=V={v1，v2，…，vn}，V’={e1，e2，…，em}，也就是說，對應G中每個頂點和每條邊構(gòu)造G’的一個頂點。邊的集合E’由兩部分組成。第1部分是E’1={(u,v)|u,vU’，uv}，也就是說，U’中點形成一個完全圖。第2部分是E’2={(vi,ej)|viU’，ejV’，vi在G中是ej的端點}。下面的圖(a)(b)給出了一個這樣轉(zhuǎn)換的實例。((b)圖G’abcde(a)圖Ge1e2e3e4e5e6abcdee1e2e3e4e5e6U’V’顯然，這個轉(zhuǎn)換算法只需多項式時間?，F(xiàn)在證明，圖G有一個k-復蓋當且僅當G’有個k-支配集，kn。假設G有一個k-復蓋。那么這k個頂點所對應的U’中的k個頂點是G’的一個支配集。這是因為G中每一條邊都與這k-復蓋中某個點關(guān)聯(lián)，所以在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。我們先確定最小支配集中頂點個數(shù)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òu)造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是最小支配集中頂點數(shù)endwhileD? //支配集開始為空WV //W是可能被選為支配集中點while|D|≠k extractavertexvfromW //從W取一點v V*?V-Adj(v) -{v} //V不變，構(gòu)造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關(guān)聯(lián)的邊 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經(jīng)過圖中每個點恰好一次，那么路徑P稱為一條哈密爾頓路徑。判斷圖G=(V,E)是否有一條哈密爾頓路徑稱為哈密爾頓路徑問題。證明哈密爾頓路徑問題是個NP難問題。解：我們把哈密爾頓回路問題多項式歸約為哈密爾頓路徑問題。假設G(V,E)是哈密爾頓回路問題的一個實例。在多項式時間內(nèi)，我們由G(V,E)構(gòu)造一個哈密爾頓路徑問題的實例，也就是圖G’(V’,E’)。不失一般性，可假設G至少有3個頂點，否則G最多有兩個點，不可能有回路。這個構(gòu)造算法的步驟如下：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òu)造的圖G’(V’,E’)中，V’=Vè{w,x,y},E’=Eè{(w,a),(x,y)}è{(v,x)|v?Adj(a)}。下面的圖給出了一個上面構(gòu)造算法的一個例子。顯然，這是一個多項式時間的構(gòu)造算法。aadecbaadecbaw乙xy(a)圖G(b)圖G’現(xiàn)在，我們證明圖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為起始點?？杉僭OP的頂點序列為<w,a,u,…,v,x,y>。那么我們可以得到G的一條哈密爾頓回路C，其頂點序列為<a,u,…,v,a>，證畢。假設在一個城市里有m個家庭有小孩要上學，同時有n個學校可以保證每個家庭在150米之內(nèi)至少有一個學校。假設這m個家庭編號為Hi(1im)，這n個學校編號為Sj(1jn)?，F(xiàn)在由于經(jīng)費短缺，需要關(guān)閉一些學校以節(jié)省開支，但仍然保證每個家庭在200米之內(nèi)至少有一個學?？梢陨稀＝?jīng)過調(diào)查，我們?yōu)槊總€學校Sj(1jn)列出在它200米內(nèi)所有家庭的編號，即Pj={Hi|1im，Hi與Sj相距不超過200米}。一個優(yōu)化問題是，我們希望在保證每個家庭有一個學校在200米內(nèi)的基礎上，關(guān)閉最多的學校。請為上述優(yōu)化問題定義一個對應的判斷型問題。證明該判斷型問題屬于NP類。證明該判斷型問題是NP難問題。解:(a) 對應的判斷型問題可表述為：假設在一個城市里有m個家庭有小孩要上學，同時有n個學校。假設這m個家庭編號為Hi(1im)，這n個學校編號為Sj(1jn)。經(jīng)過調(diào)查，我們?yōu)槊總€學校Sj(1jn)列出在它200米內(nèi)所有家庭的編號，即Pj={Hi|1im，Hi與Sj相距不超過200米}。請判斷我們是否可以關(guān)閉k個學校但仍保證每個家庭有一個在200米內(nèi)的學校不被關(guān)閉。這里，k是一個正整數(shù)。(b) 我們?yōu)榇嗽O計如下的一個多項式檢驗算法。其中，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表示該校被關(guān)閉 thenjj+1 ifj>n thenreturnno //y不是學?；蛑貜统霈F(xiàn)于Y endif elseS[j]nil //S[j]=y，該校被關(guān)閉 endif endforendforH //統(tǒng)計與余下學校200米距離內(nèi)的所有家庭的集合forj1ton ifS[j]nil thenHHP[j] endifendforfori1tom ifH[i]H thenreturnno endifendforreturnyesEnd(c) 我們把頂點復蓋問題多項式歸約到這個問題。假設圖G(V,E)和正整數(shù)k是頂點復蓋問題的一個實例，其中V={v1,v2,…,vn}，E={e1,e2,…,em}?，F(xiàn)在我們構(gòu)造一個關(guān)閉學校問題如下：(1) 為每一個頂點vj(1jn)構(gòu)造一個學校Sj。(2) 為每一條邊ei(1im)構(gòu)造一個家庭Hi。(3) 為每一個學校Sj(1jn)構(gòu)造與其距離小于等于200米的家庭的集合Pj：Pj={Hi|邊ei與點vj關(guān)聯(lián)}。也就是說，如果邊ei與頂點vj關(guān)聯(lián)，那么，由邊ei構(gòu)造的家庭Hi與由頂點vj構(gòu)造的學校Sj相距小于等于200米。(4) 置k’n-k。 例如，下面的圖是找k-復蓋的一個實例。我們把它轉(zhuǎn)換為學校關(guān)閉問題的一個實例如下：學校集合為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關(guān)聯(lián))當且僅當u對應的學校距離e對應的家庭相距小于等于200米。如果圖G(V,E)有個k-復蓋，使得任一條邊e關(guān)聯(lián)于這k個頂點中某個頂點u，那么由e構(gòu)造的家庭與由點u構(gòu)造的學校就相距小于等于200米。所以，保留由這k-復蓋中的k個頂點構(gòu)造的學校就可保證每個家庭與其中一個學校相距小于等于200米。這也就是說，我們可以關(guān)閉k’(=n-k)個學校。反之，如果我們可以關(guān)閉k’(=n-k)個學校，使每個家庭H與某個不關(guān)閉的k個學校之一，學校s，相距小于等于200米，那么對應這個家庭H的邊e就關(guān)聯(lián)于對應這個學校s的頂點u。所以，對應這不關(guān)閉的k個學校的k個頂點就是圖G(V,E)的一個k-復蓋。所以，圖G(V,E)有k-復蓋，當且僅當構(gòu)造的學校問題可以關(guān)閉k’(=n-k)個學校。因為上述轉(zhuǎn)換顯然只需多項式時間，所以學校關(guān)閉問題是個NP難問題。前面習題7中討論的哈密爾頓路徑問題，以及哈密爾頓回路問題都假定給定的圖G=(V,E)是個無向圖。請解釋為什么在有向圖中找哈密爾頓路徑或回路也是NP完全問題。解：我們總可以把一無向圖G(V,E)的哈密爾頓路徑或回路問題多項式轉(zhuǎn)換為有向圖的哈密爾頓路徑或回路問題。我們只要把無向圖中每一條邊(u,v)換為一對有向邊(u,v)和(v,u)。這樣一來，無向圖G(V,E)中有一條哈密爾頓路徑或回路當且僅當對應的有向圖中有一條哈密爾頓路徑或回路。所以，有向圖中找哈密爾頓路徑或回路也是NP完全問題。給定圖G(V,E)，最長路徑問題就是找一條最長的簡單路徑，也就是找一條路徑P使得所含邊數(shù)最多并且路徑上每個頂點最多經(jīng)過一次。這里，路徑的起點和終點可任取。請為這個優(yōu)化型問題定義一個相應的判斷型問題并證明其NP難。解：對應的判斷型問題可定義如下：給定圖G(V,E)和正整數(shù)k，判斷G是否有一條長度至少為k的簡單路徑。我們可以把哈密爾頓路徑問題多項式歸約為這個問題。假定圖G=(V,E)是哈密爾頓回路問題的實例，其中|V|=n。我們把它轉(zhuǎn)換為最長路徑問題時仍用同一個圖G，但置k=n-1，那么顯然可見，圖G(V,E)有一條哈密爾頓路徑當且僅當圖G有一條長度至少為n-1的簡單路徑。因此，最長路徑問題是個NP難問題。在第10章的討論中，我們知道如果一個加權(quán)的有向圖中含有一個負回路，那么Bellman-Ford算法和Dijkstra算法都不能找到兩個給定頂點間的最短簡單路徑。實際上，如果圖中邊的權(quán)限制為正整數(shù)或負整數(shù)，那么找兩個給定頂點間的最短(簡單)路徑問題也是個NP難問題。請為這個優(yōu)化型問題定義一個對應的判斷型問題并證明它是NP難問題。解：對應的判斷型問題可定義如下：給定一個加權(quán)有向圖G(V,E)，其中每條邊上的權(quán)可以是一個正整數(shù)或一個負整數(shù)。另外，給定V中兩個頂點s和t，以及一個整數(shù)k(可正可負)，判斷G是否有一條從s到t的簡單路徑P使得P的總權(quán)值小于等于k。我們把有向圖的哈密爾頓回路問題多項式歸約為這個最短路徑問題。假設簡單有向圖G(V,E)是哈密爾頓回路問題的一個實例。我們由G(V,E)構(gòu)造一個最短路徑問題的實例G’(V’,E’)。不失一般性，可假設V至少有3個頂點，否則不可能有回路。我們構(gòu)造圖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ò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òu)造算法的一個例子。顯然，這是一個多項式時間的構(gòu)造算法。aadecbaadecbaw乙xy(a)圖G(b)圖G’-1-1-1-1-1-1-1-1-1-1-1-1現(xiàn)在，我們證明圖G有一條哈密爾頓回路當且僅當G’有一條總權(quán)值小于等于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的總權(quán)值是k=-(n+2)。假設圖G’中有一條總權(quán)值小于等于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>。所以，由本題可見，即使權(quán)值是整數(shù)，有負回路的圖的最短路徑問題是個NP難問題。假設一個連通圖G(V,E)的每一條邊有一個非負整數(shù)的權(quán)，我們希望判斷是否可以找到一個支撐樹使得樹中所有邊的權(quán)之和正好是k。請證明這個問題是個NP難問題。解：我們把子集和問題多項式歸約為這個支撐樹問題。假定一個子集和問題的實例是含n個正整數(shù)的集合S={a1,a2,…,an}和目標值t。我們由此構(gòu)造一個支撐樹問題的一個實例。步驟如下：對應每個整數(shù)ai(1￡i￡n)，構(gòu)造一個三角形，(xi,yi,zi)，并且賦以權(quán)值w(xi,yi)=w(yi,zi)=0，w(zi,xi)=ai。在頂點xi和xi+1之間聯(lián)一條邊并賦以權(quán)值w(xi,xi+1)=0(1￡i￡n-1)。置k=t。下面的圖顯示了這樣構(gòu)造的圖。顯然這個構(gòu)造只需多項式時間?，F(xiàn)在證明，集合S有子集和為t當且僅當所構(gòu)造圖有一棵支撐樹，其總權(quán)值為k。假設S有子集AíS使得ai∈Aai=t。那么，如果aiA，我們在圖中對應于ai的三角形(xi,yi,zi)中把邊(xi,yi)刪去，否則把(xi,zi)刪去。這樣得到的一棵支撐樹的總權(quán)值顯然等于ai∈A如果所構(gòu)造的圖有一棵支撐樹T，它的總權(quán)值等于k，那么在圖中對應于ai的三角形(xi,yi,zi)中必定有兩條邊屬于T而第3條邊被刪去。從圖的構(gòu)造可知，T的總權(quán)值=(zi,xi)∈Tw(zi,xi)=k。我們可以這樣構(gòu)造集合A：如果邊(zi,xi)屬于T，我們則把ai選入集合A，否則不把ai選入集合A。這樣一來，ai∈Aai=(zi,xi)∈Ta由上面討論可知，本題中的問題是個NP難問題。給定一個連通圖G(V,E)，我們希望找到一個支撐樹使得樹中的葉結(jié)點最少。例如，下面圖(ii)和(iii)都是圖(i)的支撐樹，分別有4個葉結(jié)點和3個葉結(jié)點，圖(iii)的解較好。請回答以下問題：為本題的優(yōu)化型問題定義一個對應的判斷型問題。證明這個問題是NPC問題。aabcdefg(iii)abcdefg(i)abcdefg(ii)解：(a) 對應的判斷型問題可定義如下： 給定一個連通圖G(V,E)和一個正整數(shù)k，判斷G是否含有一個葉子數(shù)少于等于k的支撐樹。(b) 為證明這個問題是NPC，我們先證明它屬于NP類。我們用的證書是一棵支撐樹的邊的集合Y。下面的偽碼檢驗Y是否是葉子數(shù)少于等于k的支撐樹。Verification-k-Leave-Spanning-Tree(G(V,E),k,Y) //|V|=nV’?V //開始構(gòu)造這個支撐樹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開始作一輪廣度優(yōu)先搜索number-of-leaves?0 //統(tǒng)計葉子個數(shù)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現(xiàn)在證明這個問題是NP難。我們把哈密爾頓路徑問題多項式歸約為這個問題。假定圖G是哈密爾頓路徑問題的一個實例。當我們把哈密爾頓路徑問題多項式歸約到支撐樹時，仍用這個圖G并置k=2。顯然，圖G有一條哈密爾頓路徑當且僅當圖G有一個2個葉子的支撐樹。所以本題中的問題是NP完全問題。假設我們有n個獨立的任務，J1,J2,...,Jn，要從時間t=0開始在兩個同樣的處理器上執(zhí)行。假設Ji(1in)需要Ti秒的時間完成并且一旦開始執(zhí)行，必須不中斷地在同一個處理器上運行直止完成。我們希望找到一個調(diào)度，即任務安排，使這n個任務可以在最短時間內(nèi)完成。例如，如果有3個任務，其執(zhí)行時間分別為T1=4秒,T2=5秒,T3=7秒,那么下面圖示的調(diào)度用9秒鐘可以把它們完成。這個調(diào)度顯然是最好的。請回答下面問題。TT1T2T3處理器1處理器2t=0213456879(a) 為上述調(diào)度問題定義一個對應的判斷型問題。(b) 證明該調(diào)度問題是個NP難問題。解：(a) 對應的判斷型問題可定義如下：假設我們有n個獨立的任務，J1,J2,...,Jn，要從時間t=0開始在兩個同樣的處理器上執(zhí)行。假設Ji(1in)需要Ti秒的時間完成并且一旦開始執(zhí)行，必須不中斷地在同一個處理器上運行直至完成。判斷是否存在一個調(diào)度使這n個任務可以在k秒內(nèi)完成。(b) 我們把集合平分問題多項式歸約為這個問題。假設集合平分問題的一個實例中，S={a1,a2,…,an}是n個正整數(shù)，其和為i=1nai=2m。我們由此構(gòu)造一個調(diào)度問題的實例如下。我們?yōu)槊總€整數(shù)ai構(gòu)造一個對應的獨立任務Ji，并置它的執(zhí)行時間為Ti=ai(1≤i≤n)。另外，置k=m我們用P1和P2分別表示調(diào)度問題中的兩個處理器，也表示調(diào)度給它們執(zhí)行的任務的集合。下面我們證明，如上構(gòu)造的n個任務，J1,J2,...,Jn，可以在P1和P2上在k秒內(nèi)完成當且僅當這個集合S可被平分。假設集合S可被平分，即存在子集AS使得ai∈Aai=ai∈S-Aai=m。那么，我們可設計任務調(diào)度如下：我們把對應于集合A中整數(shù)的任務分配給P1，而把對應于集合S-A中整數(shù)的任務分配給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=如果所構(gòu)造的n個任務，J1,J2,...,Jn，可以在P1和P2上在k秒內(nèi)完成，即Ji∈P1Ti=Ji∈P2Ti=k，那么我們可以把集合S平分如下：A={ai|JiP1(1≤i≤n)}，即把對應于P1所執(zhí)行的任務的整數(shù)選入子集A。這樣，子集A中的整數(shù)之和為ai∈Aai=Ji∈P1Ti=k=m。而子集S–A因此，我們證明了集合平分問題可多項式歸約為本題的調(diào)度問題。因為集合平分問題是個NPC問題，所以本題的調(diào)度問題是NP難。假設計算機中有n個文件，f1,f2,…,fn，需要存入兩張光盤中。這n個文件所需的空間分別是s1,s2,…,sn(以千字節(jié)KB為單位)，而每張光盤的容量都是M(KB)。假設存入一個文件不需要額外的空間開銷，并且所有文件所需的空間總和不超過2M，即i=1nsi2M。我們需要判斷這兩張光盤是否有足夠的空間存入這n個文件。請證明這個判斷解：如果我們把文件fi看為任務Ji，si視為執(zhí)行時間Ti，把二張光盤1和2看為處理器P1和P2，把文件fi存入光盤1看為把任務分配給P1，把文件fi存入光盤2看為把任務分配給P2，那么用類似第14題中的證明可以證明這個判斷問題是個NP難問題，或者把任務調(diào)度問題多項式歸約到這個問題來證明這個判斷問題是個NP難問題。裝箱問題(binpacking)是說有n個物體，O1,O2,…,On，需要裝箱。這n個物體分別有體積si并且滿足0<si￡1(1in)。假定每個箱子的容積是1，我們希望用最少的箱子把它們裝入。我們假定任何一組物體，只要它們的總體積不超過1，都可以裝入一個箱子之中?；卮鹣旅鎲栴}。為這個優(yōu)化型問題定義一個對應的判斷型問題。證明這個判斷型問題是NP難問題。解：(a) 這個對應的判斷型問題可定義如下：有n個物體，O1,O2,…,On，需要裝箱。這n個物體分別有體積si，并且滿足0<si￡1(1in)。假定有k個箱子，而每個箱子的容積是1，并且假定任何一組物體，只要它們的總體積不超過1，都可以裝入一個箱子之中，判斷這n個物體是否可以裝入這k個箱子之中。(b) 我們把集合平分問題多項式歸約到這個裝箱問題。假設集合平分問題的實例中，S={a1,a2,…,an}是n個非負整數(shù)的集合，其和為i=1nai=2m。我們可假定ai≤m(1≤i≤n)，否則S不可平分，那我們只需構(gòu)造一個不可能事件即可，例如讓k=1，s1=0.8,s2=0.8。假定ai≤m(1≤i≤n)，那么我們構(gòu)造一個k=2的裝箱問題如下：為每一個整數(shù)ai(1≤i≤n)，構(gòu)造一個物體Oi，并且賦以體積si=aim≤1。顯然，這是一個多項式時間的轉(zhuǎn)換算法。下面證明，這樣構(gòu)造的(1) 假如構(gòu)造的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中的物體所對應的整數(shù)組成S的子集A，即A={ai(2) 假如集合S可平分，即存在一個子集A，使得ai∈Aai=ai∈S-Aai=m。那么我們可以把A中整數(shù)對應的物體組成集合B1，即B1={Oi|aiA}。因為ai∈Aai=m，所以B1中物體的體積之和為Oi∈B1si=Oi∈B1aim=1mOi∈B因此，我們證明了集合平分問題可多項式歸約為本題的裝箱問題。因為集合平分問題是個NPC問題，所以本題的裝箱問題是NP難。(兩條點不相交路徑問題) 證明下面的判斷型問題是NP難問題：給定一個加權(quán)的有向圖G(V，E)和V中兩個頂點s和t，以及正數(shù)k，判斷圖G是否有兩條頂點不相交的從s到t的簡單路徑使得每條長度均不大于k？這里“不相交”是指除了起點s和終點t以外，兩條路徑上所有頂點都不同。這個問題在網(wǎng)絡的路由問題中有實際應用的背景。提示：把集合平分問題多項式歸約到這個問題。假設集合平分問題的一個實例中，S={a1,a2,…,an}是n個非負整數(shù)，其和為i=1nai解：我們把集合平分問題多項式歸約到這個問題。假設集合平分問題的一個實例中，S={a1,a2,…,an}是n個非負整數(shù)，其和為i=1nai=2m。我們構(gòu)造一加權(quán)的有向圖G如提示中圖所示，并置k=m。顯然，這是一個多項式時間的轉(zhuǎn)換。現(xiàn)在證明，S可平分當且僅當圖G中有兩條頂點不相交的從s到t假如S可平分，即存在一個子集A，使得ai∈Aai=ai∈S-Aai=m。那么，我們可以構(gòu)造一條對應集合A中整數(shù)的路徑P1如下：從s開始到頂點u1，然后，如果a1A，那么P1到達的下一個頂點是v2，否則是u2。往下，類似地決定P1要到達的下一個點。原則是，如果P1到達的當前頂點是ui或vi時(i1)，如果aiA，那么下一個到達的點是vi+1，否則是ui+1。當?shù)竭_頂點un+1或者vn+1后，下一步到達終點t。因為從i=1開始，每一條到達vi+1的邊有權(quán)ai，而到達ui+1的邊的權(quán)為0，因此這條路徑的長度為w(P1)=vi+1∈P1ai=ai∈Aai=m=k?，F(xiàn)在我們構(gòu)造另一條路徑P2如下：從s開始到頂點v1。然后，決定P2要到達的下一個點。原則是，如果P2到達的當前頂點是ui或vi時(i1)，如果aiS-A，那么下一個到達的點是vi+1，否則是ui+1。當?shù)竭_頂點un+1或者vn+1后，下一步到達終點t。顯然，如果P1經(jīng)過頂點ui+1那么P2則經(jīng)過頂點vi+1，反之，如果P1經(jīng)過頂點vi+1那么P2則經(jīng)過頂點ui+1，所以P1和P2是兩條頂點不相交的從s到t的簡單路徑。另外，P假如所構(gòu)造的圖G有兩條頂點不相交的從s到t的簡單路徑，P1和P2，每條長度不大于k。不失一般性，可假定P1經(jīng)過點u1而P2經(jīng)過點v1。我們可如下平分S：如果P1經(jīng)過點vi+1(1in)，則把ai選入子集A中。這樣一來，子集A中整數(shù)和為ai∈Aai=vi+1∈P1ai=w(P1)k=m。類似的，如果P2經(jīng)過點vi+1，則把ai選入子集S–A中。子集S-A中整數(shù)和為ai∈S-Aai=vi+1∈P2ai=w(P2)k=m。因為頂點vi+1(1in)必定被兩條路徑之一經(jīng)過，所以有w(P1)+w(P2)=i=1nai=2m。因此，w(P1)=因此，我們證明了集合平分問題可多項式歸約為本題的頂點不相交的路徑問題。因為集合平分問題是個NPC問題，所以本題的頂點不相交的路徑問題是NP難。0/1背包的優(yōu)化問題(0/1knapsackoptimizationproblem)定義如下：設U={O1,O2,…,On}是n個物體的集合。物體Oi的體積和它的價值分別為wi>0和vi>0(1￡i￡n)。另外，有一個容積為W的背包。任意一組物體，只要它們的體積總和不超過W就可以裝入這個背包。我們希望從集合U中選出一個子集Q使子集中物體的體積總和不超過W，但是它的總價值最大。我們稱這個問題為0/1背包的優(yōu)化問題是因為它不允許一個物體被切下一部分來放入背包。請回答下面問題。為0/1背包的優(yōu)化問題定義一個對應的判斷型問題。證明這個0/1背包問題是NP難問題。解：(a) 0/1背包的判斷型問題可定義如下：設U={O1,O2,…,On}是n個物體的集合。物體Oi的體積和它的價值分別為wi>0和vi>0(1￡i￡n)。另外，給定一個容積為W的背包和一個稱為“價值期望”的正數(shù)k，判斷是否存在U的一個子集Q使得子集Q中所有物體的體積總和不超過W而它們的價值總和大于等于k？(b) 我們把集合平分問題多項式歸約為這個問題。假設集合平分問題的一個實例中，集合S={a1,a2,…,an}含n個非負整數(shù)，其和為i=1nai=2m。我們構(gòu)造一個0/1背包問題的實例如下：對應S中每個整數(shù)ai(1￡i￡n)，構(gòu)造一個物體Oi并賦以wi=vi=ai。這n個物體組成集合U。另外，置這個背包的容積為W=m和價值期望k=m。顯然，這個構(gòu)造可在多項式時間內(nèi)完成。下面證明，這樣構(gòu)造的0/1背包問題有yes(1) 假設集合S可平分，即存在一個子集A，使得ai∈Aai=ai∈S-Aai=m。那么，我們把子集A中整數(shù)所對應的物體選入子集Q中，即Q={Oi|aiA}。這樣選出的子集Q中所有物體的總的體積和是V=Oi∈Qwi=ai∈Aai=m=W，而它們的總價值為Z=Oi∈Q(2) 假設在構(gòu)造的0/1背包問題中，存在一個物體的集合Q使得它們的總體積小于等于背包容積W，而它們的總價值大于等于價值期望k。那么，我們可以在集合S找出一個子集A如下：如果物體Oi被選在集合Q中，那么Oi對應的整數(shù)ai屬于子集A，即A={ai|OiQ}。這樣的話，A中所有整數(shù)之和是ai∈Aai=Oi∈QwiW=m。但由于Q中物體的總值價大于等于價值期望k，我們有ai∈Aai=Oi∈Qvik=m，因此有a因此，我們證明了集合平分問題可多項式歸約為本題的0/1背包的問題。因為集合平分問題是個NPC問題，所以本題的0/1背包的問題是NP難。(推廣的貨郎擔問題）假定G(V,E)是一個加權(quán)的連通圖，其中每條邊的權(quán)是一個非負實數(shù)。推廣的貨郎擔問題就是在G中找一條經(jīng)過每個頂點至少一次的回路C，使得它的所有邊的總權(quán)值最小。如果我們把每個頂點看作一個城市，把一條邊看作一條航線，而邊上的權(quán)看為航線距離的話，那么這個回路就是一個貨郎擔周游每個城市后回到原地的路線圖，而且該路線圖的總路程最小。注意，這個問題與原貨郎擔問題的不同在于它不要求G是個完全圖并允許貨郎擔經(jīng)過一個城市多次，只要總路程最小即可。另外要注意的是，一條經(jīng)過每個點正好一次的回路不一定比經(jīng)過多次的這條推廣的貨郎擔回路的總路程短。下面的圖給出了一個例子。aa一1111111bcdef100100經(jīng)過每個頂點正好一次的回路，<a,b,f,e,d,c,a>,的總權(quán)值為105。推廣的貨郎擔回路，<a,b,f,e,a,d,c,a>,的總權(quán)值為7。顯然，一個連通圖一定有經(jīng)過每個點的回路，但不一定是簡單回路。請證明，判斷一個連通圖G是否有總長小于等于k的推廣的貨郎擔回路是個NP難問題，這里k是一個給定的正數(shù)。解：我們把哈密爾頓回路問題多項式歸約到這個問題。設圖G(V,E)是哈密爾頓回路問題的一個實例。如果G(V,E)是個非連通圖，則不存在哈密爾頓回路，我們可隨便構(gòu)造一個無解的推廣的貨郎擔問題即可，例如構(gòu)造一個有3個點的三角形并使每條邊權(quán)值為2，但置k=1。所以，我們可假定G(V,E)是個連通圖。我們在構(gòu)造對應的推廣的貨郎擔問題的圖G’(V’,E’)時，用同樣的頂點集合和邊的集合，即V’=V,E’=E。另外，賦以每條邊的權(quán)值為1，并置k=|V|?？梢宰C明圖G有一條哈密爾頓回路當且僅當G’有一條推廣的貨郎擔回路并且總權(quán)值小于等于k。如果圖G有一條哈密爾頓回路，那么，在G’中這條回路對應于一條推廣的貨郎擔回路。由于每條邊權(quán)值為1，那么這條回路總權(quán)值為|V|=k。如果圖G’有一條推廣的貨郎擔回路并且總權(quán)值小于等于k，由于每條邊權(quán)值為1，那么這條回路最多有k=|V|條邊。又因為每個頂點必須經(jīng)過至少一次，那么這條回路必定至少有|V|條邊。但是，這條回路的邊數(shù)又不能大于|V|=k條邊，否則總權(quán)值會大于k。因此，這個回路必定經(jīng)過每個點正好一次。那么，這個回路對應G中的一條哈密爾頓回路。因此，我們證明了，哈密爾頓回路問題可多項式歸約到這個推廣的貨郎擔問題。因為哈密爾頓回路問題是個NPC問題，所以本題的推廣的貨郎擔問題是個NP難問題。我們知道圖的k-著色問題是個NPC問題。其實，圖的3-著色問題就已經(jīng)是個NP難問題了。下面，我們把3-SAT問題多項式歸約為這個問題。假設是一個3-CNF的表達式，它含有n個變量，x1,x2,…,xn，和m個子句，=C1C2…Cm。我們構(gòu)造一個3-著色的實例，也就是一個圖G=(V,E)如下：我們?yōu)楸磉_式中每一個變量xi和它的非xi各構(gòu)造一個頂點，并標以xi和xi。構(gòu)造3個特殊的頂點并分別標以真、假、空，并把它們聯(lián)結(jié)為一個三角形。為每一個子句，Cj(1jm)，如下圖(a)構(gòu)造5個新頂點，a,b,c,d,e。然后，把Cj中3個文字對應的3個頂點，5個新頂點，以及頂點“真”，一共9個頂點按下面圖(a)聯(lián)成一個子圖。圖中x、y、z表示子句Cj中的文字。(a)(a)(b)xyz真空假zxyz真abcdeabcde如圖(b)所示，把每一對點xi和xi(1jn)，以及特殊點“空”之間連成一個三角形。為清晰起見，圖(b)中只顯示了一對點z和z。實際構(gòu)造時應為每一個變量xi構(gòu)造一個三角形?，F(xiàn)在，圖構(gòu)造好了，證明這是個多項式歸約，所以3-著色問題是個NP難問題。解：以上構(gòu)造顯然只需多項式時間。我們只需證明，這樣構(gòu)造的圖可以3-著色當且僅當表達式可以被滿足。證明如下：假設構(gòu)造的圖可以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) 假設表達式可以被滿足，那么我們對構(gòu)造的圖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，且都是以整數(shù)公斤為單位。我們希望把這些卡車分成三組，各組負責送一個地方，并且使得三個地方獲得相等重量的煤。我們假定煤礦有足夠的煤供運輸并且每輛車必須滿載。請證明判斷這個分組問題是否有解是個NP難問題。證明：我們把集合平分問題歸約到這個問題。設集合平分問題中集合是S={a1，a2，…，an}(n>2)。我們構(gòu)造分組問題如下：計算M=i=1n可假定M是個偶數(shù)，M=2k。否則，集合劃分問題無解，我們可以構(gòu)造一個無解的運輸分組問題。構(gòu)造(n+1)部卡車，其中頭n部卡車的裝載量分別是c1=a1，c2=a2，…，cn=an，第(n+1)部卡車有裝載量k=M/2。顯然，集合劃分問題有解當且僅當這個構(gòu)造的分組問題有解。因為構(gòu)造這分組問題只需多項式時間，所以集合劃分問題可多項式歸約到這個卡車分組問題。所以這個卡車分組問題是個NP難問題。在第9章習題14中我們討論過2-樹支撐森林的問題。這里我們考慮最小-最大(min-max)2-樹支撐森林的問題。給定一個加權(quán)的連通圖G(V,E)，最小-最大(min-max)2-樹支撐森林的問題是找出一個2-樹支撐森林，T1和T2，使得有較大權(quán)值的樹的權(quán)，即max{W(T1),W(T2)}，在所有2-樹支撐森林中是最小的。回答以下問題。定義與這個優(yōu)化型問題對應的一個判斷型問題。證明這個判斷型問題是個NP難問題。解：(a) 以下是對應的一個判斷型問題：給定一個加權(quán)的連通圖G(V,E)和一個實數(shù)k，判斷是否存在一個2-樹支撐森林，T1和T2，使得max{W(T1),W(T2)}k?(b) 我們把集合平分問題多項式歸約到這個問題。假設集合平分問題的一個實例中，S={a1,a2,…,an}是n個正整數(shù)的集合，其和為i=1nai=2m。我們假設aim(1) 構(gòu)建兩個頂點，p和q。(2) 為每一個數(shù)字ai(1≤i≤n)，構(gòu)建一個頂點vi和兩條邊，(p,vi)和(q,vi)。它們的權(quán)值為w(p,vi)=w(q,vi)=ai。(3) 置k=m。顯然，這個構(gòu)造算法是個多項式算法，下圖給出一個例子。集合集合S={5,8,11,7,6,9,2}總和2m=48v1v2v3v4v5v6v75588111177669922pq由集合S構(gòu)造的圖G，k=24 現(xiàn)在我們證明，所構(gòu)造的圖G有一個2-樹支撐森林，T1和T2，使得max{W(T1),W(T2)}k當且僅當集合S可平分。假設集合S可平分為A和S-A，使得ai∈Aai=ai∈S-Aai=m。我們可以如下構(gòu)建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òu)造的有向圖G有一個2-樹支撐森林，T1和T2，使得max{W(T1),W(T2)}k，那么集合S可如下平分為A和S-A。我們分三種情況：(2.1)點p和q同屬T1。這時，T2中的點不可以與p和q相鄰，只能以孤立點出現(xiàn)(度數(shù)為0)。因此，T2沒有邊，且只含一個點。這時，在T1中的每個點vi(1≤i≤n)必須與點p或點q相鄰。另外，至少有一個點vi(1≤i≤n)與點p和點q都相鄰，否則點p和點q不連通。這使得W(T1)>m=k，所以這種情況不可能出現(xiàn)。(2.2)點p和q同屬T2。與情況(2.1)類似，這種情況不可能出現(xiàn)。(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的數(shù)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這一段可以安排活動。假設時間單位都以分鐘計算。現(xiàn)在有n個活動，a1，a2，…，an，申請使用禮堂。每個活動ai(1in)需要連續(xù)占用禮堂ti分鐘，并且必須安排在時刻si(0≤si)或早于時刻si開始。當然，在任何時刻，只能允許一個活動占用禮堂，并且所有被選取的活動要在時刻T之前完成。我們希望選出一個活動的集合A使得禮堂被使用的時間，即ai∈At定義與這個優(yōu)化型問題對應的一個判斷型問題。證明這個判斷型問題是個NP難問題。解：(a) 以下是對應的一個判斷型問題：假設禮堂從時刻t=0到t=T>0這一段可以安排活動。假設時間單位都以分鐘計算?，F(xiàn)在有n個活動，a1，a2，…，an，申請使用禮堂。每個活動ai(1in)需要連續(xù)占用禮堂ti分鐘，并且要求在si(0)或早于si開始。被選中的活動必須能安排在t=T之前完成。在任何時刻，只能允許一個活動占用禮堂。請判斷是否存在一個滿足上述要求的互相兼容的活動的集合A使得禮堂被使用的時間大于或等于k，即ai∈Ati(b) 我們把子集和問題多項式歸約到這個問題。假設子集和問題的一個實例中，S={v1,v2,…,vn}是n個正整數(shù)的集合，另有一個目標值t>0。子集和問題要求判斷是否有一個S的子集V,VS，使得vi∈Vvi=t。我們把這個(1)置T=t(目標值)。禮堂從時刻t=0到T>0這一段可以安排活動。(2)為每一個S中數(shù)vi(1≤i≤n)，構(gòu)建一個活動ai使得ti=vi，si=T-ti。(3)置k=t。顯然這個轉(zhuǎn)換只需多項式時間。下面證明，如果集合S有子集V,VS，使得Vi∈Vvi=t，那么，所構(gòu)造的活動中存在一個集合A假設集合S有子集V,VS，使得vi∈Vvi=t=T。我們可以如下選出活動的集合A：如果數(shù)字vi在子集V中，viV，那么，對應于vi所構(gòu)造的活動ai入選，即A={ai|viV}。因為vi∈Vvi=t，而ti=vi，故有ai∈Ati=vi∈Vvi=T=t=k。又因為si=T-ti和假設所構(gòu)造的活動中存在一個集合A使得禮堂被使用的時間大于或等于k，ai∈Ati≥k。我們可以如下找出子集V：如果aiA，那么我們從集合S中把構(gòu)造ai時所用的數(shù)字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安排活動。假設時間單位都以分鐘計算?，F(xiàn)在有n個活動，a1，a2，…，an，要求使用一個禮堂，兩個禮堂中任一個都行?；顒觓i(1in)必須安排在時刻si(0≤si)或早于時刻si開始，但一旦開始，需要連續(xù)占用該禮堂ti分鐘。當然，在任何時刻，任一個禮堂只能允許一個活動占用。我們希望選出一個有最多活動的集合A使得這些活動可以互相兼容地使用這兩個禮堂?；卮鹨韵聠栴}。定義與這個優(yōu)化型問題對應的一個判斷型問題。證明這個判斷型問題是個NP難問題。解：(a)對應的一個判斷型問題可定義如下：假設我們有兩個禮堂可以從時刻t=0安排活動。假設時間單位都以分鐘計算。現(xiàn)在有n個活動，a1，a2，…，an，要求使用一個禮堂，兩個禮堂中任一個都行。活動ai(1in)可以安排在時刻si(0≤si)或早于時刻si開始，但一旦開始，需要連續(xù)占用該禮堂ti分鐘。當然，在任何時刻，任一個禮堂只能允許一個活動占用。請判斷，我們能否選出有至少k個活動的集合A使得這些活動可以互相兼容地使用這兩個禮堂？這里，kn是一個正整數(shù)。(b)我們把集合平分問題多項式歸約到這個活動選擇問題。假設集合平分問題的一個實例中，S={v1,v2,…,vn}是n個正整數(shù)的集合，其和Vi∈Svi=2m(m是正整數(shù))。我們假設vi為S中每一個數(shù)vi構(gòu)造一個活動ai，它需要占用禮堂的時間是ti=vi，它的開始時刻是si=m-vi或早于si。置k=n。這顯然是個多項式時間的轉(zhuǎn)換算法。我們證明集合S可平分當且僅當我們構(gòu)造的n個活動可以互相兼容地使用這兩個禮堂。假設集合S可平分為子集A和S-A，使得vi∈Avi=vi∈S-Avi=m。那么，我們可以為第一個禮堂選擇活動如下：H1={ai|viA}，也就是選取由子集A中數(shù)字所構(gòu)造的所有活動。因為ti=vi，我們有ti∈H1ti=vi∈Avi=m。因為它們的開始時刻只要是si=m-vi或更早即可，所以我們只需把它們一個接一個地安排在第一個禮堂，便可以互相兼容地使用這個禮堂。同理，其余的活動是由集合S-A中數(shù)字所構(gòu)造的活動，我們可以把它們安排在第二個禮堂，H2={ai|viS-A}。因為假設我們構(gòu)造的n個活動可以互相兼容地使用這兩個禮堂。設H1是安排在第一個禮堂的活動，H2是安排在第二個禮堂的活動。那么，我們可以平分集合S如下：A={vi|aiH1}，也就是構(gòu)造H1中活動所用的數(shù)字的集合。顯然，由余下的數(shù)字S-A構(gòu)造的活動必定安排在第二個禮堂，即S-A={vi|aiH2}。因為ti∈H1ti≤m，ti∈H2ti≤m，而ti∈H1ti+ti∈H2ti=vi∈Avi+v∈S-Avi=vi∈Svi=2