最短路徑問題

數(shù)學(xué)建模講座主講人：王曉峰內(nèi)容1：數(shù)學(xué)建模及其競賽2：中國大學(xué)生數(shù)學(xué)建模競賽歷程3：建模過程與方法4：建模案例分析5：數(shù)學(xué)建模論文的撰寫1.數(shù)學(xué)建模及其競賽

——什么是數(shù)學(xué)建模數(shù)學(xué)建模是構(gòu)造刻劃客觀事物原型的數(shù)學(xué)模型并用以分析、研究和解決實際問題的一種科學(xué)方法。運用這種科學(xué)方法，必須從實際問題出發(fā)，遵循從實踐到認(rèn)識再實踐的認(rèn)識規(guī)律，圍繞建模的目的，運用觀察力、想象力的抽象概括能力，對實際問題進行抽象、簡化，反復(fù)探索，逐步完善，直到構(gòu)造出一個能夠用于分析、研究和解決實際問題的數(shù)學(xué)模型。因此，數(shù)學(xué)建模是一種定量解決實際問題的創(chuàng)新過程。1.數(shù)學(xué)建模及其競賽

——數(shù)學(xué)建模競賽題目

數(shù)學(xué)建模競賽的題目由日常生活、工程技術(shù)、經(jīng)濟管理、社會生活等領(lǐng)域中的實際問題簡化加工而成，它對數(shù)學(xué)知識要求不一定深，一般沒有事先設(shè)定的標(biāo)準(zhǔn)答案，但留有充分余地供參賽者發(fā)揮其聰明才智和創(chuàng)造精神。從下面一些題目的標(biāo)題可以看出其實用性和挑戰(zhàn)性：“DNA序列分類”、“血管的三維重建”、“公交車調(diào)度”、“SARS的傳播”、“奧運會臨時超市網(wǎng)點設(shè)計”、“長江水質(zhì)的評價和預(yù)測”——1.數(shù)學(xué)建模及其競賽

——數(shù)學(xué)建模競賽題目1998A、投資的收益和風(fēng)險；B、災(zāi)情巡視路線1999A、自動化車床管理；B、鉆井布局2000A、DNA序列分類；B、鋼管訂購和運輸；2001A、血管的三維重建；B、公交車調(diào)度；2002A、車燈線光源優(yōu)化設(shè)計；B、彩票中的數(shù)學(xué)；2003A、SARS的傳播；B、露天礦生產(chǎn)的車輛安排；2004A、奧運會臨時超市網(wǎng)點設(shè)計；B、電力市場的輸電阻塞管理；2005A、長江水質(zhì)的評價和預(yù)測；B、DVD在線租賃；2006A、出版社的資源配置；B、艾滋病療法的評價及療效的預(yù)測；A、國人口增長預(yù)測；B、乘公交，看奧運。

A、數(shù)碼相機定位;B、高等教育學(xué)費標(biāo)準(zhǔn)探討A、制動器試驗臺的控制方法分析B、眼科病床的合理安排A、儲油罐的變位識別與罐容表標(biāo)定B、2010年上海世博會影響力的定量評估1.數(shù)學(xué)建模及其競賽

——數(shù)學(xué)建模競賽的形式

競賽評獎以假設(shè)的合理性、建模的創(chuàng)造性、結(jié)果的正確性和文字表述的清晰程度為主要標(biāo)準(zhǔn)?？梢钥闯?，這項競賽從內(nèi)容到形式與傳統(tǒng)的數(shù)學(xué)競賽不同，既豐富、活躍了廣大同學(xué)的課外生活，也為優(yōu)秀學(xué)生脫穎而出創(chuàng)造了條件。數(shù)學(xué)建模競賽以通訊形式進行。三名大學(xué)生組成一隊，可自由地收集資料、調(diào)查研究，使用計算機和任何軟件，甚至上網(wǎng)查詢，但不得與隊外任何人包括指導(dǎo)教師討論。時間：三天。要求每個隊完成一篇包括模型的假設(shè)、建立和求解，計算方法的設(shè)計和計算機實現(xiàn)，結(jié)果的分析和檢驗，模型的改進等方面的論文。1.數(shù)學(xué)建模及其競賽

