09第9章--圖論模型

1、第9章 MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT 圖論模型 MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MT

2、Eqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT MACROBUTTON MTEditEquation

3、Section2 Equation Section (Next) SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h *

4、 MERGEFORMAT 圖論是運(yùn)籌學(xué)的一個(gè)經(jīng)典和重要分支，專門研究圖與網(wǎng)絡(luò)模型的特點(diǎn)、性質(zhì)以及求解方法。許多優(yōu)化問題，可以利用圖與網(wǎng)絡(luò)的固有特性而形成的特定方法來解決，比用數(shù)學(xué)規(guī)劃等其他模型來求解往往要簡單且有效得多。圖論起源于1736年歐拉對(duì)柯尼斯堡七橋問題的抽象和論證。1936年，匈牙利數(shù)學(xué)家柯尼希（D. Knig）出版的第一部圖論專著有限圖與無限圖理論，樹立了圖論發(fā)展的第一座里程碑。近幾十年來，計(jì)算機(jī)科學(xué)和技術(shù)的飛速發(fā)展，大大地促進(jìn)了圖論研究和應(yīng)用，其理論和方法已經(jīng)滲透到物理、化學(xué)、計(jì)算機(jī)科學(xué)、通信科學(xué)、建筑學(xué)、生物遺傳學(xué)、心理學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)各個(gè)學(xué)科中。9.1 圖的基礎(chǔ)理論9.1.

5、1 圖的基本概念所謂圖，概括地講就是由一些點(diǎn)和這些點(diǎn)之間的連線組成的。定義為，是頂點(diǎn)的非空有限集合，稱為頂點(diǎn)集。是邊的集合，稱為邊集。邊一般用表示，其中屬于頂點(diǎn)集。以下用表示圖中頂點(diǎn)的個(gè)數(shù)，表示邊的條數(shù)。如 REF _Ref523640792 h * MERGEFORMAT 圖9.1是幾個(gè)圖的示例，其中 REF _Ref523640792 h * MERGEFORMAT 圖9.1 (a)共有3個(gè)頂點(diǎn)、2條邊，將其表示為，.圖9. SEQ 圖9. * ARABIC 1 圖的示意圖1.無向圖和有向圖如果圖的邊是沒有方向的，則稱此圖為無向圖（簡稱為圖），無向圖的邊稱為無向邊（簡稱邊）。如 REF _

6、Ref523640792 h * MERGEFORMAT 圖9.1 (a)和(b)都是無向圖。連接兩頂點(diǎn)和的無向邊記為或。如果圖的邊是有方向（帶箭頭）的，則稱此圖為有向圖，有向圖的邊稱為?。ɑ蛴邢蜻叄?，如 REF _Ref523640792 h * MERGEFORMAT 圖9.1 (c)是一個(gè)有向圖。連接兩頂點(diǎn)和的弧記為，其中稱為起點(diǎn)，稱為終點(diǎn)。顯然此時(shí)弧與弧是不同的兩條有向邊。有向圖的弧的起點(diǎn)稱為弧頭，弧的終點(diǎn)稱為弧尾。有向圖一般記為，其中為頂點(diǎn)集，為弧集。例如 REF _Ref523640792 h * MERGEFORMAT 圖9.1 (C)可以表示為，頂點(diǎn)集，弧集為。對(duì)于圖除非指明是

7、有向圖，一般地，所謂的圖都是指無向圖。有向圖也可以用表示。例9. SEQ 例9. * ARABIC 1 設(shè)，其中，.則是一個(gè)圖，其圖形如 REF _Ref523662232 h * MERGEFORMAT 圖9.2所示。圖9. SEQ 圖9. * ARABIC 2 非簡單圖示例2.簡單圖和完全圖定義9. SEQ 定義9. * ARABIC 1 設(shè)是圖的一條邊，則稱是的端點(diǎn)，并稱與相鄰，邊與頂點(diǎn)（或）相關(guān)聯(lián)。若兩條邊與有共同的端點(diǎn)，則稱邊與相鄰；稱有相同端點(diǎn)的兩條邊為重邊；稱兩端點(diǎn)均相同的邊為環(huán)；稱不與任何邊相關(guān)聯(lián)的頂點(diǎn)為孤立點(diǎn)。 REF _Ref523662232 h * MERGEFORMA

8、T 圖9.2中，邊與為重邊，為環(huán)，頂點(diǎn)為孤立點(diǎn)。定義9. SEQ 定義9. * ARABIC 2 無環(huán)且無重邊的圖稱為簡單圖。 REF _Ref523662232 h * MERGEFORMAT 圖9.2不是簡單圖，因?yàn)閳D中既含重邊（與）又含環(huán)（）。定義9. SEQ 定義9. * ARABIC 3 任意兩點(diǎn)均相鄰的簡單圖稱為完全圖。含個(gè)頂點(diǎn)的完全圖記為。3.賦權(quán)圖定義9. SEQ 定義9. * ARABIC 4 如果圖的每條邊都附有一個(gè)實(shí)數(shù)，則稱圖為賦權(quán)圖，實(shí)數(shù)稱為邊的權(quán)。賦權(quán)圖也稱為網(wǎng)絡(luò)，如 REF _Ref523640792 h * MERGEFORMAT 圖9.1 (a)就是一個(gè)賦權(quán)圖。

