1、2 3.4 回路矩陣與割集矩陣回路矩陣與割集矩陣有向連通圖有向連通圖G=(V,E) 的回路矩陣和割集矩的回路矩陣和割集矩陣，與陣，與G 的支撐樹有密切聯系。的支撐樹有密切聯系。 回路矩陣及其性質回路矩陣及其性質 (1) 概念概念 設設T是有向連通圖是有向連通圖G的一棵支撐樹的一棵支撐樹, 對于不對于不在在T上的邊上的邊e，T+e 必含一個唯一回路必含一個唯一回路C. 如果給回路如果給回路C定一個參考方向定一個參考方向, 那么那么C中方中方向與回路方向一致的邊向與回路方向一致的邊, 就稱為就稱為正向邊正向邊,否則稱否則稱為為反向邊反向邊.3將將G的全部初級回路對應的向量構成的全部初級回路對應的向

2、量構成一個矩陣，這就是一個矩陣，這就是G的的完全回路矩陣完全回路矩陣Ce。 0 1 1kiikkiikkiikeCCeeCCeeCc不不含含邊邊相相反反的的方方向向與與但但含含邊邊一一致致的的方方向向與與且且含含邊邊, 設設G的全部邊為的全部邊為e1, e2, , em ，則初，則初級回路級回路Ci 對應向量對應向量(ci1, ci2, , cim ), 其其中中4 110011101101011110100110111000010101001011eeeeee 7654321654321CCCCCCCCe例例(p.46) 求右求右圖的完全回路圖的完全回路矩陣矩陣.5 一個圖的初級回路很多，其

3、中哪些是一個圖的初級回路很多，其中哪些是最基本的呢？或者說最基本的呢？或者說, Ce中哪些行構成全中哪些行構成全部行的極大無關組呢？部行的極大無關組呢？定義定義設設T是圖是圖G的一棵支撐樹，則的一棵支撐樹，則T以外以外的每條邊對應的回路的每條邊對應的回路(一條邊恰好對一條邊恰好對應一個回路，應一個回路，回路的方向規定為此邊的回路的方向規定為此邊的方向方向)均稱為均稱為基本回路基本回路，全部，全部m-n+1個基個基本回路構成的矩陣本回路構成的矩陣Cf ，稱為，稱為G的的基本回基本回路矩陣路矩陣。支撐樹的支撐樹的余邊余邊: 以外的任何一邊以外的任何一邊6例例(p.46) 對圖對圖G的支的支撐樹撐樹

4、T=e1,e5,e6，求其基，求其基本回路矩陣。本回路矩陣。 T的余邊的余邊e2,e3,e4, 分別分別對應回路對應回路C1,C2,C3 , 故故. 111000010101110011321654321CCCCeeeeeefT外各邊對應列外各邊對應列7重新排列行和列的順序重新排列行和列的順序(相當于對各相當于對各回路和各邊重新編號回路和各邊重新編號)，可以得到一個，可以得到一個含含m-n+1階單位矩陣階單位矩陣(對應于對應于T以外的以外的各邊各邊)新基本回路矩陣，而新矩陣的秩新基本回路矩陣，而新矩陣的秩不變。不變。. 110100011010111001321651432CCCCeeeeee

5、fT外各邊對應列外各邊對應列T各邊對應列各邊對應列8(2) 基本回路矩陣和完全回路矩陣的秩基本回路矩陣和完全回路矩陣的秩定理定理1有向連通圖的基本回路矩陣有向連通圖的基本回路矩陣秩是秩是m-n+1.證證：設：設Cf 是對應于支撐樹是對應于支撐樹T 的基本回的基本回路矩陣，則路矩陣，則T的一條余邊僅在其對應基的一條余邊僅在其對應基本回路中出現，而不會在別的基本回路本回路中出現，而不會在別的基本回路中出現。換言之，全部余邊在矩陣中出現。換言之，全部余邊在矩陣Cf中中對應的列構成的子陣中，每行每列恰含對應的列構成的子陣中，每行每列恰含一個一個1，其余元素均為，其余元素均為0。因為因為Cf 共共m-n