——數(shù)學(xué)建模競賽的特點競賽讓同學(xué)們面對一個從未接觸過的實際問題，運用數(shù)學(xué)方法和計算機技術(shù)加以分析、解決，他們必須開動腦筋、拓寬思路，充分發(fā)揮創(chuàng)造力和想象力，培養(yǎng)同學(xué)們創(chuàng)新意識及主動學(xué)習(xí)、獨立研究的能力。競賽緊密結(jié)合社會熱點問題，富有挑戰(zhàn)性，吸引著學(xué)生關(guān)心、投身國家的各項建設(shè)事業(yè)，培養(yǎng)他們理論聯(lián)系實際的學(xué)風(fēng)。競賽需要學(xué)生在很短時間內(nèi)獲取與賽題有關(guān)的知識，鍛煉同學(xué)們收集資料的能力，提高撰寫科技論文的文字表達水平。競賽要三個同學(xué)共同完成一篇論文，在競賽中要分工合作、取長補短、求同存異，既有相互啟發(fā)，也有相互爭論，培養(yǎng)了學(xué)生們同舟共濟的團隊精神和進行協(xié)調(diào)的組織能力。競賽是開放型的，三天中沒有或者很少有外部的強制約束，同學(xué)們要自覺地遵守競賽紀(jì)律，公平地開展競爭。誠信意識和自律精神是建設(shè)和諧社會的基本要素之一，同學(xué)們能在競賽中得到這種品格鍛煉對他們的一生是非常有益的。

內(nèi)容1：數(shù)學(xué)建模及其競賽2：中國大學(xué)生數(shù)學(xué)建模競賽歷程3：建模過程與方法3：建模案例分析4：數(shù)學(xué)建模論文的撰寫中國大學(xué)生數(shù)學(xué)建模競賽歷程（1）

1988.6大學(xué)生數(shù)學(xué)建模競賽最早是1985年在美國出現(xiàn)的，葉其孝教授在美國講學(xué)期間向美國大學(xué)生數(shù)學(xué)建模競賽發(fā)起者和負責(zé)人Fusaro教授了解這項競賽的情況，商討中國學(xué)生參賽的辦法和規(guī)則。1989.2.24～26

我國大學(xué)生（北京大學(xué)、清華大學(xué)、北京理工大學(xué)共4個隊）首次參加美國大學(xué)生數(shù)學(xué)建模競賽，自此每年我國都有同學(xué)參加這項競賽。中國大學(xué)生數(shù)學(xué)建模競賽歷程（2）1989.3《高校應(yīng)用數(shù)學(xué)學(xué)報》第4卷第1期發(fā)表葉其孝教授的文章“美國大學(xué)生數(shù)學(xué)建模競賽及一些想法”，第一次向國內(nèi)介紹這項競賽。1990.12.7～9上海市舉辦大學(xué)生（數(shù)學(xué)類）數(shù)學(xué)模型競賽，這是我國省、市級首次舉辦數(shù)學(xué)建模競賽。中國大學(xué)生數(shù)學(xué)建模競賽歷程（3）1992.11.27～291992年部分城市大學(xué)生數(shù)學(xué)模型聯(lián)賽舉行，這是全國性的首屆競賽，10省（市）79所院校的314隊參加。1993.10.15～171993年全國大學(xué)生數(shù)學(xué)建模競賽舉行，16?。ㄊ校?01所院校的420隊參加。中國大學(xué)生數(shù)學(xué)建模競賽歷程（4）1994.10.28～301994年全國大學(xué)生數(shù)學(xué)建模競賽舉行，21?。ㄊ?、自治區(qū)）196所院校的870隊參加。內(nèi)容1：數(shù)學(xué)建模及其競賽2：中國大學(xué)生數(shù)學(xué)建模競賽歷程3：建模過程與方法4：建模案例分析5：數(shù)學(xué)建模論文的撰寫3.建模過程簡介

----什么是數(shù)學(xué)建模

把現(xiàn)實世界中的實際問題加以提煉，抽象為數(shù)學(xué)模型，求出模型的解，驗證模型的合理性，并用該數(shù)學(xué)模型所提供的解答來解釋現(xiàn)實問題，我們把數(shù)學(xué)知識的這一應(yīng)用過程稱為數(shù)學(xué)建模。3.建模過程簡介

----數(shù)學(xué)建模的幾個過程（1）模型準(zhǔn)備（2）模型假設(shè)（3）模型建立（4）模型構(gòu)成（5）模型求解（6）模型分析（7）模型檢驗（8）模型應(yīng)用

（1）模型準(zhǔn)備

了解問題的實際背景，明確其實際意義與建模目的，掌握對象的各種信息（要收集）。用數(shù)學(xué)語言來描述問題。（2）模型假設(shè)

