【文章內(nèi)容簡介】 )(mO 當網(wǎng)絡不是簡單圖，而是具有平行弧（即多重?。r，顯然此時鄰接矩陣表示法是不 能采用的。其他方法則可以很方便地推廣到可以處理平行弧的情形。 上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖中邊沒有方向， 因此可能需要做一些自然的修改。例如，可以在計算機中只存儲鄰接矩陣的一半信息 （如上三角部分），因為此時鄰接矩陣是對稱矩陣。無向圖的關聯(lián)矩陣只含有元素 0和 +1，而不含有 1，因為此時不區(qū)分邊的起點和終點。又如，在鄰接表和星形表示法中，每條 邊會被存儲兩次，而且反向星形表示顯然是沒有必要的，等等。 軌與連通 kk veevevW ?2110? ，其中 ， 。其中 與 關聯(lián)。 W稱為圖 G的一條道路， k為路長。頂點 稱為 W的起點 和終點。 )(GEei ? ki ??1 )(GVvj ? kj ??0ieii vv ,1? 0v kv若道路 W的邊互不相同，則 W稱為跡 (trail)。若道路 W的頂點互不相同，則 W稱為軌 (path)。 稱一條道路是閉的，如果它有正的長且起點和終點相同。起點和終點重合的軌叫做圈 . 若圖 G的兩個頂點 u,v間存在道路，則稱 u和 v連通 (connected)。 U,v間的最短軌的長叫做 U,v間的距離。記作 d(u,v)。若圖 G的任二頂點均連通，則稱 G是連通圖。 應用 ?兩個指定頂點之間的最短距離 00,vu問題如下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡，在這個網(wǎng)絡的兩個指定城鎮(zhèn)間， 找一條最短鐵路線 以各城鎮(zhèn)為圖 G的頂點，兩城鎮(zhèn)間的直通鐵路為圖 G相應兩頂點間的邊，得圖 G。 對 G的每一邊 e，賦以一個實數(shù) w(e)— 直通鐵路的長度，稱為 e的權(quán)，得到賦權(quán)圖 G。 G的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖中指定的兩個頂點 間的具最小權(quán)的軌。這條軌叫做 間的最短路，它的權(quán)叫做 間的距離， 亦記作 。 00,vu00,vu),( 00 vud求最短路已有成熟的算法：迪克斯特拉（ Dijkstra）算法，其基本思想是按距 從近 到遠為順序，依次求得 到的各頂點的最短路和距離，直至 （或直至 G的所有頂 點），算法結(jié)束。為避免重復并保留每一步的計算信息，采用了標號算法 .下面是該算法。 0u0u 0v (i 令 ，對 ，令 ， ， 。 0)( 0 ?ul 0uv? ??)(vl }{00 uS ? 0?i(ii) 對每個 （ ），用 代替 。計算 ，把達到這個最小值的一個頂點記為 ，令 。 iSv? ii SVS \?)}()(),({m i n uvwulvliSu ??)(vl )}({min vliSv?1?iu}{ 11 ?? ? iii uSS ?(iii). 若 ，停止；若 ，用 代替 ，轉(zhuǎn) (ii)。 1|| ?? Vi 1|| ?? Vi 1?i i算法結(jié)束時，從 到各頂點的距離由 的最后一次的標號給出。在 進入 之前的標號叫 T標號， 進入 時的標號叫 P標號。算法就是不斷修改 各項點的 T標號，直至獲得 P標號。若在算法運行過程中，將每一頂點獲得 P標號 所由來的邊在圖上標明，則算法結(jié)束時， 至各項點的最短路也在圖上標示出來了。 0u )(vl viS v iS0u例 9 某公司在六個城市中有分公司 ，從 到 的直接航程票價記在 下述矩陣的 位置上。（ 表示無直接航路），請幫助該公司設計一張 城市 到其它城市間的票價最便宜的路線圖。 621 , ccc ? ic jc),( ji ?1c????????????????????????055252510550102025251001020402022022252022050102540500用矩陣 （ n為頂點個數(shù)）存放各邊權(quán)的鄰接矩陣，行向量 、 、 、 分別用來存放 標號信息、標號頂點順序、標號頂點索引、最短通路的值。其中分量 ； 存放始點到第 點最短通路中第 頂點前一頂點的序號； 存放由始點到第 點最短通路的值。 nna? pb 1index 2indexP????頂點未標號當?shù)陧旤c已標號當?shù)趇iipb01)()(2 iindex i i)(id i求第一個城市到其它城市的最短路徑的 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。 end d, index1, index2 連通的無圈圖叫做樹，記之為 。若圖 滿足 ， ，則稱 是 的生成樹。圖 連通的充分 必要條件為 有生成樹。一個連通圖的生成樹的個數(shù)很多，用 表示 的生成樹的個數(shù)，則有公式 T G )()( TVGV ? )()( GETE ?T G GG )(G?G)()()( eGeGG ???? ???其中 表示從 上刪除邊 ， 表示把 的長度收縮為零得到的圖。 eG? G e eG? e應用 — 連線問題 : 欲修筑連接 個城市的鐵路，已知城 與城 之間的鐵路造價為 ，設計一個線路圖，使總造價最低。 ni j ijC下面介紹構(gòu)造最小生成樹的兩種常用算法。 prim算法構(gòu)造最小生成樹 設置兩個集合 和 ,其中 用于存放的最小生成樹中的頂點，集合 存放的最小生 成樹中的邊。令集合 的初值為 （假設構(gòu)造最小生成樹時，從頂點 出發(fā)） ，集合 的初值為 。 prim算法的思想是，從所有 ， 的邊中，選取具有最小權(quán)值的邊 ， 將頂點 加入集合 中，將邊 加入集合 中，如此不斷重復，直到 時，最小生成樹構(gòu)造完畢，這時集合 中包含了最小生成樹的所有邊。 P Q P