6、+1行，而以上證明其行行，而以上證明其行向量組線性無關，故它的秩是向量組線性無關，故它的秩是m-n+1 。9定理定理2 有向連通圖有向連通圖G 的關聯矩陣的關聯矩陣B 與完全與完全回路矩陣回路矩陣Ce 的邊次序一致時，恒有的邊次序一致時，恒有 BCeT=0。 證明證明: 設設B的第的第i 行為行為(bi1, bi2, , bim) ，Ce的的第第j 行為行為(cj1, cj2, , cjm) ，則，則 BCeT中第中第i 行第行第j 個個元素為元素為dij=bi1cj1+ bi2cj2+ +bimcjm. 因為因為B的第的第i 行對應結點行對應結點vi， Ce的第的第j 行對應行對應回路回路C

7、j 。當。當Cj 不經過不經過vi時時,對于滿足對于滿足bik0的的k,必必有有cjk=0，因此，因此dij =0; 當當Cj 經過經過vi時時,恰有恰有Cj的兩的兩條邊條邊ek,el 經過經過vi(不妨設一進一出不妨設一進一出)，則，則dij= bikcjk+ bilcjl =111(-1)0 .10定理定理3 有向連通圖有向連通圖G的完全回路矩陣的完全回路矩陣Ce的秩是的秩是m-n+1. 證明證明：由于基本回路矩陣：由于基本回路矩陣Cf 是完全回路矩陣是完全回路矩陣的的Ce 的子陣的子陣, 而而Cf 的秩是的秩是m-n+1, 故故 秩秩( Ce)=m-n+1. 由由Sylvester定理定

8、理, 若有若有An mDm s= 0, 則則秩秩(A) +秩秩(D) =m.由定理由定理1和定理和定理2，BCeT=0，秩，秩(B) n-1，故由，故由秩秩(B) +秩秩(Ce) =m,(m為邊數為邊數)知秩知秩(Ce) =m-n+1，從而秩，從而秩(Ce) =m-n+1。11(3) 回路矩陣回路矩陣定義定義由連通圖由連通圖G的有的有m-n+1個互相獨個互相獨立的回路組成的矩陣，稱為立的回路組成的矩陣，稱為G的的回路矩陣回路矩陣，記為記為C。 性質性質:(1) 基本回路矩陣基本回路矩陣Cf 是回路矩陣。是回路矩陣。 (2) BCT=0 (B與與C中邊的順序排列一致中邊的順序排列一致) (3)

9、C=PCf，P是某個滿秩方陣。是某個滿秩方陣。(C與與Cf 中邊的順序排列一致中邊的順序排列一致)12 G的余樹與回路矩陣間的關系的余樹與回路矩陣間的關系定理定理4 連通圖連通圖G 的回路矩陣的回路矩陣C 的任一的任一m-n+1階子陣行列式非零，當且僅當階子陣行列式非零，當且僅當這些列對應于這些列對應于G 的某一棵的某一棵余樹余樹(刪去這些列的對應邊后，所得圖刪去這些列的對應邊后，所得圖是一棵樹是一棵樹)。證明：證明：充分性充分性. 已知已知G的某支撐樹的某支撐樹T, 使得此子使得此子陣中那些列對應的全部邊就是陣中那些列對應的全部邊就是T 以外的全部邊。以外的全部邊。 于是，于是，T 的基本回

10、路矩陣中這些邊對應的各的基本回路矩陣中這些邊對應的各列，適當重排順序后為列，適當重排順序后為m-n+1 階單位矩陣，故階單位矩陣，故該子陣的行列式非零。該子陣的行列式非零。 13必要性必要性. 將這將這m-n+1列換到最前面列換到最前面(通過重新通過重新對邊編號對邊編號)，則，則C=(C11,C12)。現在只需證明現在只需證明C12 對應對應G的一棵支撐樹。的一棵支撐樹。如果如果C12 對應邊不是樹，則其中必含有回路，對應邊不是樹，則其中必含有回路，從而必含有一個初級回路。即有一個初級回路從而必含有一個初級回路。即有一個初級回路C，全由，全由C12中的某些列的對應邊構成。中的某些列的對應邊構成

11、。于是在回路矩陣于是在回路矩陣C 前前m-n+1列列(即即C11)中，初中，初級回路級回路C對應的那行全為對應的那行全為0，所以，所以det(C11) = 0,這與題設矛盾。這與題設矛盾。14 已知基本關聯矩陣已知基本關聯矩陣Bk ，求基本回路矩陣，求基本回路矩陣Cf定理定理5 若已知有向連通圖的基本關聯矩陣若已知有向連通圖的基本關聯矩陣Bk =(B11,B12)，其中，其中B12是非奇異方陣，則可得是非奇異方陣，則可得基本回路矩陣基本回路矩陣Cf = ( I C12) ，其中，其中C12=-B11TB12-1T.這里這里 Cf 與與Bk的邊次序一致。的邊次序一致。 證明證明:由定理由定理4

