【文章內(nèi)容簡介】 間的距離。記作。若圖的任二頂點均連通，則稱是連通圖。顯然有：(i) 圖是一條軌的充要條件是是連通的，且有兩個一度的頂點，其余頂點的度為2；(ii) 圖是一個圈的充要條件是是各頂點的度均為2的連通圖。167。3 應(yīng)用—最短路問題 兩個指定頂點之間的最短路徑問題如下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖的頂點，兩城鎮(zhèn)間的直通鐵路為圖相應(yīng)兩頂點間的邊，得圖。對的每一邊，賦以一個實數(shù)—直通鐵路的長度，稱為的權(quán)，得到賦權(quán)圖。的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖中指定的兩個頂點間的具最小權(quán)的軌。這條軌叫做間的最短路，它的權(quán)叫做間的距離，亦記作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠(yuǎn)為順序，依次求得到的各頂點的最短路和距離，直至（或直至的所有頂點），算法結(jié)束。為避免重復(fù)并保留每一步的計算信息，采用了標(biāo)號算法。下面是該算法。(i) 令，對，令。(ii) 對每個（），用代替。計算，把達(dá)到這個最小值的一個頂點記為，令。(iii). 若，停止；若，用代替，轉(zhuǎn)(ii)。算法結(jié)束時，從到各頂點的距離由的最后一次的標(biāo)號給出。在進(jìn)入之前的標(biāo)號叫T標(biāo)號，進(jìn)入時的標(biāo)號叫P標(biāo)號。算法就是不斷修改各項點的T標(biāo)號，直至獲得P標(biāo)號。若在算法運行過程中，將每一頂點獲得P標(biāo)號所由來的邊在圖上標(biāo)明，則算法結(jié)束時，至各項點的最短路也在圖上標(biāo)示出來了。例9 某公司在六個城市中有分公司，從到的直接航程票價記在下述矩陣的位置上。（表示無直接航路），請幫助該公司設(shè)計一張城市到其它城市間的票價最便宜的路線圖。用矩陣（為頂點個數(shù)）存放各邊權(quán)的鄰接矩陣，行向量、分別用來存放標(biāo)號信息、標(biāo)號頂點順序、標(biāo)號頂點索引、最短通路的值。其中分量； 存放始點到第點最短通路中第頂點前一頂點的序號； 存放由始點到第點最短通路的值。求第一個城市到其它城市的最短路徑的Matlab程序如下：clear。clc。M=10000。a(1,:)=[0,50,M,40,25,10]。a(2,:)=[zeros(1,2),15,20,M,25]。a(3,:)=[zeros(1,3),10,20,M]。a(4,:)=[zeros(1,4),10,25]。a(5,:)=[zeros(1,5),55]。a(6,:)=zeros(1,6)。a=a+a39。pb(1:length(a))=0。pb(1)=1。index1=1。index2=ones(1,length(a))。d(1:length(a))=M。d(1)=0。temp=1。while sum(pb)length(a) tb=find(pb==0)。 d(tb)=min(d(tb),d(temp)+a(temp,tb))。 tmpb=find(d(tb)==min(d(tb)))。 temp=tb(tmpb(1))。 pb(temp)=1。 index1=[index1,temp]。 index=index1(find(d(index1)==d(temp)a(temp,index1)))。 if length(index)=2 index=index(1)。 end index2(temp)=index。endd, index1, index2 每對頂點之間的最短路徑計算賦權(quán)圖中各對頂點之間最短路徑，顯然可以調(diào)用Dijkstra算法。具體方法是：每次以不同的頂點作為起點，用Dijkstra算法求出從該起點到其余頂點的最短路徑，反復(fù)執(zhí)行次這樣的操作，就可得到從每一個頂點到其它頂點的最短路徑。這種算法的時間復(fù)雜度為。第二種解決這一問題的方法是由Floyd R W提出的算法，稱之為Floyd算法。假設(shè)圖權(quán)的鄰接矩陣為，來存放各邊長度，其中： ； 之間沒有邊，在程序中以各邊都不可能達(dá)到的充分大的數(shù)代替； 是之間邊的長度。對于無向圖，是對稱矩陣。Floyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列，其中表示從頂點到頂點的路徑上所經(jīng)過的頂點序號不大于的最短路徑長度。計算時用迭代公式：是迭代次數(shù)。最后，當(dāng)時，即是各頂點之間的最短通路值。例10 用Floyd算法求解例1。矩陣path用來存放每對頂點之間最短路徑上所經(jīng)過的頂點的序號。Floyd算法的Matlab程序如下：clear。clc。M=10000。a(1,:)=[0,50,M,40,25,10]。a(2,:)=[zeros(1,2),15,20,M,25]。a(3,:)=[zeros(1,3),10,20,M]。a(4,:)=[zeros(1,4),10,25]。a(5,:)=[zeros(1,5),55]。a(6,:)=zeros(1,6)。b=a+a39。path=zeros(length(b))。for k=1:6 for i=1:6 for j=1:6 if b(i,j)b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j)。 path(i,j)=k。 end end endendb, path167。4 樹 基本概念連通的無圈圖叫做樹，記之為。若圖滿足，則稱是的生成樹。圖連通的充分必要條件為有生成樹。一個連通圖的生成樹的個數(shù)很多，用表示的生成樹的個數(shù)，則有公式公式 (Caylay)。公式 。其中表示從上刪除邊，表示把的長度收縮為零得到的圖。樹有下面常用的五個充要條件。定理1 （i）是樹當(dāng)且僅當(dāng)中任二頂點之間有且僅有一條軌道。（ii）是樹當(dāng)且僅當(dāng)無圈，且。（iii）是樹當(dāng)且僅當(dāng)連通，且。（iv）是樹當(dāng)且僅當(dāng)連通，且，不連通。（v）是樹當(dāng)且僅當(dāng)無圈，恰有一個圈。 應(yīng)用—連線問題欲修筑連接個城市的鐵路，已知城與城之間的鐵路造價為，設(shè)計一個線路圖，使總造價最低。連線問題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具有最小權(quán)的生成樹叫做最小生成樹。下面介紹構(gòu)造最小生成樹的兩種常用算法。 prim算法構(gòu)造最小生成樹設(shè)置兩個集合和,其中用于存放的最小生成樹中的頂點，集合存放的最小生成樹中的邊。令集合的初值為（假設(shè)構(gòu)造最小生成樹時，從頂點出發(fā)），集合的初值為。prim算法的思想是，從所有，的邊中，選取具有最小權(quán)值的邊，將頂點加入集合中，將邊加入集合中，如此不斷重復(fù)，直到時，最小生成樹構(gòu)造完畢，這時集合中包含了最小生成樹的所有邊。prim算法如下：（i），；（ii）while end例11 用prim算法求右圖的最小生成樹。我們用的第一、二、三行分別表示生成樹邊的起點、終點、權(quán)集合。Matlab程序如下：clc。clear。M=1000。a(1,2)=50。 a(1,3)=60。a(2,4)=65。 a(2,5)=40。a(3,4)=52。a(3,7)=45。a(4,5)=50。 a(4,6)=30。a(4,7)=42。a(5,6)=70。 a=[a。zeros(2,7)]。a=a+a39。a(find(a==0))=M。result=[]。p=1。tb=2:length(a)。while length(result)~=length(a)1 temp=a(p,tb)。temp=temp(:)。 d=min(temp)。 [jb,kb]=find(a(p,tb)==d)。 j=p(jb(1))。k=tb(kb(1))。 result=[result,[j。k。d]]。p=[p,k]。tb(find(tb==k))=[]。endresult Kruskal算法構(gòu)造最小生成樹科茹斯克爾（Kruskal）算法是一個好算法。Kruskal算法如下:(i)選，使得。(ii)若已選好，則從中選取，使得① 中無圈，且② 。(iii)直到選得為止。例12 用Kruskal算法構(gòu)造例3的最小生成樹。我們用存放各邊端點的信息，當(dāng)選中某一邊之后，就將此邊對應(yīng)的頂點序號中較大序號改記為此邊的另一序號，同時把后面邊中所有序號為的改記為。此方法的幾何意義是：將序號的這個頂點收縮到頂點，頂點不復(fù)存在。后面繼續(xù)尋查時，發(fā)現(xiàn)某邊的兩個頂點序號相同時，認(rèn)為已被收縮掉，失去了被選取