9、賦權(quán)圖中的權(quán)可以是距離、費(fèi)用、時(shí)間、效益、成本等。如果有向圖的每條弧都被賦予了權(quán)，則稱為有向賦權(quán)圖。4.頂點(diǎn)的度定義9. SEQ 定義9. * ARABIC 5 （1）在無向圖中，與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目（環(huán)算兩次）稱為的度，記為。（2）在有向圖中，從頂點(diǎn)引出的弧的數(shù)目稱為的出度，記為，從頂點(diǎn)引入的弧的數(shù)目稱為的入度，記為，稱為的度。度為奇數(shù)的頂點(diǎn)稱為奇頂點(diǎn)，度為偶數(shù)的頂點(diǎn)稱為偶頂點(diǎn)。定理9. SEQ 定理9. * ARABIC 1 給定圖，所有頂點(diǎn)的度數(shù)之和是邊數(shù)的2倍，即.推論9. SEQ 推論9. * ARABIC 1 任何圖中奇頂點(diǎn)的總數(shù)必為偶數(shù)。5.子圖定義9. SEQ 定義9. * A

10、RABIC 6 設(shè)與是兩個(gè)圖，并且滿足，則稱是的子圖。如是的子圖，且，則稱是的生成子圖。6.道路與回路設(shè)，其中，與和關(guān)聯(lián)，稱是圖的一條道路，簡稱路，為路長，為起點(diǎn)，為終點(diǎn)；各邊相異的道路稱為跡（trail）；各頂點(diǎn)相異的道路稱為軌道（path），記為；起點(diǎn)和終點(diǎn)重合的道路稱為回路；起點(diǎn)和終點(diǎn)重合的軌道稱為圈，即對(duì)軌道，當(dāng)時(shí)成為一個(gè)圈。稱以兩頂點(diǎn)分別為起點(diǎn)和終點(diǎn)的最短軌道之長為頂點(diǎn)的距離。7.連通圖與非連通圖在無向圖中，如果從頂點(diǎn)到頂點(diǎn)存在道路，則稱頂點(diǎn)和是連通的。如果圖中的任意兩個(gè)頂點(diǎn)和都是連通的，則稱圖是連通圖，否則稱為非連通圖。非連通圖中的連通子圖，稱為連通分支。在有向圖中，如果對(duì)于任意兩

11、個(gè)頂點(diǎn)和，從到和從到都存在道路，則稱圖是強(qiáng)連通圖。9.1.2 圖的矩陣表示本節(jié)均假設(shè)圖為簡單圖，其中，。1.關(guān)聯(lián)矩陣對(duì)于無向圖，其關(guān)聯(lián)矩陣，其中對(duì)有向圖，其關(guān)聯(lián)矩陣，其中2.鄰接矩陣對(duì)無向非賦權(quán)圖，其鄰接矩陣，其中對(duì)有向非賦權(quán)圖，其鄰接矩陣，其中對(duì)無向賦權(quán)圖，其鄰接矩陣，其中注9. SEQ 注9. * ARABIC 1 當(dāng)兩個(gè)頂點(diǎn)之間不存在邊時(shí)，根據(jù)實(shí)際問題的含義或算法需要，對(duì)應(yīng)的權(quán)可以取為0或。有向賦權(quán)圖的鄰接矩陣可類似定義。例9. SEQ 例9. * ARABIC 2 REF _Ref532625390 h * MERGEFORMAT 圖9.3所示的無向圖，其鄰接矩陣為. 圖9. SEQ