12、知知B11對應對應G的一個余樹的一個余樹, 即即B12各列對應一棵支撐樹各列對應一棵支撐樹T。因此。因此T對應的基本回對應的基本回路矩陣路矩陣Cf前前m-n+1列構成的子方陣中，每行每列構成的子方陣中，每行每列恰含一個列恰含一個1，其余元素為，其余元素為0。重排各行順序重排各行順序(即給各基本回路重新編號即給各基本回路重新編號)，15可使前可使前m-n+1階子方陣成為單位矩陣階子方陣成為單位矩陣I。因此，可設因此，可設Cf = ( I C12) 。由定理由定理2 知知BkCfT=0，即，即。，故故即即T 112T111211112T12T121211T121211BBCBBC, 0CBB, 0

13、CIBB16例例 已知圖已知圖3.11的基本關聯矩陣，其中的基本關聯矩陣，其中e1,e5,e6所所對應的子陣行列式非零，求對應的子陣行列式非零，求Cf.),(011100100101001011011001101010000111121165132246543214BBeeeeeeBeeeeeeB17，因因為為10010101111B，01110000112B，故故計計算算得得010101001121B11001111111001111101010001111000101112 fC,),(12111212TTfffBBCCIC 其其中中則則182 . 割集矩陣及其性質割集矩陣及其性質 (1)

14、定義定義設設S是有向圖是有向圖G =(V,E)的邊子集，若的邊子集，若 1、G=(V,E-S)比比G的連通支數多的連通支數多1 (去掉這去掉這S包含的邊集后，圖包含的邊集后，圖G 恰好多恰好多1個分枝個分枝). 2、對任意、對任意S S, G與與G=(G,E-S)的連通支的連通支數一樣數一樣(少去一條邊，仍是連通的少去一條邊，仍是連通的)則稱則稱S為為割集割集。 連通連通連通連通某連通支某連通支有向割集的有向割集的方向方向(任意規定的一個方向任意規定的一個方向)19 例例：S1=e2,e3,e4 和和 S2=e4,e5是割集是割集,而而S3=e6,e7不是割集不是割集。V1V3V2V4V5V6

15、e1e2e3e4e5e6e7S1S2S320 (2) 完全割集矩陣完全割集矩陣 有向圖有向圖G的的全部割集全部割集組成的矩陣，稱為組成的矩陣，稱為完全割集矩陣完全割集矩陣，記作，記作Se，其元素的定義：，其元素的定義： Sij= 1, ej在在Si中且方向一致中且方向一致; Sij= -1, ej在在Si中且方向相反中且方向相反; Sij= 0，其它，其它. pemSSSSe.ee.212121 6543217654321eeeeee101110011101110011110100011010101001000111SSSSSSSSes1s2s3s4s5s6s722 (3) 基本割集基本割集

16、設設T是連通圖是連通圖G的一棵支撐樹，的一棵支撐樹，ei 是是T 的一個邊。對應的一個邊。對應ei存在存在G的割集的割集Si, Si 只包只包括一條樹枝邊括一條樹枝邊ei及某些余樹枝，且與及某些余樹枝，且與ei 的的方向一致。這時稱方向一致。這時稱Si 為為G的對應樹的對應樹T的一個的一個基本割集基本割集。ei割集割集Si的方向規定為的方向規定為ei的方向。的方向。23 定義定義 給定有向連通圖的一棵樹給定有向連通圖的一棵樹T，則由全部基本割集組成的矩陣為則由全部基本割集組成的矩陣為基本基本割集矩陣割集矩陣，記作，記作Sf . 對于不同的支撐樹對于不同的支撐樹T，其對應的基本，其對應的基本割集

17、矩陣割集矩陣Sf 會不同。會不同。 12121 .nfmSSSSe.ee24s2s4s5654321Seeeeee1011100111011100111101000110101010010001117654321SSSSSSSe對于樹對于樹T e2,e3,e4 , 101001110100110011 eeeeee 654321245SSSSf25將將Sf 中邊的排列次序作調整：把中邊的排列次序作調整：把T 的邊放的邊放在最前面，非在最前面，非T 的邊放在后面；的邊放在后面；T 的邊適當的邊適當排列，可使對應矩陣塊為一單位矩陣排列，可使對應矩陣塊為一單位矩陣I。, 10100111010011

18、0011 eeeeee 654321245SSSSf注意注意 101100110010111-001 eeeeee 651432245SSSSfT 的邊的邊非非T 的邊的邊26(4) 割集矩陣及性質割集矩陣及性質定理定理1 當有向連通圖當有向連通圖G的完全回路矩陣的完全回路矩陣Ce和和完全割集矩陣完全割集矩陣Se的邊次序一致時，有的邊次序一致時，有SeCeT=0. 證明證明: 設設Se的第的第i 行為行為(si1, si2, , sim) ，Ce的第的第j 行為行為(cj1, cj2, , cjm) ，則，則 SeCeT中第中第i 行第行第j 個元個元素為素為 dij=si1cj1+ si2c

19、j2+ +simcjm. 因為因為Se的第的第i 行對應割集行對應割集Si， Ce的第的第j 行對應行對應回路回路Cj 。SiCj 當當Cj 與與Si不相交時，對于不相交時，對于Sj 經過經過的邊的邊ek (Cj不經過不經過)，有，有sikcjk=100 ; 對于對于Cj 經過的邊經過的邊ek (Sj 不經不經過過)，有，有sikcjk=010 ; 因此因此dij =0.27 當當Cj 與與Sj 相交時相交時, 它們有偶數條共同的邊：它們有偶數條共同的邊：其中一半的邊與割集方向相同，另一半邊則與其中一半的邊與割集方向相同，另一半邊則與割集方向相反。割集方向相反。對于對于Sj 經過但經過但Cj不

20、經過的邊不經過的邊ek ，有，有sikcjk=100。 對于對于Sj和和Cj 均經過的一對邊均經過的一對邊ek , ek (一邊與一邊與割集方向相同，一邊與割集方向相反割集方向相同，一邊與割集方向相反)，有，有 sikcjk+ sikcjk= 111(-1)0, 因此因此dij =0.28 定理定理2 連通圖連通圖G的完全割集矩陣的完全割集矩陣Se的秩是的秩是n-1. 定理定理3 連通圖連通圖G 的割集矩陣的割集矩陣S的任意一個的任意一個n-1階子陣行列式非零階子陣行列式非零當且僅當當且僅當這些列對應于這些列對應于G的的某棵樹某棵樹 (與回路矩陣類似與回路矩陣類似) 定理定理4 設設Sf和和C

21、f分別連通圖分別連通圖G中關于某棵樹中關于某棵樹T的基本割集和基本回路矩陣的基本割集和基本回路矩陣,且邊次序一致且邊次序一致.若若Sf=(Sf11,I),Cf=(I,Cf12),則則Sf11=-Cf12T 。( 由由SeCeT=0 可得可得)293.5 支撐樹的生成支撐樹的生成 (1) 兩樹的距離兩樹的距離: 設設t1,t2是連通圖是連通圖G的兩棵生的兩棵生成樹。若成樹。若t1中共有中共有k 條邊不屬于條邊不屬于t2, 則說則說t1與與t2的的距離距離d(t1,t2)=k。若若d(t1,t2)=k，則，則d(t2,t1)=k.基本樹變換基本樹變換: 設設t1是連通圖是連通圖G的一棵生成樹，的一

22、棵生成樹，邊邊e t1, 邊邊e t1, 若對若對t1 加邊加邊e、去邊、去邊e后得后得G的的新生成樹新生成樹 t2= t1 (e, e), 這稱為是這稱為是t1到到t2的的基本基本樹變換樹變換。 在在基本樹變換基本樹變換中，中，t1到到t2的距離為的距離為1.30 基本割集基本割集Se(t0) :對于連通圖對于連通圖G的一的一棵生成樹棵生成樹t0,t0的一條邊的一條邊e 對應一個基本對應一個基本割集割集Se(t0)，于是樹，于是樹t0 共對應共對應n-1個基本割個基本割集集. 例例 設設 t0 e1, e2, e3 .Se1(t0)= e1,e4,e6 ,Se2(t0)= e2,e5,e6

23、,Se3(t0)= e3,e4,e5 ,v1v4v3v2e1e6e4e3e5e231(2) 定理定理1 設設t1是連通圖是連通圖G的生成樹。的生成樹。 若若對于對于b Se(t1)(b e)，則則t1-e+b可得一棵距可得一棵距離為離為1的新樹。反之，若的新樹。反之，若t1-e+b是一棵樹，是一棵樹， e t1 且且b e ，則則b Se(t1)。eb32定理定理2 對于對于G的一棵生成樹的一棵生成樹t0, e t0, 若若Se(t0) = e, b1, b2, , bp ,則則t0-e+b1, t0-e+b2, t0-e+bp是不含是不含e且與且與t0 距離距離為為1的的G的全部生成樹。的全

24、部生成樹。 v1v4v3v2e1e6e4e3e5e2例例 設設 t0= e1, e2, e3 , 則則 Se1(t0)= e1,e4,e6 ,Se2(t0)= e2,e5,e6 ,Se3(t0)= e3,e4,e5 。故故G中與距離為中與距離為1的全部樹為：的全部樹為： t1= e4, e2, e3 , t2= e6, e2, e3 , t3= e1, e5, e3 , t4= e1, e6, e3 , t5= e1, e2, e4 , t6= e1, e2, e5 , 33(3) 對于對于G 的生成樹的生成樹t0 , e t0, 記記(不含不含e且與且與t0 距離為距離為1 的的G 的全部生

25、成樹的全部生成樹)上例中，上例中，Te=t1, t2, Te=t3, t4, Te=t5, t6. 定理定理3 設設t0=(e1,e2,.,ek) 是是G中的一棵生成中的一棵生成樹樹, 則則G中與中與t0 距離為距離為1的樹恰在的樹恰在Te, Te, , Te 的某個集合之中。的某個集合之中。eib34對于對于G 的生成樹的生成樹t0 及及t0 的邊的邊e和和f，記，記(不含不含e, f 且與且與t0 距離為距離為2的的G 的全部生成樹的全部生成樹)即對樹即對樹t0 中的一條邊中的一條邊e，用，用Se(t0)中的每條邊替換中的每條邊替換e后得到后得到Te, 然后對然后對Te中的每棵樹中的每棵樹

26、t, 再用再用中的每條邊替換中的每條邊替換f 后得到樹集后得到樹集Tt, 這樣所有的這樣所有的Tt的并就是的并就是Tef ，即，即Tef t Tt.ebf35定義定義 T,1 i n-11 ij n-11 ijw1)比離根更遠，則互換樹比離根更遠，則互換樹葉葉i,1的權值后，新樹的帶權路徑總長比的權值后，新樹的帶權路徑總長比T小，這小，這與與T是最優二叉樹矛盾。是最優二叉樹矛盾。 若若w1無兄弟，則刪除相應于的樹葉樹枝，將無兄弟，則刪除相應于的樹葉樹枝，將權賦給的父親，所得新樹的帶權路徑總長比權賦給的父親，所得新樹的帶權路徑總長比T小，小，這與這與T是最優二叉樹矛盾。是最優二叉樹矛盾。所以所以