根據(jù)實際對象的特征和建模的目的，對問題進行必要的、合理的簡化，并用精確的語言提出一些恰當(dāng)?shù)募僭O(shè)，是建模至關(guān)重要的一步。如果對問題的所有因素一概考慮，是不現(xiàn)實的，所以高超的建模者能充分發(fā)揮想象力、洞察力和判斷力，善于辨別主次，而且為了使處理方法簡單，應(yīng)盡量使問題線性化、均勻化。

（3）模型建立

在假設(shè)的基礎(chǔ)上，利用適當(dāng)?shù)臄?shù)學(xué)工具來刻劃各變量之間的數(shù)學(xué)關(guān)系，建立相應(yīng)的數(shù)學(xué)結(jié)構(gòu)。（盡量用簡單的數(shù)學(xué)工具）（4）模型構(gòu)成

根據(jù)所作的假設(shè)分析對象的因果關(guān)系，利用對象的內(nèi)在規(guī)律和適當(dāng)?shù)臄?shù)學(xué)工具，構(gòu)造各個量間的等式關(guān)系或其它數(shù)學(xué)結(jié)構(gòu)。有高數(shù)、概率統(tǒng)計、圖論、排隊論、線性規(guī)劃、對策論等等。提示：建立數(shù)學(xué)模型是為了讓更多的人明了并能加以應(yīng)用，因此工具愈簡單愈有價值。

（5）模型求解

利用獲取的數(shù)據(jù)資料，對模型的所有參數(shù)做出計算（估計）?？梢圆捎媒夥匠?、畫圖形、證明定理、邏輯運算、數(shù)值運算等各種傳統(tǒng)的和近代的數(shù)學(xué)方法，特別是計算機技術(shù)。實際問題的解決往往需要紛繁的計算，許多時候還得將系統(tǒng)運行情況用計算機模擬出來，因此編程和熟悉數(shù)學(xué)軟件的能力非常重要。（6）模型檢驗

將模型分析結(jié)果與實際情形進行比較，以此來驗證模型的準(zhǔn)確性、合理性和適用性。如果模型與實際較吻合，則要對計算結(jié)果給出其實際含義，并進行解釋。如果模型與實際吻合較差,則應(yīng)該修改假設(shè)，在次重復(fù)建模過程。3.建模過程與方法

----建模全過程示意圖3.建模過程與方法

----具備的數(shù)學(xué)知識1、數(shù)學(xué)分析2、高等代數(shù)3、概率與數(shù)理統(tǒng)計4、最優(yōu)化理論5、圖論6、組合數(shù)學(xué)7、微分方程穩(wěn)定性分析8、排隊論3.建模過程與方法

----具備的應(yīng)用軟件知識1、綜合類：Matlab,Mathematic2、統(tǒng)計類：Spss,SAS,Statistics3、最優(yōu)解：Lindo,Lingo3.建模過程與方法

----圖論方法最短路問題兩個指定頂點之間的最短路徑—給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，找一條最短鐵路線（Dijkstra算法）每對頂點之間的最短路徑（Dijkstra算法、Floyd算法）最小生成樹問題連線問題—欲修筑連接多個城市的鐵路設(shè)計一個線路圖，使總造價最低（prim算法、Kruskal算法）圖的匹配問題人員分派問題：n個工作人員去做件n份工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？(匈牙利算法)遍歷性問題中國郵遞員問題—郵遞員發(fā)送郵件時，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行程最短的路線最大流問題運輸問題最小費用最大流問題在運輸問題中，人們總是希望在完成運輸任務(wù)的同時，尋求一個使總的運輸費用最小的運輸方案3.建模過程與方法

----圖論方法（1）基本概念（2）固定起點的最短路（3）每對頂點之間的最短路3.建模過程與方法

----最短路問題基本概念固定起點的最短路

從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短?交通網(wǎng)絡(luò)可用帶權(quán)圖來表示。頂點表示城市名稱，邊表示兩個城市有路連通，邊上的權(quán)值可表示兩城市之間的距離、交通費或途中所花費的時間等。求兩個頂點之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。另外，若兩個頂點之間沒有邊，則認(rèn)為兩個頂點無通路，但有可能有間接通路(從其它頂點達到)。路徑上的開始頂點(出發(fā)點)稱為源點，路徑上的最后一個頂點稱為終點，并假定討論的權(quán)值不能為負數(shù)。從一個頂點到其余各頂點的最短路徑

問題：給定一個帶權(quán)有向圖G與源點v,求從v到G中其他頂點的最短路徑,并限定各邊上的權(quán)值大于或等于0。

