圖論講義第1章-圖的概念

圖論與網絡流理論(GraphTheoryandNetworkFlowTheory高隨祥中科院研究生院專業(yè)基礎課學時/學分:60/3本課程適合基礎數(shù)學、應用數(shù)學、計算數(shù)學、運籌學與控制論、概率論與數(shù)理統(tǒng)計各專業(yè)的碩士學位研究生作為專業(yè)基礎課,也可供物理學、化學、天文學、地學、生物科學、計算機科學與技術、計算機軟件、管理科學與工程以及通信、信號等學科專業(yè)的碩士研究生選修。主要講授圖論與網絡流理論的基本概念、方法和定理,介紹該領域重要的問題以及典型的算法,展示圖論與網絡流模型及方法的廣泛應用。為學習者將來從事有關方面的理論研究打下基礎,也為進行應用性研究提供一種有力的工具。內容提要第一章圖的基本概念圖的基本概念;二部圖及其性質;圖的同構;關聯(lián)矩陣與鄰接矩陣。路、圈與連通圖;最短路問題。樹及其基本性質;生成樹;最小生成樹。第二章圖的連通性割點、割邊和塊;邊連通與點連通;連通度;Whitney定理;可靠通信網絡的設計。第三章匹配問題匹配與最大匹配;完美匹配;二部圖的最大匹配;指派問題與最大權匹配。第四章歐拉圖與哈密爾頓圖歐拉圖;中國郵遞員問題;哈密爾頓圖;旅行商問題。第五章支配集、獨立集、覆蓋集與團支配集、點獨立集、點覆蓋集、邊覆蓋集與團的概念及其求法。第六章圖的著色問題點著色;邊著色;平面圖;四色猜想;色多項式;色數(shù)的應用。第七章網絡流理論有向圖;網絡與網絡流的基本概念;最大流最小割定理;求最大流的標號算法;最小費用流問題;最小費用最大流;網絡流理論的應用。主要參考書[1]J.A.BondyandU.S.Murty,Graphtheorywithapplications,1976,有中譯本(吳望名等譯。[2]B.Bollobas,Moderngraphtheory(現(xiàn)代圖論,科學出版社,2001。[3]蔣長浩,圖論與網絡流,中國林業(yè)出版社,2001。[4]田豐,馬仲蕃,圖與網絡流理論,科學出版社,1987。[5]徐俊明,圖論及其應用,中國科技大學出版社,1998。[6]王樹禾,圖論及其算法,中國科技大學出版社,1994。[7]殷劍宏,吳開亞,圖論及其算法,中國科技大學出版社,2003。考核方式:平時成績+期末閉卷筆試第一章圖的基本概念§1.1圖的基本概念1.圖(graph:一集元素及它們之間的某種關系。具體地說,圖是一個二元組,(EV,其中集合V稱為頂點集,集合E是V中元素組成的某些無序對的集合,稱為邊集。例1.1.1,(EVG=,其中圖的頂點集中的元素稱為頂點,邊集中的元素稱為邊。在本書中邊e=(u,v也常寫為e=uv,頂點u和v稱為邊e的端點,反過來也稱邊e連接頂點u和v。圖G的頂點數(shù)目||V稱為圖G的階,邊的數(shù)目||E稱為圖G的邊數(shù)。本書中一般將圖的邊數(shù)記為ε,將圖的階記為υ。2.圖的圖示通常,圖的頂點可用平面上的一個點來表示,邊可用平面上的線段來表示(直的或曲的。這樣畫出的平面圖形稱為圖的圖示。注:(1由于表示頂點的平面點的位置的任意性,同一個圖可以畫出形狀迥異的很多圖示。比如下圖是例1.1.1中圖的另一個圖示:(2圖的圖示直觀易懂,因此以后一般說到一個圖,我們總是畫出它的一個圖示來表示。3.一些術語和概念設G=(V,E是一個圖,下述概念中頂點均取自V,邊均取自E。(1點與邊的關聯(lián)(incident:如果在圖G中點v是邊e的一個端點,則稱點v與邊e在圖G中相關聯(lián)。(2點與點的相鄰(adjacent:如果圖上兩點u,v被同一條邊相連,則稱u,v在圖G中相鄰。(3邊與邊的相鄰:如果圖G中兩條邊有至少一個公共端點,則稱這兩條邊在圖G中相鄰。(4環(huán)邊(loop:圖中兩端點重合的邊稱為環(huán)邊。(5重邊(multiedge:設u和v是圖G的頂點,圖G中連接u和v的兩條或兩條以上的邊稱為圖G中u、v間的重邊。(6簡單圖(simplegraph:既無環(huán)邊也無重邊的圖稱為簡單圖。(7完全圖(completegraph:任意兩點間都有一條邊的簡單圖稱為完全圖,n階完全圖記為Kn.(8平凡圖(trivialgraph:只有一個頂點,沒有邊的圖。(9空圖(emptygraph:邊集為空的圖。(10零圖(nullgraph:頂點集為空的圖。(11頂點v的度(degree:圖G中頂點v所關聯(lián)的邊的數(shù)目(環(huán)邊計兩次稱為頂點v的度,記為dG(v或d(v。(12圖G的最大度:}(|(max{(GVvvdGG∈=Δ;圖G的最小度:}(|(min{(GVvvdGG∈=δ。(13正則圖(regulargraph:每個頂點的度都相等的圖。(14圖的補圖(complement:設G是一個圖,以(GV為頂點集,以}(,(|,{(GEyxyx?為邊集的圖稱為G的補圖,記為G。定理1.1.1對任何圖G,都有((2vVGdvε∈=∑。證明:按每個頂點的度來計數(shù)邊,每條邊恰數(shù)了兩次。推論1.1.1任何圖中,奇度頂點的個數(shù)總是偶數(shù)(包括0。證明留作練習。4.子圖子圖(subgraph:對圖G和H,如果((GVHV?且((GEHE?,則稱圖H是圖G的子圖,記為GH?。生成子圖(spanningsubgraph:若H是G的子圖且((VHVG=,則稱H是G的生成子圖。點導出子圖(inducedsubgraph:設G是一個圖,(GVV?′。以V′為頂點集,以G中兩端點均屬于V′的所有邊作為邊集所組成的子圖,稱為G的由頂點集V′導出的子圖,簡稱為G的點導出子圖,記為][VG′.邊導出子圖(edge-inducedsubgraph:設G是一個圖,(GEE?′。以E′為邊集,以E′中邊的所有端點作為頂點集所組成的子圖,稱為G的由邊集E′導出的子圖,簡稱為G的邊導出子圖,記為][EG′。設(GVV?′,(GEE?′,今后經常用GV′?表示從圖G中刪除頂點子集V′(連同它們關聯(lián)的邊一起刪去所獲得的子圖,用GE′?表示從圖G中刪除邊子集E′(但不刪除它們的端點所獲得的子圖。特別地,對頂點v和邊e,常用Gv?表示G{}v?,Ge?表示{}Ge?圖G的一個頂點子集E′。5.路和圈途徑(walk:圖G中一個點邊交替出現(xiàn)的序列kkiiiiiiveevevw2110=稱為圖G的一條途徑,其中0iv、kiv分別稱為途徑w的起點和終點,w上其余頂點稱為中途點。跡(trail:圖G中邊不重復的途徑稱為跡。路(path:圖G中頂點不重復的跡稱為路。(注:簡單圖中的路可以完全用頂點來表示,kiiivvvP10=閉途徑(closedwalk:圖G中起點和終點相同的途徑稱為閉途徑。閉跡(closedtrail:圖G中邊不重復的閉途徑稱為閉跡,也稱為回路(circuit。圈(cycle:中途點不重復的閉跡稱為圈。注:(1途徑(閉途徑、跡(閉跡、路(圈上所含的邊的數(shù)目稱為它的長度。(2簡單圖G中長度為奇數(shù)和偶數(shù)的圈分別稱為奇圈(oddcycle和偶圈(evencycle。(3對任意(,GVyx∈,從x到y(tǒng)的具有最小長度的路稱為x到y(tǒng)的最短路(shortestpath,其長度稱為x到y(tǒng)的距離(distance,記為,(yxdG。(4簡單圖G中最短圈的長度稱為圖G的圍長(girth,最長圈的長度稱為圖G的周長(circumference。例1.1.2設G是一個簡單圖,若2(≥Gδ,則G中必含有圈。證明:設G中的最長路為kvvvP10=。因2(0≥vd,故存在與1v相異的頂點v與0v相鄰。若Pv?,則得到比P更長的路,這與P的取法矛盾。因此必定Pv∈,從而G中有圈。證畢。例1.1.3設G是簡單圖,若3(≥Gδ,則G必有偶圈。證明:設kvvvP10=是G的最長路。因為3(0≥vd,所以存在兩個與1v相異的頂點vv′′′,與0v相鄰。vv′′′,必都在路P上,否則會得到比P更長的路。無妨設(,,jivvvvji<=′′=′。若ji,中有奇數(shù),比如i是奇數(shù),則路P上0v到iv的一段與邊ivv0構成一個偶圈;若ji,都是偶數(shù),則路P上iv到jv的一段與邊ivv0及jvv0構成一個偶圈。證畢。例1.1.4設G是簡單圖,若3(≥Gδ,則G中各個圈長的最大公因數(shù)是1或2。證明:由上例知,G中有長分別為1,1++ji和2+?ij的圈。若1,1++ji,2+?ij三數(shù)有公因數(shù)2>m,則|(mji?,于是2|m,這是不可能的。因此1,1++ji,2+?ij三數(shù)的公因數(shù)必不超過2。從而各個圈長的最大公因數(shù)是1或2。證畢。6.二部圖二部圖(bipartitegraph:若圖G的頂點集可劃分為兩個非空子集X和Y,使得G的任一條邊都有一個端點在X中,另一個端點在Y中,則稱G為二部圖(或偶圖,記為G=,(EYX∪,,(YX稱為G的一個頂點二劃分。完全二部圖(completebipartitegraph:在二部圖,(EYXG∪=中,若X的每個頂點與Y的每個頂點有邊連接,則稱G為完全二部圖;若mX=||,nY=||,則記此完全二部圖為nmK,。定理1.1.2一個圖是二部圖當且僅當它不含奇圈。證明:必要性:設010vvvvCk=是二部圖,(EYXG∪=的一個圈。無妨設Xv∈0,由二部圖的定義知,Yv∈1,Xv∈2,,一般地,Xvi∈2,Yvi∈+12,(,1,0=i。又因Xv∈0,故Yvk∈,因而k是奇數(shù)。注意到圈C上共有1+k條邊,因此是偶圈。充分性:設G不含奇圈。取(GVu∈,令},(|({oddvudGVvX=∈=,},(|({evenvudGVvY=∈=。任取一條邊21vve=,欲證21,vv分屬于X和Y。設P,Q分別是u到21,vv的最短路。(1如果12vvQP+=或21vvPQ+=,則21,vv到u的距離奇偶性相反,21,vv分屬于X和Y。(2否則,設u′是P與Q的最后一個公共頂點,因P的,(uu′段和Q的,(uu′段都是u到u′的最短路,故這兩段長度相等。假如P,Q的奇偶性相同,則P的,(1vu′段和Q的,(2vu′段奇偶性相同,這兩段與邊e構成一個奇圈,與定理條件矛盾?？梢奝,Q的奇偶性不同,從而21,vv分屬于X和Y。這便證明了G是一個二部圖。證畢。例1.1.5判斷下列圖是不是二部圖。Peterson圖解:Herschel圖的一個頂點二劃分如下:可見HerschelPeterson圖中含有奇圈,因此不是二部圖。7.連通性圖中兩點的連通:如果在圖G中u,v兩點間有路相通,則稱頂點u,v在圖G中連通。連通圖(connectedgraph:若圖G中任二頂點都連通,則稱圖G是連通圖。圖的連通分支(connectedbranch,component:若圖G的頂點集V(G可劃分為若干非空子集ωVVV,,,21,使得兩頂點屬于同一子集當且僅當它們在G中連通,則稱每個子圖][iVG為圖G的一個連通分支(ω,,2,1=i。注:(1圖G的連通分支是G的一個極大連通子圖。(2圖G連通當且僅當1=ω。例1.1.6設有2n個電話交換臺,每個臺與至少n個臺有直通線路,則該交換系統(tǒng)中任二臺均可實現(xiàn)通話。證明:構造圖G如下:以交換臺作為頂點,兩頂點間連邊當且僅當對應的兩臺間有直通線路。問題化為:已知圖G有2n個頂點,且nG≥(δ,求證G連通。事實上,假如G不連通,則至少有一個連通分支的頂點數(shù)不超過n。在此連通分支中,頂點的度至多是1?n。這與nG≥(δ矛盾。證畢。例1.1.7若圖中只有兩個奇度頂點,則它們必連通。證明:用反證法。假如u與v不連通,則它們必分屬于不同的連通分支。將每個分支看成一個圖時,其中只有一個奇度頂點。這與推論1.1.1矛盾。證畢。8.圖的同構我們已經知道,同一個圖可以有不同形狀的圖示。反過來,兩個不同的圖也可以有形狀相同的圖示。比如:易見1G和2G的頂點及邊之間都一一對應,且連接關系完全相同,只是頂點和邊的名稱不同而已。這樣的兩個圖稱為是同構的(isomorphic。從數(shù)學上看,同構的兩個圖,其頂點間可建立一一對應,邊之間也能建立一一對應,且若一圖的兩點間有邊,則在另一圖中對應的兩點間有對應的邊。嚴格的數(shù)學定義如下。定義1.1.1對兩個圖(,((GEGVG=與(,((HEHVH=,如果存在兩個一一映射:((:HVGV→α,((:HEGE→β,使得對任意(,(GEvue∈=,都有((,((HEvu∈αα且=(eβ(,((vuαα,則稱圖G與H同構,記為HG?。圖的同構關系是一種等價關系(即滿足反身性、對稱性、傳遞性,這種等價關系將υ階圖分成若干等價類,彼此同構的圖屬于同一類。同一個等價類中的圖有相同的結構,差別僅在于頂點和邊的名稱不同。由于人們關心的是圖的結構,因此,通常將同構圖類中的所有圖看成同一個圖,而不在乎它們頂點和邊的名稱以及它們的圖示畫法。在圖的圖示中,不給頂點和邊標定名稱的圖稱為非標定圖,否則稱為標定圖。非標定圖實際上就是一個同構圖類的代表。在不致誤解的情況下,我們也往往不嚴格區(qū)分標定圖與非標定圖。目前尚無簡便的方法判別兩個圖是否同構,特別是當圖的頂點數(shù)較大時,判斷兩個圖是否同構是一件很困難的事情。兩圖同構,首先它們的階必須相等,邊數(shù)必須相等;其次要有相同的環(huán)邊、重邊及圈的狀態(tài);還應保持頂點的度,即在同構映射下相對應的頂點必須有相同的度。這些都是兩圖同構的必要條件,可用來判斷兩圖不同構。為判定兩圖同構,一般要按定義構造出兩圖頂點間的一一映射,然后檢驗它是否保持鄰接關系。有時也可根據(jù)圖的特點使用特殊方法。解:圖G1和G2是同構的。事實上,定義它們頂點間的映射f,分別將頂點v1,v2,v3,v4,v5,v6映射到u1,u3,u5,u2,u4,u6,顯然這是G1到G2的一個一一映射,且容易驗證它保持頂點間的相鄰關系。圖G2和G3也是同構的。事實上,定義它們頂點間的映射g,分別將頂點u1,u2,u3,u4,u5,u6映射到w1,w2,w3,w4,w5,w6,顯然這是G2到G3的一個一一映射,且容易驗證它保持頂點間的相鄰關系。圖G3和G4不同構,因為G4含有三角形(即子圖K3,但G3不含。注:(1G1、G2、G3的同構性還可以通過它們的二部圖特性來證明?？梢詸z驗,它們都是完全二部圖K3,3。(2容易證明,兩個圖G和H同構當且僅當它們的補圖GH、同構。利用這一結論,也可以較簡便地判定G1、G2、G3的同構性,事實上,G1、G2、G3的補圖都是兩個不相交的C3(長為3的圈,因此同構。而G4的補圖是C6,故G4與前三個圖不同構。關于圖的同構有兩個猜想至今尚未解決。猜想1(Ulam重構猜想,1929設G與H是兩個圖,|V(G|=|V(H|,V(G={u1,u2,???,un},V(H={v1,v2,???,vn}。若對{1,2,,}in?∈,都有iiGuHv???,則GH?。其中iGv?表示將vi以及與vi關聯(lián)的邊都從G中刪除后所得之圖,iHv?類似。猜想2設G與H都是至少有四條邊的圖,若存在一一映射:((EGEH?→,使得對(eEG?∈,都有(GeHe????,則GH?。有關圖的重構問題的更多內容可參看:[1]C.St.J.A.Nash-Williams,Thereconstructionproblem,inSelectedTopicsinGraphTheory(L.W.BeinekeandR.J.Wilsoneds.,AcademicPress,London,(1978205-236.[2]W.T.Tutte,GraphTheory,CambridgeUniversityPress,(2001115-124.(影印版:圖論,機械工業(yè)出版社,2004.§1.2最短路問題一、賦權圖給圖G的每條邊e賦以一個實數(shù)w(e,稱為邊e的權。每條邊都賦有權的圖稱為賦權圖。權在不同的問題中會有不同的含義。例如交通網絡中,權可能表示運費、里程或道路的造價等。設H是賦權圖G的一個子圖,H的權定義為(HW=∑∈((HEeew,特別地,對G中一條路P,其權為(PW=∑∈((PEeew。二、最短路問題最短路問題:給定賦權圖G及G中兩點u,v,求u到v的具有最小權的路(稱為u到v的最短路。注:賦權圖中路的權也稱為路的長,最短(u,v路的長也稱為u,v間的距離,記為d(u,v。最短路問題是一個優(yōu)化問題,屬于網絡優(yōu)化和組合優(yōu)化的范疇。對這種優(yōu)化問題的解答一般是一個算法。最短路問題有很多算法,其中最基本的一個是Dijkstra算法。三、Dijkstra算法1.算法思想設賦權圖G中所有邊都具有非負權,Dijkstra算法的目標是求出G中某個指定頂點0v到其它所有點的最短路。它依據(jù)的基本原理是:若路011kkPvvvv?=是從0v到kv的最短路,則011kPvvv?′=必是從0v到1kv?的最短路。基于這一原理,算法由近及遠地逐次求出0v到其它各點的最短路。下面通過例子說明具體做法。(1令0{}Sv=,\SVS=,求0v到S中最近點的最短路。在當前的例子中,從v0v1、v0v2、v0v3中選一條最短的,結果獲得v0到v1的最短路v0v1。(2令1:{}SSv=∪,:\SVS=,求0v到S中最近點的最短路。這里“最近”是指0v到S的直接連邊、以及從0v出發(fā)的已有最短路上的點(即S中除0v外的點,當前只有1v通過最短路再添加上向S的連邊所形成的路中最短的。即選取S中一點v使得距離00,(,min{(,(}iiivSvSdvvdvvwvv∈∈=+。(*在當前的例子中,從v0v2、v0v3、v0v1v2、v0v1v3中選一條最短的,結果獲得v0到v3的最短路v0v1v3。(3令3:{}SSv=∪,:\SVS=,求0v到S中最近點的最短路。即選取S中一點v使得00,(,min{(,(}iiivSvSdvvdvvwvv∈∈=+。當前應從v0v2、v0v1v2、v0v1v3v2、v0v1v3v4中選一條最短的,結果獲得v0到v4的最短路v0v1v3v4。(4令4:{}SSv=∪,:\SVS=,求0v到S中最近點的最短路。即選取S中一點v使得00,(,min{(,(}iiivSvSdvvdvvwvv∈∈=+。當前應從v0v2、v0v1v2、v0v1v3v2、v0v1v3v4v2中選一條最短的,結果獲得v0到v2的最短路v0v1v2(或v0v1v3v4v2。一般地,若01{,,,}kSvvv=以及相應的最短路已找到,則可用(*式來選取v,獲得0v到v的最短路。在上述算法的過程中,每輪循環(huán)求0(,dvv時,都要對所有的點ivS∈計算0(,(iidvvwvv+且比較出一個最小的值,因而在算法循環(huán)過程中需要大量重復的路長計算和比較。為了避免這種重復計算,Dijkstra算法采用標號方法來實現(xiàn):算法執(zhí)行中,給每個點v都附一個標號l(v,表示當前已經算出的從v0到該點的最短路的長0(,dvv。算法每輪循環(huán)都考慮修改點v的標號,如果通過此前剛剛進入S集合的點vi到該點的連邊不能獲得更短的路,則該點保持原有標號l(v不變;否則,修改該點標號為l(v:=l(vi+w(viv,當前v0到v的最短路應由v0到vi的最短路及邊viv構成。標號法的基本原理是累進比較。初始時,0(:0lv=,∞=:(vl,(0vv≠,0{}Sv=,\SVS=。然后算法逐步修改S中頂點的標號。第i步時,對S中每個v,只對剛進入S的點vi計算0(,(iidvvwvv+(即((iilvwvv+,并與(lv進行比較,取其較小的一個作為的新標號,即(:min{(,((}iilvlvlvwvv=+。因為對在iv之前進入S的點011,,,ivvv?,0(,(kkdvvwvv+(k=1,2,…,i?1的值及其大小信息已含于(lv之中,因此只需計算一個值0(,(iidvvwvv+,并將其與此前紀錄的最短路的長(lv進行比較即可,而不必對所有的點ivS∈都重新計算0(,(iidvvwvv+且比較出一個最小的,從而避免了重復計算和比較。按照算法過程,標號法實現(xiàn)算法主要包括兩個過程,(1修改各點的標號,(2從S的所有點中取標號最小的一個點,放入S中。某個點被放入S集合后,它的標號成為永久標號,不再被修改。算法反復執(zhí)行上述過程,直至所有頂點獲得永久標號(被放入S中。算法具體步驟如下:Dijkstra算法:求非負權圖中v0點到其余各點的最短路。第1步.令0(:0lv=,∞=:(vl,(0vv≠,0:{}Sv=,:\SVS=,0:=i。第2步.對每個vS∈,令(:min{(,((}iilvlvlvwvv=+。取*vS∈使得(*min{(}vSlvlv∈=。記*1ivv+=,令1:{}iSSv+=∪,:\SVS=。第3步.令1:+=ii。如果1iυ=?,則停止;否則,轉第2步。3.算法正確性定理1.2.1Dijkstra算法結束時,對任一個頂點v,其標號l(v恰是v0到v的最短路的長。證明:按照算法,頂點v的最終標號l(v是v進入集合S時的標號。假設v在算法第i次循環(huán)時進入集合S,則1ivv+=,且v進入集合S后{,,,,}011iiSvvvv+=。由于l(v是算法在前i次循環(huán)中逐次比較出的當前從v0到v最短路的長,因此從v0到v僅含{,,,,}011iivvvv+中點的任何路的長都不會小于l(v。任取圖G中一條從v0到v的路P,如果P僅含{,,,,}011iivvvv+中的點,則如上所述,P的長不會小于l(v;如果P含{,,,,}011iivvvv+之外的點,無妨設沿著P從v0出發(fā)第一個不在{,,,,}011iivvvv+中的頂點是v′。因在算法第i次循環(huán)時,vi+1進入S而v′仍未進入S,說明當前l(fā)(vi+1≤l(v′。注意v′只是P的中途點且圖G中所有邊的權都非負,而當前的l(v′大于或等于v0到v′僅含{,,,,}011iivvvv+中點的最短路的長,故路P的長大于或等于P上v0到v′段的長(≥l(v′,從而P的長不會小于l(vi+1(即l(v。證畢。按照上述定理,Dijkstra算法結束時,每個頂點的標號l(v表示v0到該點的最短路的長。此外,通過檢查標號的來源點,可反向追蹤得到v0到各點的最短路。4.算法有效性對于一個圖論算法,如果在任何圖上施行這個算法所需要的基本計算量(比如加、減、乘、除運算或比較、賦值等都以圖的頂點數(shù)υ的一個函數(shù)為其上界,則稱這個函數(shù)為該算法的計算復雜度或時間復雜度,一般簡稱為復雜度(complexity。圖的頂點數(shù)υ稱為圖論問題的規(guī)模。人們總是希望利用計算機執(zhí)行算法以解決人工難以計算的大規(guī)模問題,因此,對一個算法人們主要關心它在解決大規(guī)模問題時的計算量。對于圖論算法,主要關心當圖的頂點數(shù)υ增大時,算法所需計算量的增加情況。如果一個算法的計算復雜度是規(guī)模υ的指數(shù)函數(shù),比如2υ、!υ等,則當問題的規(guī)模較大時,算法所需的計算量快速增大以至于無法接受,這樣的算法在解決大規(guī)模問題時實際上是無用的。當一個算法的計算復雜度是多項式函數(shù)時,算法的計算量隨規(guī)模的增加其增幅較緩,人們認為一般是可以接受的。因此,一個具有多項式時間復雜度的算法稱為是有效算法(efficientalgorithm或好算法(goodalgorithm,有時直接稱為多項式時間算法或多項式算法。對于多項式算法,影響其時間復雜度的主項是多項式的最高次項,因此人們在作算法分析時,主要關注其最高次項。一般地,如果一個算法的復雜度是1110kkkkaaaaυυυ??++++,則我們說它的計算復雜度是(kOυ,或是(kOυ階的。利用這個記號,如果一個算法的復雜度是2υ或!υ,我們也可寫為O(2υ或O(!υ。按照復雜度的上述定義,如果一個算法是(kOυ階的,則它也是1(kOυ+階的,甚至也是O(2υ階的。但實際上,人們在提到算法的復雜性時,總是指它的最低的階。下一定理表明Dijkstra算法是多項式算法。定理1.2.2Dijkstra算法的計算復雜度為(2Oυ。證明:Dijkstra算法的主要計算量在第2步。在第i次循環(huán)中,第2步第1式需要1iυ??次加法,1iυ??次比較;第2式需要不超過1iυ??次比較。(0,1,,2iυ=?。從而1υ?次循環(huán)總的計算量不超過23(1iiνυ?=??=∑3(12υυ?=(2Oυ。對一個需要用算法解決的問題,如果存在求解它的多項式算法,則這個問題稱為P問題(polynomialproblem。如果一個問題,當猜出其答案時可在多項式計算量內驗證答案的正確性,則這個問題稱為NP問題(non-deterministicpolynomialproblem。將所有P問題的集合記為P,所有NP問題的集合記為NP,是否P=NP?這是計算機科學和組合最優(yōu)化領域的一個重要未解難題。明顯地PNP?,但人們目前還不知道是否PNP?。Cook(1970發(fā)現(xiàn)NP問題中有一類問題,只要其中有一個問題是P問題,則所有NP問題全是P問題,即P=NP。這類問題稱為NP完全問題,簡稱為NPC問題(non-deterministicpolynomialproblem。遺憾的是,對目前已找到的成千上萬個NPC問題,人們還未能證明其中任何一個是P問題。圖論中有許多問題屬于NPC問題。有興趣的讀者可參閱下列文獻。[2]http://www.nada.kth.se/~viggo/problemlist/[3]M.R.Garey&D.S.Johnson,ComputersandIntractability?aguidtothetheoryofNP-completeness,W.H.Freedman,SanFrancisco,1979.(中譯本:張立昂等譯,計算機和難解性—NP完全性理論導引,科學出版社,1987。[4]D.S.Hochbaum,ApproximationalgorithmsforNP-hardproblems,InternationalThomsonPublishingCompany,1995.[5]Ding-zhuDuandKer-IKo,TheoryofComputationalComplexity,JohnWiley&Sons,INC.,NewYork,2000.[6]FengGao,Ding-zhuDu,BiaoGao,Peng-junWan,andP.M.Pardalos,Minimaxproblemsincombinatorialoptimization,MinmaxandApplications(eds.byDing-zhuDu&P.M.Pardalos,KluwerAcademicPublishers,1995.[7]D.B.Shmoys,Computingnear-optimalsolutionstocombinatorialoptimizationproblems,CombinatorialOptimization(W.Cook,L.LovaszandP.Seymoureds.,DIMACSSeriesinDiscreteMathematicsandTheoreticalComputerScience,Vol.20,(1995355-397.[8]C.H.Papadimitriou&K.Steiglitz,CombinatorialOptimization:AlgorithmsandComplexity,Prentice-Hall,Inc.,EnglewoodCliffs,NewJersey,1982.[9]A.Gibbons,Algorithmicgraphtheory,Cambridge,CambridgeUniversityPress,1985.[10]M.R.Garey&D.S.JohnsonandL.Stockmeyer,SomesimplifiedNP-completegraphproblems,Theoret.Comput.Sci.,I237-267,1976.[11]CookS.Thecomplexityoftheorem-provingprocedure,ConferenceRecordofThirdACMSymposiumonTheoryofComputing,1970,pp151-158.[12]王樹禾,圖論及其算法,中國科技大學出版社,1990。[13]謝政,網絡算法與復雜性理論(第二版,國防科技大學出版社,2003。上述Dijkstra算法可以用列表的方式進行計算,下面舉例說明?？紤]圖1.1中的賦權圖。首先將頂點v1,v2,v3,v4作為一行。然后將起始點v0放在表內第一行左首,將v0到其余各點連邊上的權(即標號l(vk放在各頂點下方相應位置上。從第一行數(shù)字中選取最小的一個,用方括號標記,并在斜杠下方標上v0,當前找到v1下方的數(shù)字最小。接著,將v1放在表內第二行左首(表示v1進入集合S,對每個尚未進入S的頂點vk,將第一行方括號中的數(shù)字與邊v1vk上的權相加,并與第一行vk下方的數(shù)字比較,取較小的一個(即新標號(:min{(,((}11kkklvlvlvwvv=+放在第二行相應位置上。從第二行數(shù)字中選取最小的一個,用方括號標記,當前找到v3下方的數(shù)字最小。由于該數(shù)字3是通過v1得來的(即min{(,((}3113lvlvwvv+113((3lvwvv=+=,故在該數(shù)字斜杠下方標上v1。同樣,將v3放在表內第三行左首(表示v3進入集合S,對每個尚未進入S的頂點vk,將第一行方括號中的數(shù)字與邊v3vk上的權相加,并與第二行vk下方的數(shù)字比較,取較小的一個(即新標號(:min{(,((}33kkklvlvlvwvv=+放在第三行相應位置上。并從第三行數(shù)字中選取最小的一個,用方括號標記,當前找到v4下方的數(shù)字最小。由于該數(shù)字5是通過v3得來的(即min{(,((}4334lvlvwvv+334((5lvwvv=+=,故在該數(shù)字斜杠下方標上v3。最后,將v4放在表內第四行左首(表示v4進入集合S,對尚未進入S的唯一頂點v2,將第一行方括號中的數(shù)字與邊v3v2上的權相加,并與第三行v2下方的數(shù)字比較,取較小的一個(即新標號(:min{(,((}22442lvlvlvwvv=+放在第四行相應位置上。并從第四行數(shù)字中選取最小的一個,現(xiàn)在第四行只有v2下方的數(shù)字6,用方括號標記之,v2進入集合S。由于該數(shù)字6可看成是通過v2的舊標號l(v2得來的(即min{(,((}2442lvlvwvv+2(6lv==,舊標號l(v2又是在第二行通過v1得來的,故在該數(shù)字斜杠下方標上v1。至此,算法結束。從每個頂點vk所在列的最后一個數(shù)字(方括號內的數(shù)字可以得知v0到vk的最短路的長。比如,v0到v4的最短路的長為5。由斜杠后的標識可反向追蹤出最短路。比如找v0到v4的最短路:先從v4列下方的標識找到v3,再從v3列下方的標識找到v1,最后從v1列下方的標識找到v0,從而可知v0到v4的最短路為v0v1v3v4。Dijkstra算法也可以通過矩陣形式來進行,其步驟為:第0步.將賦權圖G的權矩陣(wij的第一列中所有元素全改為×,在第一行剩下的其他元素下面劃一條橫線。第1步.在畫橫線的元素中找一個最小的wki,若wki=∞,則停止,從v0到某些頂點沒有路;否則,把wki用方括號標記,并把第i列其他元素都改成×,然后給第i行中不是×的元素都加上wki,并在這些元素下面劃一條橫線,轉第2步。第2步.如果存在不含×的列,則轉第1步;否則結束,方括號標記的元素wij表示從v0到vj的最短路的長,而從v0到vj的最短路由最短(v0,vi路與邊vivj構成。仍以圖1.1為例,其權矩陣為(wij=123401234∞∞????∞∞????∞??∞????∞∞∞???1845256126212×∞????×∞∞????×∞??×∞????×∞∞???[1]8463616212×∞????××∞????××∞??××∞????××∞???[1]86[3]1951××∞????××∞????××∞×??×××????×××∞???[1]86[3]9[5]6×××????×××????××∞××??×××????××××???[1][6][3][5]××××????×××????×××××??××××????×××××??由最后一個矩陣的元素回溯便可獲得v0到各點的最短路。比如,v4的最短路的長為5;為找從v0到v4的最短路,從v4所在列(最后一列開始回溯,因該列非×元素在v3行(第4行,v3列非×元素在v1行(第2行,而v1列非×元素在v0行(第1行,故v0到v4的最短路為v0v1v3v4。上述最短路算法僅適用于求所有邊的權均非負的途中的最短路。在邊允許有負權的圖中求最短路,有Ford算法和Floyd算法。Ford算法用于求無負權圈的圖中一點到其它各點的最短路;Floyd算法用于求無負權圈的圖中所有頂點對之間的最短路。這兩個算法當然也可以用于所有邊的權均為非負的圖中。有興趣的讀者可參看文獻[14]、[15]、[16]。求圖的前k條最短路的算法可參考[16]。[14]謝政,網絡算法與復雜性理論(第二版,國防科技大學出版社,2003。[15]王朝瑞,圖論(第三版,北京理工大學出版社,2001。[16]N.Christofides,GraphTheory–aalgorithmicapproach,AcademicPress,INC.,1990.此外,對分層圖,也可用動態(tài)規(guī)劃方法來求最短路。動態(tài)規(guī)劃源于多階段最優(yōu)決策過程,它的基本思想是Bellman最優(yōu)化原理。該原理可概括地描述為:如果圖G中從A點到C點的最短路P經過點B,則P上B到C的一段必定是該圖中B點到C點的最短路。依據(jù)這個原理,可用一個基本的遞推關系式使最優(yōu)決策過程連續(xù)地轉移。使用動態(tài)規(guī)劃方法時,要從最終狀態(tài)開始逐步遞推到起始狀態(tài)。例如,對下圖求A到H的最短路。該圖的頂點從A到F分為5層,同層頂點間互不連邊,隔層頂點間也沒有連邊,這便是分層圖。我們從H點開始考慮。其前一層頂點F和G到H的最短路的長分別是4和3,記為W(F=4,W(G=3。再考慮F和G的前一層頂點D和E。從D出發(fā)有兩種選擇:DFH,路長為1+W(F=5;DGH,路長為1+W(G=4;故從D到H的最短路為DGH,W(D=4。同樣可知,從E到H的最短路為EGH,W(E=5。再考慮B、C。B到H可經過D也可經過E,經D到H的最短路長為6+W(D=10,經E到H的最短路長為6+W(E=11,故從B到H的最短路應經過D,且最短路長為W(B=10。同樣可得,從C到H的最短路應經過D,且最短路長為W(C=8。最后考慮頂點A,它到H可經過B也可經過C,經B到H的最短路長為4+W(B=14,經C到H的最短路長為5+W(C=13,故從A到H的最短路應經過C,且最短路長為W(A=13。因此獲得A到H的最短路為ACDGH。在上述過程中,決定每層頂點的結果只需要做4次加法。如果將圖擴展為n層,則計算量為4(n?3+2,這比Dijkstra算法的計算量低的多。由此可見,針對具體問題的特點可以設計出非常有效的算法。關于最短路問題讀者可進一步參閱文獻:[17]E.Dijkstra,Anoteontwoprobleminconnectionwithgraphs,Numer.Math.,1(1959269-271.[18]L.R.Ford,Networkflowtheory,RandCorporationReport,(1956923.[19]R.W.Floyed,Algorithm97-ShortestPath,Comm.,ACM,5(1962345.[20]D.Bertsekas,Asimpleandfastlabelcorrectingalgorithmforshortestpaths,Networks,23(1993703-709.[21]M.Desrochers,andF.Soumis,areoptimizationalgorithmfortheshortestpathproblemwithtimewindows,EuropaeanJournalofOperationalResearch,35(1988242-254.[22]M.Dror,Noteonthecomplexityoftheshortestpathmodelsforcolumngeneration,OperationsResearch,42(1994977-978.[23]G.Gallo,andS.Pallottino,Shortestpathalgorithms,AnnalsofOperationsResearch,7(198873-79.[24]F.Glover,R.Glover,andD.Klingman,Thethresholdshortestpathalgorithm,Networks,14(198425-36.[25]W.B.Powell,Zhi-LongChen,Ageneralizedthresholdalgorithmfortheshortestpathproblemwithtimewindows,inNetworkDesign:ConnectivityandFacilitiesLocation(P.M.PardalosandDing-zhuDueds.,DIMACSSeriesinDiscreteMathematicsandTheoreticalComputerScience,Vol.40,(1998303-318.§1.3樹及其性質不含圈的圖稱為森林(forest,不含圈的連通圖稱為樹(tree。定理1.3.1下列命題等價:(1G是樹;(2G中無環(huán)邊且任二頂點之間有且僅有一條路;(3G中無圈且1ευ=?;(4G連通且1ευ=?;(5G連通且對任何(GEe∈,eG?不連通;(6G無圈且對任何(GEe∈,eG+恰有一個圈。證明:(1?(2G是樹?G連通?(,GVvu∈?,存在路,(vuP。若還存在一條路≠′,(vuP,(vuP,則必存在w,w是路P與P′除了v之外最后一個公共頂點。P的,(vw段與P′的,(vw段構成圈,這與G是樹矛盾。故只存在唯一的,(vu路。(2?(3若G有圈,則此圈上任二頂點間有兩條不同的路,與前提條件矛盾。下面用歸納法證明1ευ=?。1υ=時,0=ε,結論真。假設kυ≤時結論真,我們來證明當1kυ=+時,也有1ευ=?成立。當1kυ=+時,任取邊E(uvG∈?？紤]圖uvGG?=′,因G中u、v間只有一條路,即邊uv,故G′不連通且只有兩個連通分支,設為21,GG。注意到21,GG分別都連通且任二頂點間只有一條路,由歸納法假設,11((1GGευ=?,22((1GGευ=?。因此1212(((1((1((11(1GGGGGGεεευυυ=++=?+?+=?。歸納法完成。(3?(4用反證法。若G不連通,設wGGG,,,21是其連通分支(2≥w,則1iiευ=?(因iG是連通無圈圖,由已證明的(1和(2知,對每個iG,(3成立。這樣,11wwiiiiwwεευυ====?=?∑∑,這與1ευ=?矛盾。(4?(5((12GeGεευ?=?=?,但每個連通圖必滿足1ευ≥?(見下列引理,故圖eG?不連通。引理若圖H連通,則((1HHευ≥?。證明:對υ做數(shù)學歸納法。1,2υ=時,1ευ≥?顯然成立。假設kυ≤的連通圖都1ευ≥?。對于1kυ=+的連通圖H,任取(HVv∈,考慮vH?。若vH?連通,則由歸納假設,((11HvHvkευ?≥??=?,而((1(11(11(1HHvkkHεευ≥?+≥?+=+?=?。若vH?不連通,設wHHH,,,21是其連通分支(2≥w。由歸納假設,((1iiHHευ≥?,(wi,,2,1=。故11((((wwiiiiHvHHwHvwkwεευυ==?=≥?=??=?∑∑,而((((11(1HHvwkwwkHεευ≥?+≥?+=+?=?。歸納法完成。(5?(6先證G中無圈:若G中有圈,刪去圈上任一邊仍連通,矛盾。再證對任何(GEe∈,eG+恰含一個圈:因G連通且已證G無圈,故G是樹。由(2,任二不相鄰頂點間都有一條路相連,故eG+中必有一個含有e的圈;另一方面,若eG+中有兩個圈含有e,則(eG+Ge=?中仍含有一個圈,矛盾。(6?(1只需證G連通。任取(,GVvu∈,若u、v相鄰,則u與v當然連通。若u、v不相鄰,則uvG+恰含一個圈,故u與v在G中連通。由u、v的任意性,圖G連通。定理證畢。推論1.3.1非平凡樹至少含兩個1度頂點(葉子。證明:設T是一個非平凡樹。因T連通,故對每個頂點iv,都有1(≥ivd。若對所有iv都有2(≥ivd,則1(2iidvυυ=≥∑。但另一方面,1(22(122iidvυευυ===?=?∑。這兩方面矛盾。故T至少有一個1度頂點,設為u。除此之外,其余1υ?個頂點的度數(shù)之和為23υ?。若這些點的度都大于或等于2,則其度數(shù)之和2(122υυ≥?=?。這與23υ?矛盾。故除u之外T還至少有一個度為1的頂點。證畢?！?.4生成樹與最小生成樹一、生成樹(spanningtree定義1.4.1設T是圖G的一個子圖,如果T是一棵樹,且((TGυυ=,則稱T是G的一個生成樹。定理1.4.1每個連通圖都有生成樹。證明:設G是一個連通圖。令GGA′′=|{是G的連通子圖且((}GGυυ′=。易見A非空。從A中取邊數(shù)最少的一個,記為T。下證T是G的生成樹。顯然只需證明T是樹即可。事實上,已知T連通,下證T無圈。若T有圈C,則去掉C上任一條邊e,eT?仍連通。從而AeT??。但eT?比T少一條邊,這與T的取法矛盾。證畢。推論1.4.1若G連通,則1ευ≥?。證明:取G的生成樹T,則(((1(1GTTGεευυ≥≥?=?。證畢。二、最小生成樹問題最小生成樹問題:在賦權圖G中,求權最小的生成樹(簡稱為最小生成樹。即:求G的一棵生成樹T,使得∑∈=TeTewTw(min(。最小生成樹問題是一個優(yōu)化問題,需要設計優(yōu)化算法尋找其最優(yōu)解。求解最小生成樹問題的算法較多,本節(jié)主要介紹Kruskal算法和Prim算法。(一Kruskal算法(JosephBernardKruskal,19561.算法思想:先從圖G中找出權最小的一條邊作為最小生成樹的邊,然后逐次從剩余邊中選邊添入最小生成樹中,每次選邊找出不與已選邊構成圈的權最小的一條邊。直至選出(G1υ?條邊為止。2.算法步驟:輸入:賦權連通υ階圖G。輸出:G的最小生成樹T。第一步取(1GEe∈使得(min{(},eGwewe∈=令:1i=。第二步取},,,{\(211iieeeGEe∈+使得(1G[{121,,,,+iieeee}]不含圈;(21+ie是滿足(1的權最小的邊。第三步當i+1=(1Gυ?時,輸出最小生成樹G[{121,,,eeeυ?}],算法停止;否則,令1:+=ii,轉第二步。3.算法正確性:定理1.4.2設12(1,,,Geeeυ?是Kruskal算法獲得的邊,則邊導出子圖G[{12(1,,,Geeeυ?}]是G的最小生成樹。證明:記*T=G[{12(1,,,Geeeυ?}]。顯然*T無圈,因此*T是森林。設它有w個連通分支,則(T(T(T1((G11(Gwυεευυ???=+≥+=?+=。但*T是G的子圖,故*((TGυυ=。于是**((1(1TGTευυ=?=?。由定理1.3.1的(3,*T是一棵樹。又*((TGυυ=,從而是G的一棵生成樹。下證其最優(yōu)性,用反證法。假設*T不是權最小的生成樹(下稱最優(yōu)樹。對G的任一棵不同于*T的生成樹T,記121(min{|{,,,}ifTieeeeυ?=∈且}Tei?。在G的所有最優(yōu)樹中選取一棵使(Tf最大的,記為T~。(T~不會是*T,因假設*T不是最優(yōu)樹。設kTf=~(。由~(Tf的定義,121,,,?keee既在*T上也在T~上,但ke不在T~上。因此keT+~含有一個圈C。C上必有一條邊*Tek?′。顯然kkeeTT′?+=′~(也是一棵生成樹,且((~((kkewewTwTw′?+=′。按照算法,ke是使G[{keee,,,21}]中無圈的邊中權最小的。注意G[{kkeeee′?,,,,121}]是T~的子圖,也無圈。故由算法規(guī)則知:((kkewew≥′。由前式,~((TwTw≤′,這說明T′也是最優(yōu)樹。但~((TfkTf=>′(注意由于121,,,?keee在*T上且*Tek?′,故121{,,,}kkeeee?′?。這與T~的取法矛盾。證畢。4.Kruskal算法的實現(xiàn)及其計算復雜度分析Kruskal算法的計算量主要在第二步。算法共需執(zhí)行1υ?次第二步,在第i次執(zhí)行第二步時,須比較集合12(\{,,,}iEGeee中所有邊的權以求得一條權最小的邊,并檢驗該邊是否與已有邊構成圈,如果構成圈,還需再找新的最小權邊,這是比較浪費的。在實際應用Kruskal算法時,一般先將所有的邊按權由小到大排序,這需要大約2logεε次比較(見[26]。每次執(zhí)行算法第二步時,不必再比較邊的權,而是直接選取此前尚未考慮過的權最小的邊,檢驗它是否與已有邊構成圈即可。這樣可省去許多次循環(huán)比較。[26]D.E.Knuth,Theartofcomputerprogramming,Vol.3:SortingandSearching,Addison-Wesley,Reading,Mass.,(1973184.接下來的問題是如何檢驗所選邊是否與已有邊構成圈。這可通過給頂點標號來實現(xiàn)。設算法在i次循環(huán)后選出的邊集合為Ei。算法開始時,給所有頂點標不同的標號:頂點kv標號為k,(1,2,,kυ=。當算法執(zhí)行第i+1次循環(huán)選出一邊1ie+添加進G[Ei]形成G[Ei+1]時,用該邊兩端點標號的較小者給這條邊所連的G[Ei+1]的兩個連通分支的頂點重新標號(連通分支有可能僅由1ie+的一個端點組成。按這個標號方案,在任意一步中,兩個頂點屬于已選邊形成的同一連通分支當且僅當它們有相同的標號。這意味著當我們考慮向G[Ei]添加某條邊e是否會形成圈時,只要檢查e的兩個端點是否有相同的標號即可。如果有相同的標號,則拋棄該邊(以后的循環(huán)中不再使用,再檢驗權稍大些的下一個候選邊;如果標號相異,則取e作為1ie+添加進G[Ei]。在這個過程中,對每條候選邊只需做一次比較就能決定是否拋棄它。算法全過程至多需要ε(12υυ?≤次這樣的比較。當添加1ie+進入G[Ei]時,頂點重新標號最多需要υ次比較,因此對1υ?條邊最多需要(1υυ?次比較?？梢娝惴▓?zhí)行過程約需要ε+(1υυ?次計算。由以上分析可得如下結論。定理1.4.3若事先將頂點按權排序,則Kruskal算法的計算復雜度為2O(υ;若加上事先排序的計算量,則Kruskal算法的計算復雜度為22O(logυυ。證明:算法執(zhí)行過程中需要的主要計算量為ε+(1υυ?(12υυ?≤+(1υυ?=3(12υυ?,事先排序需要的計算量為2logεε222(1(1loglog22υυυυυυ??≤≤。故知定理結論成立。證畢。例1.4.1欲建設一個連接5個城市的光纖通信網絡。各城市間線路的造價如圖所示,求一個使總造價最少的線路建設方案。解:算法執(zhí)行過程如下所示。(二Prim算法(RobertClayPrim,19571.算法思想:先從圖G中找出權最小的一條邊作為最小生成樹的邊,在算法任一輪循環(huán)中,設已經選出的邊導出的子圖為G′,從G′的頂點向G′以外頂點的連邊為E′,則選擇E′中權最小的邊向G′中添加,如此反復循環(huán)直至選出(G1υ?條邊為止。Prim算法與Kruskal算法的根本區(qū)別在于:Kruskal算法在保持無圈的基礎上選邊,而在保持連通的基礎上選邊。Prim算法的添邊過程實際上是樹的生長過程。Kruskal算法的添邊過程一般情況下是森林合并為樹的過程。在一些文獻中,Kruskal算法也稱為避圈法,Prim算法也稱為邊割法。2.算法步驟:輸入:賦權連通υ階圖G。輸出:G的最小生成樹T。step1.任取(0GVv∈,令00{}Sv=,00(\SVGS=,:0i=,0Eφ=。step2.求iS到iS間權最小的邊1ie+,設1ie+的屬于iS的端點為1iv+,令11:{}iiiSSv++=∪,11\(++=iiSGVS,11:{}iiiEEe++=∪Step3.當i+1=(1Gυ?時,輸出最小生成樹G[Ei+1]=G[{121,,,eeeυ?}],算法停止;否則,令1:+=ii,轉step2。3.算法正確性:定理1.4.4設121,,,eeeυ?是Prim算法獲得的邊,則邊導出子圖G[{121,,,eeeυ?}]是G的最小生成樹。證明:用kT表示Prim算法第k次循環(huán)得到的邊集所構成的子圖,即kT=G[Ek]=G[{12,,,keee}],1,2,1kυ=?。我們用歸納法來證明,對每個k(1,2,1kυ=?,kT必含于G的某個最小生成樹中。當k=1時,1T僅由邊1e生成。注意到1e是G中權最小的邊,因此,對G的任一棵最小生成樹T?,若T?不含有1e,則1Te?+有一個圈C,C上每條邊的權都不小于1e的權1(we。設e是C上一條異于1e的邊,則1TTee?′=+?也是G的一棵生成樹,且其權*((wTwT′≤?？梢奣′也是G的一棵最小生成樹,并且含有邊1e。即1T含于最小生成樹T′中。假設k=m時(11mυ≤<?,結論成立,即mT含于G的某個最小生成樹T*中。考慮最后一條進入1121[{,,,}]mmmTGeeee++=的邊1me+。若1me+在T*中,則11mmmTTe++=+含于最小生成樹T*中。若1me+不在T*中,則1mTe?++有一個圈C。由于11mmmTTe++=+無圈,故C上必有邊屬于T*而不屬于mT,但mT是T*的子圖,故C上必可找到一條異于1me+的邊euv=,使得muT∈而mvT?。由算法步驟知,權1((mwewe+≥。于是1mTTee?+′=+?也是G的一棵最小生成樹,并且含有邊1me+。再注意到mT的邊全在T*中,因此上述結論表明11mmmTTe++=+含于最小生成樹T′中。歸納法完成。證畢。4.計算復雜度分析:Prim算法的主要計算量在第二步。在算法第i輪循環(huán)執(zhí)行第二步時,iS中有i個頂點,iS中有iυ?個頂點,故iS到iS間最多有(iiυ?條邊。從這些邊中選出一條權最小的邊1ie+,需要(1iiυ??次比較。算法需循環(huán)執(zhí)行第二步1υ?次,因此總的計算量為-1-1111[(1]((1(+16iiiiiiυυυυυυυ==??≤?=?∑∑。由此可見,Prim算法的計算復雜度為3(Oυ。與Kruskal算法類似,使用頂點標號法可進一步降低Prim算法的計算復雜度。(三Prim算法的標號形式―標號Prim算法1.算法思想:給圖的頂點賦以標號,該標號與邊的權有關,在執(zhí)行Prim算法的過程中,通過修改頂點標號和比較頂點的權,來選擇滿足Prim算法要求的最小權邊。頂點v的標號記為(lv。用(wuv表示邊euv=的權,若,uv兩點間沒有邊,則(wuv=∞。2.算法步驟:輸入:賦權連通ν階圖G。輸出:G的最小生成樹T。step1.任取(0GVv∈,令0000(0,(,(,{}lvlvvvSv==∞≠=,00(\SVGS=,00Tv=,:0i=。step2.對(GiivNvS?∈∩,若((iwvvlv<,則令(:(ilvwvv=。Step3.選取1iivS+∈使得1(min(iivSlvlv+∈=。設11,(iiieuvuS++=∈使得11((iiwelv++=,令11:{}iiiSSv++=∪,11\(++=iiSGVS,11:{}iiiTTe++=∪。Step4.當i+1=1(?Gν時,輸出最小生成樹1Tν?,算法停止;否則,令1:+=ii,轉step2。3.算法正確性:標號Prim算法是Prim算法的標號實現(xiàn),因此由Prim算法的正確性即知標號Prim算法結束時必能得到圖G的最小生成樹。4.計算復雜度分析:算法的主要計算量在第2步和第3步。算法第一次執(zhí)行Step3需做n?2次比較,第二次執(zhí)行Step3需做n?3次比較,??????,因此執(zhí)行Step3共需做1(2(12υυ??次比較;同樣,執(zhí)行Step2共需不超過1(2(12υυ??次比較。于是標號Prim算法的時間復雜性為O(υ2。標號Prim算法將Prim算法每次循環(huán)中比較1iS+到1iS+間所有邊的權,改為修改(GiiNvS∩中點的標號并比較iS中點的標號,因此節(jié)省了計算量。一些文獻中將標號Prim算法稱為Dijkstra最小生成樹算法。5.Prim算法的矩陣實現(xiàn)―求最小樹的權矩陣法Prim算法可以通過權矩陣來實現(xiàn)。給定一個賦權的連通n階簡單圖G,其各邊上的權組成的n階(ijnnWw×=稱為G的權矩陣,其中元素ijw定義如下:(1,1,2,,iiwin=∞=;(2若邊(ijvvEG∈,則(ijijwwvv=;(3若邊(ijvvEG?,則ijw=∞。算法步驟為:Step0.劃掉矩陣W的第一列(將W第一列元素全改為×,并在第一行剩下的每個元素下面畫一條橫線。Step1.在畫橫線的元素中找一個最小的元素kiw,并將其圈起來。然后把第i列其它元素全部劃去(改為×,并在第i行沒有被劃掉的元素下面畫上橫線。Step2.若矩陣W的所有元素要么已被劃去要么已被圈起來,則算法結束,圈起來的元素即對應于所求最小生成樹的邊。否則,轉Step1。例1.4.2用權矩陣法求如下賦權圖G的一棵最小生成樹。解:求解過程如下?！????∞∞????∞??∞????∞∞??→20×????×∞∞????×∞??×∞????×??××∞????××∞??××∞????××∞??→(2030(25504020101520×????×××∞????××∞×??×××????×××∞??→(20(255020(1015××????××××∞????××××??×××????××××∞??→(20(25(10(15×××????×××××????×××××??×××????×××××??。最后得到的最小生成樹由邊v1v2、v1v4、v4v3、v4v5構成,其權為20+25+10+15=70。在實際應用中,往往需要求圖的滿足某種約束條件的最小生成樹。這一類問題統(tǒng)稱為約束最小生成樹問題(Constrainedminimumspanningtreeproblems。常見的有頂點度約束最小生成樹、直徑約束最小生成樹、邊容量約束最小生成樹、最多葉子最小生成樹等,詳細可參閱下列文獻[27]或[28]~[42]。約束最小生成樹問題大多數(shù)是NPC問題,因此對這些問題主要是設計好的近似算法。約束最小生成樹問題參考文獻[27]N.DeoandN.Kumar,Computationofconstrainedspanningtrees:aunifiedapproach,NetworkOptimization(P.M.Pardalos,D.W.Hearn,andW.W.Hagereds.,LectureNotesinEconomicsandMathematicalSystems,450,Springer-Verlag,BerlinHeidelberg,1997.[28]D.KleitmanandD.West,Spanningtreeswithmanyleaves,SIAMJournalonDiscreteMathematics,4(1(199199-106.[29]N.DeoandN.Kumar,Constrainedspanningtreeproblems:approximatemethodsandparallelcomputation,inNetworkDesign:connectivityandfacilitieslocation(P.M.PardalosandDing-zhuDueds.,DIMACSSeriesinDiscreteMathematicsandTheoreticalComputerScience,Vol.40,(1998191-216.[30]A.Abdallah,N.Deo,N.Kumar,andT.Terry,Parallelcomputationofadiameter-constrainedMSTandrelatedproblems,TechnicalReportCS-TR-97-04,DepartmentofComputerScience,UniversityofCentralFlorida,Orlando,(1997.[31]B.Boldon,N.Deo,andN.Kumar,Minimum-weightdegree-constrainedspanningtreeproblem:heuristicsandimplementationonanSIMDparallelmachine,ParallelComput.22(1996369-382.[32]G.Craig,M.Krishnamoorthy,andM.Palaniswami,Comparisonofheuristicalgorithmsforthedegreeconstrainedminimumspanningtree.InMeta-heuristics:TheoryandApplications(I.H.OsmanandJ.P.Kellyeds.,(199683-96.[33]N.Kumar,Parallelcomputationofconstrainedspanningtrees:heuristicsandSIMDimplementations,Ph.D.Dissertation,DepartmentofComputerScience,UniversityofCentra