12、圖9. * ARABIC 3 賦權(quán)無向圖用MATLAB重新畫 REF _Ref532625525 h * MERGEFORMAT 圖9.3的程序如下：clc, cleara=zeros(5); %鄰接矩陣初始化a(1,2:5)=9 2 4 7; a(2,3 4)=3 4; %輸入鄰接矩陣的上三角元素a(3,4 5)=8 4; a(4,5)=6; b=a+a; %構(gòu)造完整的鄰接矩陣s=cellstr(strcat(v,int2str(1:5); %構(gòu)造頂點(diǎn)字符串的細(xì)胞數(shù)組c=graph(b,s); %構(gòu)造無向圖plot(c,EdgeLabel,c.Edges.Weight,LineWidth,1

13、.5); %畫無向圖例9. SEQ 例9. * ARABIC 3 REF _Ref532626696 h * MERGEFORMAT 圖9.4所示的有向圖的鄰接矩陣為.圖9. SEQ 圖9. * ARABIC 4 非賦權(quán)有向圖用MATLAB重新畫 REF _Ref532626696 h * MERGEFORMAT 圖9.4的程序如下：clc, cleara=zeros(6); %鄰接矩陣初始化a(1,2 3)=1; a(2,3)=1; a(3,2 5)=1; a(4,2 6)=1; a(5,2 4 6)=1; a(6,5)=1;b=digraph(a) %生成有向圖plot(b) %畫有向圖9

14、.2 最短路算法及其MATLAB實(shí)現(xiàn)最短路徑問題是圖論中非常經(jīng)典的問題之一，旨在尋找圖中兩頂點(diǎn)之間的最短路徑。作為一個(gè)基本工具，實(shí)際應(yīng)用中的許多優(yōu)化問題，如管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等，都可被歸結(jié)為最短路徑問題來解決。定義9. SEQ 定義9. * ARABIC 7 設(shè)圖是賦權(quán)圖，為中的一條路。則稱的各邊權(quán)之和為路的長度。對(duì)于的兩個(gè)頂點(diǎn)和，從到的路一般不止一條，其中最短的（長度最小的）一條稱為從到的最短路；最短路的長稱為從到的距離，記為。求最短路的算法有Dijkstra（迪克斯特拉）標(biāo)號(hào)算法和Floyd（弗洛伊德）算法等方法，但Dijkstra標(biāo)號(hào)算法只適用于邊權(quán)是非負(fù)的情形。最短

15、路問題也可以歸結(jié)為一個(gè)整數(shù)規(guī)劃模型。9.2.1 固定起點(diǎn)到其余各點(diǎn)的最短路算法尋求從一固定起點(diǎn)到其余各點(diǎn)的最短路，最有效的算法之一是E. W. Dijkstra于1959年提出的Dijkstra算法。這個(gè)算法是一種迭代算法，它的依據(jù)是一個(gè)重要而明顯的性質(zhì)：最短路是一條路，最短路上的任一子段也是最短路。對(duì)于給定的賦權(quán)圖，其中為頂點(diǎn)集合，為邊的集合，鄰接矩陣，這里（），.為中的某個(gè)固定起點(diǎn)，求頂點(diǎn)到中另一頂點(diǎn)的最短距離。Dijkstra算法的基本思想是：按距固定起點(diǎn)從近到遠(yuǎn)為順序，依次求得到圖各頂點(diǎn)的最短路和距離，直至某個(gè)頂點(diǎn)（或直至圖的所有頂點(diǎn)）。為避免重復(fù)并保留每一步的計(jì)算信息，對(duì)于任意頂點(diǎn)，

16、定義兩個(gè)標(biāo)號(hào)：頂點(diǎn)的標(biāo)號(hào)，表示從起點(diǎn)到的當(dāng)前路的長度；：頂點(diǎn)的父節(jié)點(diǎn)標(biāo)號(hào)，用以確定最短路的路線。另外用表示具有永久標(biāo)號(hào)的頂點(diǎn)集。Dijkstra標(biāo)號(hào)算法的計(jì)算步驟如下：（1）令，對(duì)，令，。（2）對(duì)每個(gè)（），令，這里表示頂點(diǎn)和之間邊的權(quán)值，如果此次迭代利用頂點(diǎn)修改了頂點(diǎn)的標(biāo)號(hào)值，則，否則不變。計(jì)算，把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，令。（3）若或進(jìn)入，算法終止；否則，用代替，轉(zhuǎn)（2）。算法結(jié)束時(shí)，從到各頂點(diǎn)的距離由的最后一次標(biāo)號(hào)給出。在進(jìn)入之前的標(biāo)號(hào)叫T標(biāo)號(hào)，進(jìn)入時(shí)的標(biāo)號(hào)叫P標(biāo)號(hào)。算法就是不斷修改各頂點(diǎn)的T標(biāo)號(hào)，直至獲得P標(biāo)號(hào)。若在算法運(yùn)行過程中，將每一頂點(diǎn)獲得P標(biāo)號(hào)所由來的邊在圖上標(biāo)明，則算法結(jié)

17、束時(shí)，至各頂點(diǎn)的最短路也在圖上標(biāo)示出來了。例9. SEQ 例9. * ARABIC 4 求 REF _Ref532649914 h * MERGEFORMAT 圖9.5所示的圖中從到的最短路及最短距離。圖9. SEQ 圖9. * ARABIC 5 求最短距離的圖解 先寫出鄰接矩陣.Dijkstra算法計(jì)算過程的標(biāo)號(hào)值如 REF _Ref532650969 h * MERGEFORMAT 表9.1所示。表9. SEQ 表9. * ARABIC 1 Dijkstra算法計(jì)算過程的標(biāo)號(hào)值迭代次數(shù)01234最終值00887774337557777（或）22從 REF _Ref532650969 h *

18、 MERGEFORMAT 表9.1可以看出，從到的最短路徑長度為7。利用反向追蹤可以得到最短路勁，的前驅(qū)節(jié)點(diǎn)（父節(jié)點(diǎn)）為或，的前驅(qū)節(jié)點(diǎn)為；的前驅(qū)節(jié)點(diǎn)為，的前驅(qū)節(jié)點(diǎn)為；所以可以得到兩條最短路徑，分別為，.MATLAB工具箱求兩個(gè)指定的（單一）頂點(diǎn)最短路函數(shù)為shortestpath，其調(diào)用格式為path,d=shortestpath(G,s,t,Method,algorithm)返回值path是求得的最短路徑，d是求得的最短距離。輸入?yún)?shù)G是圖的鄰接矩陣，s是起點(diǎn)，t是終點(diǎn)，algorithm是一個(gè)字符串，指明屬性Method的值，即所用的求最短路算法，algorithm可以取五種值：（1）au