采用狄克斯特拉(Dijkstra)算法求解基本思想是：設(shè)G=(V,E)是一個帶權(quán)有向圖,把圖中頂點集合V分成兩組：第一組為已求出最短路徑的頂點集合(用S表示,初始時S中只有一個源點,以后每求得一條最短路徑v,…vk,就將vk加入到集合S中,直到全部頂點都加入到S中,算法就結(jié)束了)第二組為其余未確定最短路徑的頂點集合(用U表示)。按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中,總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外,每個頂點對應(yīng)一個距離,S中的頂點的距離就是從v到此頂點的最短路徑長度,U中的頂點的距離從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。狄克斯特拉算法的具體步驟如下：(1)初始時,S只包含源點,即S={v},v的距離為0。U包含除v外的其他頂點,U中頂點u距離為邊上的權(quán)(若v與u有邊<v,u>)或∞(若u不是v的出邊鄰接點)。(2)從U中選取一個距離v最小的頂點k,把k加入S中(該選定的距離就是v到k的最短路徑長度)。(3)以k為新考慮的中間點,修改U中各頂點的距離：若從源點v到頂點u(u∈U)的距離(經(jīng)過頂點k)比原來距離(不經(jīng)過頂點k)短,則修改頂點u的距離值,修改后的距離值的頂點k的距離加上邊<k,u>上的權(quán)。(4)重復(fù)步驟(2)和(3)直到所有頂點都包含在S中。S U v0到0～6各頂點的距離{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,1}{2,3,4,5,6}

{0,4,5,6,11,∞,∞}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,19}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}則v0到v1～v6各頂點的最短距離分別為4、5、6、10、9和16。狄克斯特拉算法如下(n為圖G的頂點數(shù),v0為源點編號)：voidDijkstra(intcost[][MAXV],intn,intv0){intdist[MAXV],path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;i<n;i++){dist[i]=cost[v0][i]; /*距離初始化*/ s[i]=0; /*s[]置空*/ if(cost[v0][i]<INF) /*路徑初始化*/ path[i]=v0; else path[i]=-1; } s[v0]=1;path[v0]=0; /*源點編號v0放入s中*/