27、w1有兄弟，且必須是有兄弟，且必須是w2 。 2) WPL(T)=l1w1+l2w2+lnwn =l1(w1+w2)+l3 w3+lnwn= WPL(T).42上述定理告訴我們：要畫一棵帶有上述定理告訴我們：要畫一棵帶有n個權的個權的最優二叉樹，可簡化為一棵帶有最優二叉樹，可簡化為一棵帶有n-1個權的最優個權的最優二叉樹，而這又可簡化為畫一棵帶有二叉樹，而這又可簡化為畫一棵帶有n-2個權的個權的最優二叉樹，最優二叉樹，.。 構造最優二叉樹的構造最優二叉樹的Huffman算法算法 1) 將權值排序：將權值排序： w1 w2 wn, 要求以上權值的最優二叉樹要求以上權值的最優二叉樹T。 2) 作一

28、個由公共分枝點的兩樹枝，兩樹葉作一個由公共分枝點的兩樹枝，兩樹葉分別帶最小權分別帶最小權w1,w2 ; 3) 再考慮權值為再考慮權值為w1+w2 , w3 , , wn的最優二的最優二叉樹；叉樹；反復執行反復執行1)2)3), 直到權值只剩一個為止。直到權值只剩一個為止。 43 例例“一地在要工上是中國同和的有一地在要工上是中國同和的有”在某在某文的頻率如下：文的頻率如下：2,3,5,7,11,13,17,19,23,29,31,37,41，用用Huffman方法構造相應的最優二叉樹方法構造相應的最優二叉樹,分別分別對以上漢字編碼，寫出對以上漢字編碼，寫出“中國一地要工有中國一地要工有”的的編