19、to (缺省值)：自動(dòng)選擇unweighted、positive、mixed三種算法之一。（2）unweighted：非賦權(quán)圖，使用寬度優(yōu)先搜索算法。（3）positive：權(quán)值非負(fù)的賦權(quán)圖，使用Dijkstra算法。（4）mixed：在有向圖中沒有權(quán)值為負(fù)的圈，使用Bellman-Ford算法。（5）acyclic：針對(duì)無圈有向賦權(quán)圖。求解上面最短路問題的MATLAB程序如下：clc, clear, a=zeros(6);a(1,2,3,6)=8,4,2; a(2,3)=4; a(3,4,6)=2,1;a(4,5,6)=2,5; a(5,6)=5; %輸入鄰接矩陣的上三角元素b=a+a; c

20、=graph(b) %構(gòu)造賦權(quán)無向圖p,d=shortestpath(c,1,5) %求頂點(diǎn)1到5的最短路徑和最短距離9.2.2 每對(duì)頂點(diǎn)間的最短路算法利用Dijkstra算法，當(dāng)然還可以尋求賦權(quán)圖中所有頂點(diǎn)對(duì)之間最短路。具體方法是：每次以不同的頂點(diǎn)作為起點(diǎn)，用Dijkstra算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行（為頂點(diǎn)個(gè)數(shù)）次這樣的操作，就可得到每對(duì)頂點(diǎn)之間的最短路。但這樣做需要大量的重復(fù)計(jì)算，效率不高。為此，R. W. Floyd另辟蹊徑，于1962年提出了一個(gè)直接尋求任意兩頂點(diǎn)之間最短路的算法。對(duì)于賦權(quán)圖，其中頂點(diǎn)集，鄰接矩陣，這里（），.對(duì)于無向圖，是對(duì)稱矩陣，。Floyd算

21、法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法，其基本思想是遞推產(chǎn)生一個(gè)矩陣序列，其中矩陣，其第行第列元素表示從頂點(diǎn)到頂點(diǎn)的路徑上所經(jīng)過的頂點(diǎn)序號(hào)不大于的最短路徑長度。計(jì)算時(shí)用迭代公式，是迭代次數(shù)，。最后，當(dāng)時(shí)，即是各頂點(diǎn)之間的最短通路值。如果在求得兩點(diǎn)間的最短距離時(shí)，還需要求得兩點(diǎn)間的最短路徑，需要在上面距離矩陣的迭代過程中，引入一個(gè)路由矩陣來記錄兩點(diǎn)間路徑的前驅(qū)后繼關(guān)系，其中表示從頂點(diǎn)到頂點(diǎn)的路徑經(jīng)過編號(hào)為的頂點(diǎn)。路徑矩陣的迭代過程如下：（1）初始時(shí).（2）迭代公式為，其中直到迭代到，算法終止。查找到最短路徑的方法如下：若，則點(diǎn)是頂點(diǎn)到頂點(diǎn)的最短路的中間點(diǎn)，然后用同樣的方法再分頭查找。若（1）向頂點(diǎn)反向追蹤得

22、：，；（2）向頂點(diǎn)正向追蹤得：，；則由點(diǎn)到的最短路徑為：。MATLAB工具箱求所有頂點(diǎn)對(duì)之間最短距離的命令為distances，其調(diào)用格式為d=distances(G) %該命令只有一個(gè)返回值d，給出了所有頂點(diǎn)對(duì)之間的最短距離矩陣，而沒有給出頂點(diǎn)對(duì)之間的最短路徑。例9. SEQ 例9. * ARABIC 5 設(shè)為 REF _Ref532740033 h * MERGEFORMAT 圖9.6所示有向賦權(quán)圖，求中任意兩頂點(diǎn)之間的最短距離。圖9. SEQ 圖9. * ARABIC 6 有向賦權(quán)圖利用如下的MATLAB程序：clc, clear, a=zeros(5);a(1,2)=50; a(2,5

23、)=80; a(3,2,4)=30,20;a(4,5)=70; a(5,1,3)=60,100; b=digraph(a) %構(gòu)造賦權(quán)有向圖d=distances(b) %求所有頂點(diǎn)對(duì)之間的最短距離求得所有頂點(diǎn)對(duì)之間的最短距離矩陣，從矩陣的第一行可以看出，的最短距離為50，的最短距離為230，的最短距離為250，的最短距離為130。對(duì)于 REF _Ref532755298 h * MERGEFORMAT 例9.5，如果要求所有頂點(diǎn)對(duì)之間的最短距離和最短路徑，我們可以使用Dijkstra算法，調(diào)用10次shortestpath命令即可。如果使用Floyd算法，我們必須自己編程。我們編寫的求 RE