for(i=0;i<n;i++)/*循環(huán)直到所有頂點的最短路徑都求出*/{mindis=INF; u=-1; for(j=0;j<n;j++)/*選取不在s中且具有最小距離的頂點u*/ if(s[j]==0&&dist[j]<mindis) {u=j;mindis=dist[j]; } s[u]=1; /*頂點u加入s中*/ for(j=0;j<n;j++)/*修改不在s中的頂點的距離*/ if(s[j]==0) if(cost[u][j]<INF&&dist[u]+cost[u][j]<dist[j]) {dist[j]=dist[u]+cost[u][j];path[j]=u;}}Dispath(dist,path,s,n,v0); /*輸出最短路徑*/}voidPpath(intpath[],inti,intv0)/*前向遞歸查找路徑上的頂點*/{intk;k=path[i];if(k==v0)return; /*找到了起點則返回*/Ppath(path,k,v0); /*找k頂點的前一個頂點*/printf("%d,",k); /*輸出k頂點*/}voidDispath(intdist[],intpath[],ints[],intn,intv0){inti;for(i=0;i<n;i++) if(s[i]==1) {printf(“從%d到%d的最短路徑長度為:%d\t路徑為:",v0,i,dist[i]); printf("%d,",v0); /*輸出路徑上的起點*/Ppath(path,i,v0); /*輸出路徑上的中間點*/printf("%d\n",i); /*輸出路徑上的終點*/ } elseprintf("從%d到%d不存在路徑\n",v0,i);}每對頂點之間的最短路徑

問題：對于一個各邊權(quán)值均大于零的有向圖,對每一對頂點vi≠vj,求出vi與vj之間的最短路徑和最短路徑長度。

可以通過以每個頂點作為源點循環(huán)求出每對頂點之間的最短路徑。除此之外,弗洛伊德(Floyd)算法也可用于求兩頂點之間最短路徑。

假設(shè)有向圖G=(V,E)采用鄰接矩陣cost存儲,另外設(shè)置一個二維數(shù)組A用于存放當(dāng)前頂點之間的最短路徑長度,分量A[i][j]表示當(dāng)前頂點vi到頂點vj的最短路徑長度。弗洛伊德算法的基本思想是遞推產(chǎn)生一個矩陣序列A0,A1,…,Ak,…,An,其中Ak[i][j]表示從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k的最短路徑長度。

初始時,有A-1[i][j]=cost[i][j]。當(dāng)求從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k+1的最短路徑長度時,要分兩種情況考慮：一種情況是該路徑不經(jīng)過頂點編號為k+1的頂點,此時該路徑長度與從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k的最短路徑長度相同；另一種情況是從頂點vi到頂點vj的最短路徑上經(jīng)過編號為k+1的頂點。那么,該路徑可分為兩段,一段是從頂點vi到頂點vk+1的最短路徑,另一段是從頂點vk+1到頂點vj的最短路徑,此時最短路徑長度等于這兩段路徑長度之和。這兩種情況中的較小值,就是所要求的從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k+1的最短路徑。

弗洛伊德思想可用如下的表達式來描述：A-1[i][j]=cost[i][j]Ak+1[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤k≤n-1)

采用弗洛伊德算法求解過程

考慮頂點v0,A0[i][j]表示由vi到vj,經(jīng)由頂點v0的最短路徑。只有從v2到v1經(jīng)過v0的路徑和從v2到v3經(jīng)過v0的路徑,不影響v2到v1和v2到v3的路徑長度,因此,有：

考慮頂點v1,A1[i][j]表示由vi到vj,經(jīng)由頂點v1的最短路徑。存在路徑v0-v1-v2,路徑長度為9,將A[0][2]改為9,path[0][2]改為1,因此,有：

考慮頂點v2,A2[i][j]表示由vi到vj,經(jīng)由頂點v2的最短路徑。存在路徑v3-v2-v0,長度為4,將A[3][0]改為4；存在路徑v3-v2-v1,長度為4,將A[3][1]改為4。存在路徑v1-v2-v0,長度為7,將A[1][0]改為7。將path[3][0]、path[3][1]和path[1][0]均改為2。因此,有：

考慮頂點v3,A3[i][j]表示由vi到vj,經(jīng)由頂點v3的最短路徑。存在路徑v0-v3-v2,長度為8比原長度短,將A[0][2]改為8；存在路徑v1-v3-v2-v0,長度為6(A[1][3]+A[3][0]=2+4=6)比原長度短,將A[1][0]改為6；存在路徑v1-v3-v2,長度為3,比原長度短,將A[1][2]改為3；將path[0][2]、path[1][0]后path[1][2]均改為3。因此,有：

因此,最后求得的各頂點最短路徑長度A和Path矩陣為：

從0到0路徑為：0,0 路徑長度為：0從0到1路徑為：0,1 路徑長度為：5從0到2路徑為：0,3,2 路徑長度為：8從0到3路徑為：0,3 路徑長度為：7從1到0路徑為：1,3,2,0 路徑長度為：6從1到1路徑為：1,1 路徑長度為：0從1到2路徑為：1,3,2 路徑長度為：3從1到3路徑為：1,3 路徑長度為：2從2到0路徑為：2,0 路徑長度為：3從2到1路徑為：2,1 路徑長度為：3從2到2路徑為：2,2 路徑長度為：0從2到3路徑為：2,3 路徑長度為：2從3到0路徑為：3,2,0 路徑長度為：4從3到1路徑為：3,2,1 路徑長度為：4從3到2路徑為：3,2 路徑長度為：1從3到3路徑為：3,3 路徑長度為：0弗洛伊德算法如下：voidFloyd(intcost[][MAXV],intn){intA[MAXV][MAXV],path[MAXV][MAXV];inti,j,k;for(i=0;i<n;i++) for(j=0;j<n;j++){A[i][j]=cost[i][j]; path[i][j]=-1;}for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(A[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}Dispath(A,path,n);/*輸出最短路徑*/}樹的定義和基本術(shù)語

1、樹的定義

樹是由n（n≥0）個結(jié)點組成的有限集合。若n=0，稱為空樹；若n>0，則：

（1）有且僅有一個特定的稱為根（root）的結(jié)點。它只有直接后繼，但沒有直接前驅(qū)；

（2）除根結(jié)點以外的其它結(jié)點可以劃分為m（m≥0）個互不相交的有限集合T0，T1，…，Tm-1，每個集合Ti（i=0,1,…,m-1）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。

由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。

樹的結(jié)構(gòu)參見圖6-1。

3.建模過程與方法-最小生成樹問題

一、最小生成樹（MST）概念1.設(shè)無向連通圖G=（V，{E}），其子圖G’=（V，{T}）滿足：①V(G’)=V(G)n個頂點②G’是連通的③G’中無回路則G’是G的生成樹2.最小生成樹：一個有n個結(jié)點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有n個結(jié)點，并且有保持圖聯(lián)通的最少的邊。3.建模過程與方法-最小生成樹問題

具有n個頂點的無向連通圖G

其任一生成樹恰好含n-1條邊

生成樹不一定唯一，如深度優(yōu)先搜索生成樹和廣度優(yōu)先搜索生成樹。4.生成樹代價:對圖中每條邊賦于一個權(quán)值（代價），則構(gòu)成一個網(wǎng)，網(wǎng)的生成樹G’=(V，{T})的代價是T中各邊的權(quán)值之和，最小生成樹就是網(wǎng)上所有可能的生成樹中，代價最小的一類生成樹。最小生成樹也不一定唯一。5.求MST的一般算法可描述為：針對圖G，從空樹T開始，往集合T中逐條選擇并加入n-1條安全邊(u，v)，最終生成一棵含n-1條邊的MST。當(dāng)一條邊(u，v)加入T時，必須保證T∪{(u，v)}仍是MST的子集，我們將這樣的邊稱為T的安全邊。

3.最小生成樹性質(zhì)：設(shè)G=(V，E)是一個連通網(wǎng)絡(luò)，U是頂點集V的一個真子集。若(u，v)是G中一條“一個端點在U中(例如：u∈U)，另一個端點不在U中的邊(例如：v∈V-U)，且(u，v)具有最小權(quán)值，則一定存在G的一棵最小生成樹包括此邊(u，v)。許多應(yīng)用問題都是求無向連通圖的最小生成樹問題。例1：要在n個城市之間鋪設(shè)光纜，主要目標(biāo)是要使這n個城市的任意兩個之間都可以通信，但鋪設(shè)光纜的費用很高，且各個城市之間鋪設(shè)光纜的費用不同；另一個目標(biāo)是要使鋪設(shè)光纜的總費用最低。這就需要找到帶權(quán)的最小生成樹。

例2：N臺計算機之間建立通訊網(wǎng)頂點表示computer邊表示通訊線權(quán)值表示通訊線的代價（通訊線長度，computer間距離等）要求：①n臺計算機中的任何兩臺能通過網(wǎng)進行通訊；②使總的代價最小。-------求最小生成樹[T]

最小生成樹的實用例子例3：郵遞員送信線路[T]頂點表示投遞點邊表示街道權(quán)值表示街道的長度要求：①完成n個投遞點的投遞；②使總路徑長度最短,即求最小生成樹[T]設(shè)N=（V，{E}）是一個連通網(wǎng)，V=[1，2，…，n}是N的頂點集合，輔助集合U，初值為{Uo}，用來存放當(dāng)前所得到的最小生成樹的頂點；輔助集合TE，初值為Ф，用來存放當(dāng)前所得到的最小生成樹的邊。1）普里姆（Prim）算法Prim算法步驟1.TE=Ф,U={u0}2.當(dāng)U≠V，重復(fù)下列步驟：(1)選取（u0,v0)=min{cost(u,v)|u∈U,v∈V-U}，保證不形成回路(2)TE=TE+（u0,v0),邊（u0,v0)并入TE(3)U=U+{V0}，頂點V0并入U初始化：①②①④⑤

521③3466556⑥

①1③第1步：6①1③4第2步：④6①1③42第3步：5②④6①1③42第4步：23⑤

②5④6①1③4第5步：特點:以連通為主選代價最小的鄰接邊Prim算法的實現(xiàn)voidgraph::mintree(charu){ for(intk=0;k<vexnum;k++) if(vexs[k]==u) break; for(intj=0;j<vexnum;j++) if(j!=k) { closedge[j].index=k; closedge[j].lowcost=arcs[k][j]; }//給結(jié)構(gòu)體數(shù)組賦值 closedge[k].lowcost=0;//初始化 for(inti=1;i<vexnum;i++) {//找到與頂點u相鄰的權(quán)值最小的 intk=closedge[0].lowcost; for(intx=0;x<vexnum;x++)

（鄰接矩陣存儲）if(closedge[x].lowcost<k) k=closedge[x].lowcost; cout<<"("<<vexs[closedge[k].index]<<","<<vexs[k]<<")"; closedge[k].lowcost=0;//第k頂點并入U集合 for(j=0;j<vexnum;j++) if(arcs[k][j]<closedge[j].lowcost) { closedge[j].index=vexs[k]; closedge[j].lowcost=arcs[k][j]; }}//新的頂點并入U后，從新調(diào)整輔助數(shù)組}2）克魯斯卡爾（Kruskal）算法Kruskal算法是逐步給生成樹T中添加不和T中的邊構(gòu)成回路的當(dāng)前最小代價邊。特點:以最小代價邊主。設(shè)N=（V，{E}）是個連通網(wǎng),算法步驟為：1.置生成樹T的初始狀態(tài)為T=（V，{Ф}）2.當(dāng)T中邊數(shù)<n-1時,重復(fù)下列步驟:

從E中選取代價最小的邊（v,u）,并刪除之;

若（v,u）依附的頂點v和u落在T中不同的連同分量上，則將邊（v,u）并入到T的邊集中；否則，舍去該邊，選擇下一條代價最小的邊.步驟(v,u)ET②①④⑤

③⑥

②①④⑤

③⑥

1(1,3)0②①④⑤

52③3466556⑥

②①④⑤

5③3466556⑥

21步驟(v,u)ET5(1,4)4(3,6)②①④⑤

5③66556⑥

②①④⑤

③66556⑥

②①④⑤

③⑥

②①④⑤

③⑥

步驟(v,u)ET6(2,3)②①④⑤

③6656⑥

邊數(shù)=n-1=5代價=(1+2+3+4+5)=15②①④⑤

③⑥

123453.建模過程與方法

----圖的匹配問題實例一：握手的次數(shù)史密斯先生和他太太邀請四對夫妻參加晚會。每個人到的時候，房間里的一些人都要與別的一些人握手。當(dāng)然，每個人都不會與自己的配偶握手，也不會跟同一個人握手兩次。之后，史密斯先生問每個人和別人握了幾次手，他們的答案都不一樣。那么，史密斯太太和別人握了幾次手呢?這個問題具有挑戰(zhàn)性的原因是因為它沒有一個明顯的起始點，但如果對此建立一個圖模型，問題就變得很簡單了。

分析：從題目我們得到了哪些信息?史密斯和太太邀請四對夫妻參加晚會--房間里共有10人。每個人都不會與自己的配偶握手--握手的兩個人不是配偶。每個人都不會跟同一人握手兩次--兩個人間的握手最多是一次。史密斯先生問每個人和別人握了幾次手，他們的答案都不一樣--除史密斯先生外，每個人和別人握手的次數(shù)都不一樣。除史密斯先生外，每人握手的次數(shù)最多是8次，最少為0次。房間里除了史密斯先生外的9個人，他們與別人握手的次數(shù)分別為0，1，2，3，4，5，6，7，8次。要知道史密斯太太和別人握手的次數(shù)，只需確定除史密斯先生外的9人中哪一個是史密斯太太即可。根據(jù)以上信息，建立圖模型

0-8號分別代表握手次數(shù)為0-8次的9個人（史密斯先生除外）。

8號握手8次，則其配偶肯定是0號；以此類推，7號的配偶是1號，6號的配偶是2號，5號的配偶是3號。所以，史密斯夫人是4號，即史密斯夫人握手次數(shù)為4次。由圖可知：8號的配偶是0號；7號的配偶是1號；6號的配偶是2號；5號的配偶是3號；史密斯太太是4號，所以史密斯太太和別人握了4次手。實例二：商人安全過河問題

三名商人各帶一個隨從乘船渡河，現(xiàn)有一只小船只能容納兩個人，由他們自己劃行，隨從們密約，在河的任一岸，一旦隨從的人數(shù)比商人多，就殺人越貨。但如何乘船渡河由商人決定，試給出一個商人安全渡河的方案。問題分析多步?jīng)Q策過程決策：每一步(此岸到彼岸或彼岸到此岸)船上的人員。要求：在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河。商人仆人k為奇數(shù)k為偶數(shù)此岸彼岸建模商人仆人設(shè)k次渡河前此岸的商人數(shù)為xk，隨從數(shù)為yk，則xk，yk=0，1，2，3定義狀態(tài)向量Sk=(xk,yk)定義決策：第k次渡船上的商人數(shù)為uk，隨從數(shù)為vk，則d=(uk,vk)允許決策集合：D={(u,v)|1u+v2,u,v=0,1,2}k為奇數(shù)k為偶數(shù)此岸彼岸狀態(tài)轉(zhuǎn)移規(guī)律：模型構(gòu)成xk~第k次渡河前此岸的商人數(shù)yk~第k次渡河前此岸的隨從數(shù)xk,yk=0,1,2,3;

k=1,2,sk=(xk,yk)~過程的狀態(tài)S={(x

,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}S~允許狀態(tài)集合uk~第k次渡船上的商人數(shù)vk~第k次渡船上的隨從數(shù)dk=(uk,vk)~決策uk,vk=0,1,2;k=1,2,sk+1=sk

dk+(-1)k~狀態(tài)轉(zhuǎn)移律求dkD(k=1,2,n),使skS,并按轉(zhuǎn)移律由s1=(3,3)到達sn+1=(0,0).多步?jīng)Q策問題模型求解xy3322110窮舉法~編程上機圖解法狀態(tài)s=(x,y)~16個格點~10個點允許決策~移動1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,，d11給出安全渡河方案考慮4名商人各帶一隨從的情況d1d11允許狀態(tài)S={(x

,y)x=0,y=0,1,2,3;

x=3,y=0,1,2,3;x=y=1,2}用圖的鄰接矩陣求解：首先介紹圖論中的一個定理G是一個圖，V（G）為G的頂點集，E(G)為G的邊集。設(shè)G中有n個頂點

;為G的鄰接距陣，其中

定理1：設(shè)A（G）為圖G的鄰接距陣，則G中從頂點到頂點

，長度為k

的道路的條數(shù)為

中的i行j列元素.下面分析及求解假設(shè)渡河是從南岸到北岸，（m，n）表示南岸有m個商人，n個隨從，全部的允許狀態(tài)共有10個

以

為頂點集，考慮到奇數(shù)次渡河及偶數(shù)次渡河的不同，我們建立兩個鄰接距陣

其中其中A表示從南岸到北岸渡河的圖的鄰接距陣，

表示從北岸到南岸渡河的圖的鄰接距陣。

由定理1、我們應(yīng)考慮最小的k，

中1行10列的元素不為0，此時

即為最少的渡河次數(shù)，而矩陣

中1行10列的元素為最佳的路徑數(shù)目。經(jīng)過計算K=5時,

的第1行10列元素為2，所以需11次渡河，有兩條最佳路徑.實例三渡河問題某人帶狗、羊、以及蔬菜渡河，一小船除需人劃外，每次只能載一物過河。而人不在場時，狗要吃羊，羊要吃菜，問此人應(yīng)如何過河？模型構(gòu)成：此問題可化為狀態(tài)轉(zhuǎn)移問題，用四維向量（人，狗，羊，菜）來表示狀態(tài)，當(dāng)一物在此岸時相應(yīng)分量取1，而在彼岸時則取0。(1)可取狀態(tài)人在此岸：(1,1,1,1)，(1,1,1,0)，(1,1,0,1)，(1,0,1,1)，(1,0,1,0)人在彼岸：(0,0,0,0)，(0,0,0,1)，(0,0,1,0)，(0,1,0,0)，(0,1,0,1)總共有十個可取狀態(tài)。(2)現(xiàn)在用狀態(tài)運算來完成狀態(tài)轉(zhuǎn)移。由于擺一次游戲即可改變現(xiàn)有狀態(tài)，為此再引入一個四維轉(zhuǎn)移向量，用它來反映擺渡情況用1表示過河，0表示未過河。例如(1,1,0,0)表示人帶狗過河。此狀態(tài)只有四個允許轉(zhuǎn)移向量：d1=(1,0,0,0)，d2=(1,1,0,0)，d3=(1,0,1,0)，d4=(1,0,0,1)?，F(xiàn)在規(guī)定狀態(tài)向量與轉(zhuǎn)移向量（分量）之間的運算為0+0=0，0+1=1，1+0=1，1+1=0(3)模型求解通過上面的定義，問題化為，由初始狀態(tài)出發(fā)(1,1,1,1)，經(jīng)過奇數(shù)次上述運算轉(zhuǎn)移為狀態(tài)(0,0,0,0)的轉(zhuǎn)移過程。可用圖表示為：

練習(xí)題1.今有3個油瓶，分別能裝10kg、7kg和3kg油。已知10kg瓶中裝滿了油，其余兩瓶為空瓶?，F(xiàn)要將油分成兩個5kg，沒有秤，問能找到幾種分油方案，使倒油的次數(shù)盡量的少？2.四名商人各帶一個隨從乘船渡河，一只小船只能容納二人，由他們自己劃行。隨從們密約，在河的任一岸，一旦隨從的人數(shù)比商人多，就殺人越貨。但是如何乘船渡河的大權(quán)掌握在商人們手中。商人們怎樣才能安全渡河呢?3.三個人和三個機器人要從左岸渡河到右岸。船只有一只，每次可以渡人或機器人共兩名，三個人都會劃船，機器人中只有一個會劃船。為防止意外，每岸有人的時候，人的數(shù)目不能比機器人的數(shù)目少，問應(yīng)當(dāng)怎樣渡河？內(nèi)容1：數(shù)學(xué)建模及其競賽2：中國大學(xué)生數(shù)學(xué)建模競賽歷程3：建模過程簡介4：建模案例分析5：數(shù)學(xué)建模論文的撰寫2007高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目:B題：乘公交，看奧運

我國人民翹首企盼的第29屆奧運會明年8月將在北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計