29、碼，譯出編碼，譯出“10001011101001011”的對應的漢的對應的漢字。字。 解解：首先組合：首先組合2+3，尋找，尋找5,5,7,.,41的最優二的最優二叉樹，然后組合叉樹，然后組合5+5,尋找尋找10,7,11,.,41最優二叉最優二叉樹。依此繼續。這個過程綜合為：樹。依此繼續。這個過程綜合為：例例 (p57)44453.7 最短樹最短樹 1. 對于賦權連通圖，有時要尋找生成樹對于賦權連通圖，有時要尋找生成樹各邊權之和最小或最大的某一棵。各邊權之和最小或最大的某一棵。 權可為長度、運輸量、費用等。權可為長度、運輸量、費用等。 最小生成樹最小生成樹： 在賦權連通圖的所有生成在賦權連通

30、圖的所有生成樹中權之和最小的生成樹，稱為樹中權之和最小的生成樹，稱為G的最小的最小生成樹。生成樹。 46 2. Kruskal算法算法 設賦權連通圖設賦權連通圖G 有有n個結點個結點. (1) 將全部邊按權值由小到大排序：將全部邊按權值由小到大排序： e1 e2 en; (2) 初始化：令初始化：令T:=, i:=1; (3) 迭代：迭代：若若|T|=n-1, 則結束；則結束；若若T+ei 不含回路，則不含回路，則T:=T+ei ; i:=i+1, 返回返回(3). Kruskal算法的思路算法的思路是，開始是，開始T 為空，而后將為空，而后將邊邊e1,e2, , en 依次試放入依次試放入T