24、F _Ref532755298 h * MERGEFORMAT 例9.5的最短距離和最短路徑的MATLAB程序如下：clc, clear, a=zeros(5);a(1,2)=50; a(2,5)=80; a(3,2,4)=30,20;a(4,5)=70; a(5,1,3)=60,100;b=a; b(b=0)=inf; %構(gòu)造數(shù)學(xué)上的鄰接矩陣bn=size(a,1); %頂點(diǎn)的個(gè)數(shù)b(1:n+1:end)=0 %對(duì)角線元素賦0r=zeros(n); %路由矩陣初始化for k=1:n for i=1:n for j=1:n if b(i,j)b(i,k)+b(k,j) b(i,j)=b(i,

25、k)+b(k,j); r(i,j)=k; end end endendb, r %顯示最短距離矩陣和路由矩陣求得的最短距離矩陣與上面程序是一樣的，求得的路由矩陣.由路由矩陣可知，到的最短路徑為。這是因?yàn)椋ㄗ疃搪窂缴?，的前?qū)頂點(diǎn)為，的后繼頂點(diǎn)為）；（1）反向追蹤：，（的直接前驅(qū)頂點(diǎn)為，不經(jīng)過中間頂點(diǎn)）；（2）正向追蹤：，（的直接后繼頂點(diǎn)為，不經(jīng)過中間頂點(diǎn)）；可知的后繼為，的后繼為，的后繼為，的后繼為，因而得出所求的最短路徑。9.2.3 最短路應(yīng)用范例例9. SEQ 例9. * ARABIC 6（設(shè)備更新問題） 某種工程設(shè)備的役齡為4年，每年年初都面臨著是否更新的問題：若賣舊買新，就要支付一定的購

26、置費(fèi)用；若繼續(xù)使用，則要支付更多的維護(hù)費(fèi)用，且使用年限越長維護(hù)費(fèi)用越多。若役齡期內(nèi)每年的年初購置價(jià)格、當(dāng)年維護(hù)費(fèi)用及年末剩余凈值如 REF _Ref533357268 h * MERGEFORMAT 表9.2所示。請(qǐng)為該設(shè)備制定一個(gè)4年役齡期內(nèi)的更新計(jì)劃，使總的支付費(fèi)用最少。表9. SEQ 表9. * ARABIC 2 相關(guān)費(fèi)用數(shù)據(jù)年份1234年初購置價(jià)格（萬元）25262831當(dāng)年維護(hù)費(fèi)用（萬元）10141826年末剩余凈值（萬元）20161311解 可以把這個(gè)問題化為圖論中的最短路問題。構(gòu)造賦權(quán)有向圖，其中頂點(diǎn)集，這里（）表示第年年初的時(shí)刻，表示第4年年末的時(shí)刻，為弧的集合，鄰接矩陣，這里

27、為第年年初至第年年初（或年年末）期間所支付的費(fèi)用，計(jì)算公式為，其中為第年年初的購置價(jià)格，為使用到第年當(dāng)年的維護(hù)費(fèi)用，為第年年末舊設(shè)備的出售價(jià)格（殘值）。則鄰接矩陣.則制定總的支付費(fèi)用最小的設(shè)備更新計(jì)劃，就是在有向圖中求從到的費(fèi)用最短路。利用Dijkstra算法，使用MATLAB軟件，求得到的最短路徑為，最短路徑的長度為67。設(shè)備更新最小費(fèi)用路徑見 REF _Ref533360496 h * MERGEFORMAT 圖9.7中的粗線所示，即設(shè)備更新計(jì)劃為第1年年初買進(jìn)新設(shè)備，使用到第1年年底，第2年年初購進(jìn)新設(shè)備，使用到第2年年底，第3年年初再購進(jìn)新設(shè)備，使用到第4年年底。圖9. SEQ 圖9.