31、，如果含回路則拿出，如果含回路則拿出，否則正式放入否則正式放入T, 直到直到T 有有n-1條邊為止。條邊為止。 47例例1 給定一個賦權的連通圖，用給定一個賦權的連通圖，用Kruskal算法求最小生成樹。算法求最小生成樹。 該生成樹的邊數該生成樹的邊數= 6-1=5， 樹權樹權=生成樹的邊權和生成樹的邊權和=18 .48例例2 求下列賦權連通圖的一棵最小生成樹。求下列賦權連通圖的一棵最小生成樹。11212122 權有相同的時，最小權有相同的時，最小生成樹可能不唯一。生成樹可能不唯一。或：或：49(3) Prim算法算法 首先任選一結點首先任選一結點v0 , 構成集合構成集合U。然后選。然后選V

32、-U到到U的一條最短邊的一條最短邊(v, u) 進入進入T，U=U+u ; 反復反復進行此過程，直到進行此過程，直到U=V. T= , U=v0 ,while UV do begin w(t,u)=min w(i,j): j U, j V-U , T=T+e(t,u), U=U+u, end50例例用用Prim算法求下列圖的一個最小生成樹。算法求下列圖的一個最小生成樹。15101020153040251510103020v1v2v5v3v4v1v2v5v3v4迭代：迭代：(0) U=v1, V-U= v2, v3, v4, v5 (1) U=v1 , v2, V-U=v3, v4, v5 (2

33、) U=v1 , v2 , v4, V-U=v3, v5 (3) U=v1 , v2 , v4 , v3 , V-U=v5 (4) U=v1 , v2 , v4 , v3 , v5 , V-U= 51Prim算法的正確性算法的正確性定理定理設設V是賦權連通圖是賦權連通圖G的結點真子集，的結點真子集，e是是V到到VV的最短邊，則的最短邊，則G中一定存在包含中一定存在包含e的最小生成樹的最小生成樹T。證：設證：設T是是G的一棵最小生成樹，若的一棵最小生成樹，若e T，則則T+e 必含一個回路必含一個回路C , e C且且C中有邊中有邊e= (u,v), u V, v V-V 。 由于由于w(e)=w(e), 則則TT+e-e仍為最小生仍為最小生成樹。成樹。 Prim算法可得到算法可得到G的一棵最小生成樹。的一棵最小生成樹。 最長樹的求法最長樹的求法:在在Kruskal算法中算法中, 由每次由每次加入最短邊加入最短邊, 改成每次加入最長邊改成每次加入最長邊, 即可實現即可實現.52 3.8 最大分枝最大分枝上節討論無向圖的最短樹和最長樹上節討論無向圖的最短樹和最長樹, 最大權最大權根樹等問題根樹等問題. 由于有的圖并不存在根樹由于有的圖并不存在根樹, 所以也