28、 * ARABIC 7 設(shè)備更新最小費(fèi)用示意圖計(jì)算及畫圖的MATLAB程序如下：clc, clearp=25,26,28,31; a=10,14,18,26; r=20,16,13,11;b=zeros(5); %鄰接矩陣（非數(shù)學(xué)上的鄰接矩陣）初始化for i=1:4 for j=i+1:5 b(i,j)=p(i)+sum(a(1:j-i)-r(j-i); endendb, s=cellstr(strcat(v,int2str(1:5); %構(gòu)造頂點(diǎn)字符串的細(xì)胞數(shù)組c=digraph(b,s); %構(gòu)造賦權(quán)有向圖p,d=shortestpath(c,1,5)h=plot(c,Edgelabel

29、,c.Edges.Weight,Layout,force,EdgeColor,k)highlight(h,p,EdgeColor,r,LineWidth,2)選址問題的類型很多，其中一類是為一個(gè)或幾個(gè)服務(wù)設(shè)施在一定區(qū)域內(nèi)選定它的位置，使某一指標(biāo)達(dá)到最優(yōu)值，具有代表性的是中心問題和重心問題。中心問題 有些公共服務(wù)設(shè)施（例如倉庫、急救中心、消防站等）的選址，要求網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點(diǎn)距離服務(wù)設(shè)施的距離盡可能小。例9. SEQ 例9. * ARABIC 7 某連鎖企業(yè)在某地區(qū)有6個(gè)銷售點(diǎn)，已知該地區(qū)的交通網(wǎng)絡(luò)如 REF _Ref533367468 h * MERGEFORMAT 圖9.8所示，其中點(diǎn)代

30、表銷售點(diǎn)，邊表示公路，邊上的數(shù)字表示銷售點(diǎn)間公路距離，問倉庫應(yīng)建在哪個(gè)銷售點(diǎn)，可使離倉庫最遠(yuǎn)的銷售點(diǎn)到倉庫的路程最近？圖9. SEQ 圖9. * ARABIC 8 銷售點(diǎn)間公路示意圖解 這是個(gè)選址問題，可以化為一系列求最短路問題。先求出到所有點(diǎn)的最短距離，令，表示若倉庫建在，則離倉庫最遠(yuǎn)的銷售點(diǎn)距離為。再依次計(jì)算到所有點(diǎn)的最短距離，類似求出。（）中最小者即為所求，計(jì)算結(jié)果見 REF _Ref533367682 h * MERGEFORMAT 表9.3。表9. SEQ 表9. * ARABIC 3 所有銷售點(diǎn)間的兩兩距離銷售點(diǎn)02033631530632002050254050332003018

31、3333635030048636315251848015483040336315063由于最小，所以倉庫應(yīng)建在，此時(shí)離倉庫最遠(yuǎn)的銷售點(diǎn)（和）距離為33。計(jì)算的MATLAB程序如下clc, clear, a=zeros(6);a(1,2 5)=20 15; a(2,3:5)=20 60 25;a(3,4 5)=30 18; a(5,6)=15; %輸入鄰接矩陣的上三角元素i,j,v=find(a); %找矩陣a中非零元素的行地址、列地址及非零元素的取值b=graph(i,j,v) %MATLAB另一種構(gòu)造無向賦權(quán)圖的方法d=distances(b) %求所有頂點(diǎn)對(duì)之間的最短距離d1=max(d,

32、2) %逐行求最大值d2,ind=min(d1) %求向量的最小值及最小值的地址ind2=find(d(ind,:)=d2) %找ind行中哪個(gè)元素達(dá)到最大值重心問題 有些公共服務(wù)設(shè)施（例如郵局、學(xué)校等）的選址，要求設(shè)施到所有服務(wù)對(duì)象點(diǎn)的距離總和最小。一般要考慮人口密度問題，或者全體被服務(wù)對(duì)象來往的總路程最短。例9. SEQ 例9. * ARABIC 8 某礦區(qū)有七個(gè)產(chǎn)礦點(diǎn)，如 REF _Ref533401600 h * MERGEFORMAT 圖9.9所示。已知各產(chǎn)礦點(diǎn)每天的產(chǎn)礦量（標(biāo)在 REF _Ref533401600 h * MERGEFORMAT 圖9.9的各頂點(diǎn)旁）為噸，現(xiàn)要從這七

33、個(gè)產(chǎn)礦點(diǎn)選一個(gè)來建造選礦廠，問應(yīng)選在哪個(gè)產(chǎn)礦點(diǎn)，才能使各產(chǎn)礦點(diǎn)所產(chǎn)的礦石運(yùn)到選礦廠所在地的總運(yùn)力（噸公里）最小。圖9. SEQ 圖9. * ARABIC 9 各產(chǎn)礦點(diǎn)分布圖解 令表示頂點(diǎn)與之間的距離。若選礦廠設(shè)在并且各產(chǎn)礦點(diǎn)到選礦廠的總運(yùn)力為，則確定選礦廠的位置就轉(zhuǎn)化為求，使得。由于各產(chǎn)礦點(diǎn)到選礦廠的總運(yùn)力依賴于任意兩頂點(diǎn)之間的距離，即任意兩頂點(diǎn)之間最短路的長度，因此可首先利用Floyd算法求出所有頂點(diǎn)對(duì)之間的最短距離，然后計(jì)算出頂點(diǎn)設(shè)立選礦廠時(shí)各產(chǎn)礦點(diǎn)到的總運(yùn)力.具體的計(jì)算結(jié)果見 REF _Ref533403361 h * MERGEFORMAT 表9.4。表9. SEQ 表9. * ARA

34、BIC 4 各頂點(diǎn)對(duì)之間的最短距離和總運(yùn)力計(jì)算數(shù)據(jù)產(chǎn)礦點(diǎn)總運(yùn)力0202555153048502002040254049002520030102552505540300405511850152510400154700304025551508750最后利用，求得為設(shè)置選礦廠的位置。計(jì)算的MATLAB程序如下：clc, clear, a=zeros(6);a(1,2 5)=20 15; a(2,3:5)=20 40 25;a(3,4 5)=30 10; a(5,6)=15; %輸入鄰接矩陣的上三角元素b=graph(a+a); %構(gòu)造賦權(quán)無向圖d=distances(b) %求所有頂點(diǎn)對(duì)之間的最短距

35、離q=80,90,30,20,60,10; m=d*q %計(jì)算總運(yùn)力mm,ind=min(m) %求最小運(yùn)力9.3 最小生成樹算法及其MATLAB實(shí)現(xiàn)樹（tree）是圖論中非常重要的一類圖，它非常類似于自然界中的樹，結(jié)構(gòu)簡單、應(yīng)用廣泛，最小生成樹問題則是其中的經(jīng)典問題之一。在實(shí)際應(yīng)用中，許多問題的圖論模型都是最小生成樹，如通信網(wǎng)絡(luò)建設(shè)、集成電話設(shè)計(jì)、有線電纜鋪設(shè)、加工設(shè)備分組等。9.3.1 基本概念定義9. SEQ 定義9. * ARABIC 8 連通的無圈圖稱為樹。 例如， REF _Ref532765073 h * MERGEFORMAT 圖9.10給出的是樹，但和則不是樹。圖9. SEQ

36、 圖9. * ARABIC 10 樹與非樹定理9. SEQ 定理9. * ARABIC 2 設(shè)是具有個(gè)頂點(diǎn)條邊的圖，則以下命題等價(jià)。（1）圖是樹；（2）圖中任意兩個(gè)不同頂點(diǎn)之間存在唯一的路。（3）圖連通，刪除任一條邊均不連通；（4）圖連通，且；（5）圖無圈，添加任一條邊可得唯一的圈；（6）圖無圈，且。定義9. SEQ 定義9. * ARABIC 9 若圖的生成子圖是樹，則稱為的生成樹或支撐樹。一個(gè)圖的生成樹通常不唯一。定理9. SEQ 定理9. * ARABIC 3 連通圖的生成樹一定存在。 證明 給定連通圖，若無圈，則本身就是自己的生成樹。若有圈，則任取中一個(gè)圈，記刪除中一條邊后所得之圖為。

37、顯然中圈已經(jīng)不存在，但仍然連通。若中還有圈，再重復(fù)以上過程，直至得到一個(gè)無圈的連通圖。易知是的生成樹。 REF _Ref533144613 h * MERGEFORMAT 定理9.3的證明方法也是求生成樹的一種方法，稱為“破圈法”。定義9. SEQ 定義9. * ARABIC 10 在賦權(quán)圖中，邊權(quán)之和最小的生成樹稱為的最小生成樹。一個(gè)簡單連通圖只要不是樹，其生成樹就不唯一，而且非常多。一般地，個(gè)頂點(diǎn)的完全圖，其不同生成樹的個(gè)數(shù)為。因而，尋求一個(gè)給定賦權(quán)圖的最小生成樹，一般是不能用枚舉法的。例如，20個(gè)頂點(diǎn)的完全圖有個(gè)生成樹，有24位。所以，通過枚舉求最小生成樹是無效的算法，必須尋求有效的算法

38、。9.3.2 求最小生成樹的算法對(duì)于賦權(quán)連通圖，其中為頂點(diǎn)集合，為邊的集合，為鄰接矩陣，這里頂點(diǎn)集合中有個(gè)頂點(diǎn)，構(gòu)造它的最小生成樹。構(gòu)造連通圖最小生成樹的算法有Kruskal算法和Prim算法。1.Kruskal算法Kruskal算法思想：每次將一條權(quán)最小的邊加入子圖中，并保證不形成圈。Kruskal算法如下：（1）選，使得是權(quán)值最小的邊。（2）若已選好，則從中選取，使得中無圈，且是中權(quán)值最小的邊。（3）直到選得為止。例9. SEQ 例9. * ARABIC 9 用Kruskal算法求如 REF _Ref533188840 h * MERGEFORMAT 圖9.11所示連通圖的最小生成樹。圖9

39、. SEQ 圖9. * ARABIC 11 構(gòu)造最小生成樹的連通圖解 首先將給定圖的邊按照權(quán)值從小到大進(jìn)行排序，如 REF _Ref533189795 h * MERGEFORMAT 表9.5所列。表9. SEQ 表9. * ARABIC 5 按照權(quán)值排列的邊數(shù)據(jù)邊取值1224458其次，依照Kruskal算法的步驟，迭代4步完成最小生成樹的構(gòu)造。按照邊的排列順序，前三次取定，；由于下一個(gè)未選邊中的最小權(quán)邊與已選邊構(gòu)成圈，所以排除，第4次選，得到 REF _Ref533190637 h * MERGEFORMAT 圖9.12就是圖的一顆最小生成樹，它的權(quán)值是9。圖9. SEQ 圖9. * AR

40、ABIC 12 生成的最小生成樹2.Prim算法設(shè)置兩個(gè)集合和,其中用于存放的最小生成樹中的頂點(diǎn)，集合存放的最小生成樹中的邊。令集合的初值為（假設(shè)構(gòu)造最小生成樹時(shí)，從頂點(diǎn)出發(fā)），集合的初值為（空集）。Prim算法的思想是，從所有，的邊中，選取具有最小權(quán)值的邊，將頂點(diǎn)加入集合中，將邊加入集合中，如此不斷重復(fù)，直到時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合中包含了最小生成樹的所有邊。Prim算法如下：（1），；（2）while 找最小邊，其中； ； ； end例9. SEQ 例9. * ARABIC 10（續(xù) REF _Ref533227469 h * MERGEFORMAT 例9.9） 用Prim算法求如

41、 REF _Ref533188840 h * MERGEFORMAT 圖9.11所示連通圖的最小生成樹。解 按照Prim算法的步驟，迭代4步完成最小生成樹的構(gòu)造。（0）第0步初始化，頂點(diǎn)集，邊集；（1）第1步，找到最小邊，；（2）第2步，找到最小邊，；（3）第3步，找到最小邊，；（4）第4步，找到最小邊，；最小生成樹構(gòu)造完畢。9.3.3 用MATLAB求最小生成樹及應(yīng)用 1.MATLAB求最小生成樹命令minspantreeMATLAB工具箱提供了一個(gè)求最小生成樹的函數(shù)minspantree，利用這個(gè)函數(shù)可以實(shí)現(xiàn)求最小生成樹的Prim算法和Kruskal算法。其調(diào)用格式為：T=minspant

42、ree(G, Method,Value) 其中G為輸入的圖，Value的取值有兩種：（1）dense：為缺省值，使用Prim算法。（2）sparse：使用Kruskal算法。返回值T為所求得的最小生成樹。例9. SEQ 例9. * ARABIC 11（續(xù) REF _Ref533227469 h * MERGEFORMAT 例9.9） 利用MATLAB的Kruskal算法求 REF _Ref533227469 h * MERGEFORMAT 例9.9的最小生成樹。利用MATLAB求出的最小生成樹的權(quán)值為9，所求的最小樹如 REF _Ref533342232 h * MERGEFORMAT 圖9.

43、13的粗線所示。圖9. SEQ 圖9. * ARABIC 13 MATLAB所畫出的最小生成樹計(jì)算及畫圖的MATLAB程序如下：clc, clear, a=zeros(5);a(1,2,3,5)=8,4,2; a(2,3)=4; %輸入鄰接矩陣上三角元素a(3,4,5)=2,1; a(4,5)=5;s=cellstr(strcat(v,int2str(1:5); %構(gòu)造頂點(diǎn)字符串的細(xì)胞數(shù)據(jù)b=graph(a+a,s); %構(gòu)造無向賦權(quán)圖c=minspantree(b,Method,sparse) %求最小生成樹L=sum(c.Edges.Weight) %求最小生成樹的權(quán)值h=plot(b,E

44、dgelabel,b.Edges.Weight,Layout,subspace); highlight(h,c) %加粗顯示所生成的最小生成樹2.分組技術(shù)分組技術(shù)是設(shè)計(jì)制造系統(tǒng)的一種方法，它把生產(chǎn)零件的機(jī)器分組，相應(yīng)地把需生產(chǎn)的零件分類，使零件跨組加工的情形盡量少。最理想的情況是使每個(gè)零件的加工都在組內(nèi)完成。例9. SEQ 例9. * ARABIC 12 現(xiàn)有13種零件，需在9臺(tái)機(jī)器上加工。在各臺(tái)機(jī)器上加工的零件號(hào)如 REF _Ref533449704 h * MERGEFORMAT 表9.6所列。請(qǐng)將這9臺(tái)機(jī)器分為3組，使零件跨組加工的情形盡量少。表9. SEQ 表9. * ARABIC 6

45、 各臺(tái)機(jī)器上加工的零件號(hào)機(jī)器123456789加工的零件號(hào)2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,106解 構(gòu)造賦權(quán)圖，其中，這里表示機(jī)器；為邊的集合；為鄰接矩陣，其元素，這里表示需由機(jī)器加工的零件集合，“”表示對(duì)稱差，表示集合中元素的個(gè)數(shù)，表示機(jī)器和的相異度。顯然，表達(dá)了兩臺(tái)不同機(jī)器加工零件的相異程度。分子為在機(jī)器但不在機(jī)器上加工，或在機(jī)器但不在機(jī)器上加工的零件數(shù)；分母為在機(jī)器或在機(jī)器上加工的零件數(shù)。特別地，表示機(jī)器與機(jī)器加工的零件完全相同；表示機(jī)器與機(jī)器加工的零件完全不相同。圖的最小生成樹是由那些相異度最小的邊構(gòu)成的連通

46、圖，或看成是去掉了相異度相對(duì)比較大的邊后余下的連通圖。如果希望把機(jī)器分成個(gè)組，就繼續(xù)刪去最小生成樹上權(quán)值最大的條邊。于是得到個(gè)分離的子樹，每棵樹的頂點(diǎn)就構(gòu)成了各機(jī)器組。利用 REF _Ref533449704 h * MERGEFORMAT 表9.6給出的數(shù)據(jù)，求得鄰接矩陣，利用Prim算法求得的最小樹如 REF _Ref533573767 h * MERGEFORMAT 圖9.14所示。將最小生成樹中權(quán)值最大的兩條邊和去掉，得到三顆分離樹，它們的頂點(diǎn)集分別為，。因此，將9臺(tái)機(jī)器按照標(biāo)號(hào)，分為3組時(shí)，可使零件跨組加工的情形盡量少。圖9. SEQ 圖9. * ARABIC 14 分組問題的最小生成樹計(jì)算及畫圖的MATLAB程序如下：clc, clear, close alla,b=xlsread(gdata9_12_1.xlsx);a(isnan(a)= %刪除a中的不確定值NaNk=1;