回路矩阵与割集矩阵

1、整理课件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) 求右求右图的完全回路图的完全回

3、路矩阵矩阵.整理课件5 一个图的初级回路很多，其中哪些是一个图的初级回路很多，其中哪些是最基本的呢？或者说最基本的呢？或者说, Ce中哪些行构成全中哪些行构成全部行的极大无关组呢？部行的极大无关组呢？定义定义设设T是图是图G的一棵支撑树，则的一棵支撑树，则T以外以外的每条边对应的回路的每条边对应的回路(一条边恰好对一条边恰好对应一个回路，应一个回路，回路的方向规定为此边的回路的方向规定为此边的方向方向)均称为均称为基本回路基本回路，全部，全部m-n+1个基个基本回路构成的矩阵本回路构成的矩阵Cf ，称为，称为G的的基本回基本回路矩阵路矩阵。支撑树的支撑树的余边余边: 以外的任何一边以外的任何一

4、边整理课件6例例(p.46) 对图对图G的支的支撑树撑树T=e1,e5,e6，求其基，求其基本回路矩阵。本回路矩阵。 T的余边的余边e2,e3,e4, 分别对分别对应回路应回路C1,C2,C3 , 故故. 111000010101110011321654321CCCCeeeeeefT外各边对应列外各边对应列整理课件7重新排列行和列的顺序重新排列行和列的顺序(相当于对各相当于对各回路和各边重新编号回路和各边重新编号)，可以得到一个，可以得到一个含含m-n+1阶单位矩阵阶单位矩阵(对应于对应于T以外的以外的各边各边)新基本回路矩阵，而新矩阵的秩新基本回路矩阵，而新矩阵的秩不变。不变。. 11010

5、0011010111001321651432CCCCeeeeeefT外各边对应列外各边对应列T各边对应列各边对应列整理课件8(2) 基本回路矩阵和完全回路矩阵的秩基本回路矩阵和完全回路矩阵的秩定理定理1有向连通图的基本回路矩阵有向连通图的基本回路矩阵秩是秩是m-n+1.证证：设：设Cf 是对应于支撑树是对应于支撑树T 的基本回的基本回路矩阵，则路矩阵，则T的一条余边仅在其对应基的一条余边仅在其对应基本回路中出现，而不会在别的基本回路本回路中出现，而不会在别的基本回路中出现。换言之，全部余边在矩阵中出现。换言之，全部余边在矩阵Cf中中对应的列构成的子阵中，每行每列恰含对应的列构成的子阵中，每行每

6、列恰含一个一个1，其余元素均为，其余元素均为0。因为因为Cf 共共m-n+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. 因为因为

7、B的第的第i 行对应结点行对应结点vi， Ce的第的第j 行对应行对应回路回路Cj 。当。当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 的

8、秩是的秩是m-n+1, 故故 秩秩( Ce)=m-n+1. 由由Sylvester定理定理, 若有若有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 是回路矩

9、阵。是回路矩阵。 (2) BCT=0 (B与与C中边的顺序排列一致中边的顺序排列一致) (3) C=PCf，P是某个满秩方阵。是某个满秩方阵。(C与与Cf 中边的顺序排列一致中边的顺序排列一致)整理课件12 G的余树与回路矩阵间的关系的余树与回路矩阵间的关系定理定理4 连通图连通图G 的回路矩阵的回路矩阵C 的任一的任一m-n+1阶子阵行列式非零，当且仅当阶子阵行列式非零，当且仅当这些列对应于这些列对应于G 的某一棵的某一棵余树余树(删去这些列的对应边后，所得图删去这些列的对应边后，所得图是一棵树是一棵树)。证明：证明：充分性充分性. 已知已知G的某支撑树的某支撑树T, 使得此子使得此子阵中那

10、些列对应的全部边就是阵中那些列对应的全部边就是T 以外的全部边。以外的全部边。 于是，于是，T 的基本回路矩阵中这些边对应的各的基本回路矩阵中这些边对应的各列，适当重排顺序后为列，适当重排顺序后为m-n+1 阶单位矩阵，故阶单位矩阵，故该子阵的行列式非零。该子阵的行列式非零。 整理课件13必要性必要性. 将这将这m-n+1列换到最前面列换到最前面(通过重新通过重新对边编号对边编号)，则，则C=(C11,C12)。现在只需证明现在只需证明C12 对应对应G的一棵支撑树。的一棵支撑树。如果如果C12 对应边不是树，则其中必含有回路，对应边不是树，则其中必含有回路，从而必含有一个初级回路。即有一个初

11、级回路从而必含有一个初级回路。即有一个初级回路C，全由，全由C12中的某些列的对应边构成。中的某些列的对应边构成。于是在回路矩阵于是在回路矩阵C 前前m-n+1列列(即即C11)中，初中，初级回路级回路C对应的那行全为对应的那行全为0，所以，所以det(C11) = 0,这与题设矛盾。这与题设矛盾。整理课件14 已知基本关联矩阵已知基本关联矩阵Bk ，求基本回路矩阵，求基本回路矩阵Cf定理定理5 若已知有向连通图的基本关联矩阵若已知有向连通图的基本关联矩阵Bk =(B11,B12)，其中，其中B12是非奇异方阵，则可得是非奇异方阵，则可得基本回路矩阵基本回路矩阵Cf = ( I C12) ，其

12、中，其中C12=-B11TB12-1T.这里这里 Cf 与与Bk的边次序一致。的边次序一致。 证明证明:由定理由定理4 知知B11对应对应G的一个余树的一个余树, 即即B12各列对应一棵支撑树各列对应一棵支撑树T。因此。因此T对应的基本回对应的基本回路矩阵路矩阵Cf前前m-n+1列构成的子方阵中，每行每列构成的子方阵中，每行每列恰含一个列恰含一个1，其余元素为，其余元素为0。重排各行顺序重排各行顺序(即给各基本回路重新编号即给各基本回路重新编号)，整理课件15可使前可使前m-n+1阶子方阵成为单位矩阵阶子方阵成为单位矩阵I。因此，可设因此，可设Cf = ( I C12) 。由定理由定理2 知知

13、BkCfT=0，即，即。，故故即即T 112T111211112T12T121211T121211BBCBBC, 0CBB, 0CIBB整理课件16例例 已知图已知图3.11的基本关联矩阵，其中的基本关联矩阵，其中e1,e5,e6所所对应的子阵行列式非零，求对应的子阵行列式非零，求Cf.),(011100100101001011011001101010000111121165132246543214BBeeeeeeBeeeeeeB整理课件17，因因为为10010101111B，01110000112B，故故计计算算得得010101001121B1100111111100111110101000

14、1111000101112 fC,),(12111212TTfffBBCCIC 其其中中则则整理课件182 . 割集矩阵及其性质割集矩阵及其性质 (1)定义定义设设S是有向图是有向图G =(V,E)的边子集，若的边子集，若 1、G=(V,E-S)比比G的连通支数多的连通支数多1 (去掉这去掉这S包含的边集后，图包含的边集后，图G 恰好多恰好多1个分枝个分枝). 2、对任意、对任意S S, G与与G=(G,E-S)的连通支的连通支数一样数一样(少去一条边，仍是连通的少去一条边，仍是连通的)则称则称S为为割集割集。 连通连通连通连通某连通支某连通支有向割集的有向割集的方向方向(任意规定的一个方向任

15、意规定的一个方向)整理课件19 例例：S1=e2,e3,e4 和和 S2=e4,e5是割集是割集,而而S3=e6,e7不是割集。不是割集。V1V3V2V4V5V6e1e2e3e4e5e6e7S1S2S3整理课件20 (2) 完全割集矩阵完全割集矩阵 有向图有向图G的的全部割集全部割集组成的矩阵，称为组成的矩阵，称为完全割集矩阵完全割集矩阵，记作，记作Se，其元素的定义：，其元素的定义： Sij= 1, ej在在Si中且方向一致中且方向一致; Sij= -1, ej在在Si中且方向相反中且方向相反; Sij= 0，其它，其它. pemSSSSe.ee.2121整理课件21 65432176543

16、21eeeeee101110011101110011110100011010101001000111SSSSSSSSes1s2s3s4s5s6s7整理课件22 (3) 基本割集基本割集 设设T是连通图是连通图G的一棵支撑树，的一棵支撑树，ei 是是T 的一个边。对应的一个边。对应ei存在存在G的割集的割集Si, Si 只包只包括一条树枝边括一条树枝边ei及某些余树枝，且与及某些余树枝，且与ei 的的方向一致。这时称方向一致。这时称Si 为为G的对应树的对应树T的一个的一个基本割集基本割集。ei割集割集Si的方向规定为的方向规定为ei的方向。的方向。整理课件23 定义定义 给定有向连通图的一棵树

17、给定有向连通图的一棵树T，则由全部基本割集组成的矩阵为则由全部基本割集组成的矩阵为基本基本割集矩阵割集矩阵，记作，记作Sf . 对于不同的支撑树对于不同的支撑树T，其对应的基本，其对应的基本割集矩阵割集矩阵Sf 会不同。会不同。 12121 .nfmSSSSe.ee整理课件24s2s4s5654321Seeeeee1011100111011100111101000110101010010001117654321SSSSSSSe对于树对于树T e2,e3,e4 , 101001110100110011 eeeeee 654321245SSSSf整理课件25将将Sf 中边的排列次序作调整：把中边的

18、排列次序作调整：把T 的边放的边放在最前面，非在最前面，非T 的边放在后面；的边放在后面；T 的边适当的边适当排列，可使对应矩阵块为一单位矩阵排列，可使对应矩阵块为一单位矩阵I。, 101001110100110011 eeeeee 654321245SSSSf注意注意 101100110010111-001 eeeeee 651432245SSSSfT 的边的边非非T 的边的边整理课件26(4) 割集矩阵及性质割集矩阵及性质定理定理1 当有向连通图当有向连通图G的完全回路矩阵的完全回路矩阵Ce和和完全割集矩阵完全割集矩阵Se的边次序一致时，有的边次序一致时，有SeCeT=0. 证明证明: 设

19、设Se的第的第i 行为行为(si1, si2, , sim) ，Ce的第的第j 行为行为(cj1, cj2, , cjm) ，则，则 SeCeT中第中第i 行第行第j 个元个元素为素为 dij=si1cj1+ si2cj2+ +simcjm. 因为因为Se的第的第i 行对应割集行对应割集Si， Ce的第的第j 行对应行对应回路回路Cj 。SiCj 当当Cj 与与Si不相交时，对于不相交时，对于Sj 经过经过的边的边ek (Cj不经过不经过)，有，有sikcjk=100 ; 对于对于Cj 经过的边经过的边ek (Sj 不经不经过过)，有，有sikcjk=010 ; 因此因此dij =0.整理课件

20、27 当当Cj 与与Sj 相交时相交时, 它们有偶数条共同的边：它们有偶数条共同的边：其中一半的边与割集方向相同，另一半边则与其中一半的边与割集方向相同，另一半边则与割集方向相反。割集方向相反。对于对于Sj 经过但经过但Cj不经过的边不经过的边ek ，有，有sikcjk=100。 对于对于Sj和和Cj 均经过的一对边均经过的一对边ek , ek (一边与一边与割集方向相同，一边与割集方向相反割集方向相同，一边与割集方向相反)，有，有 sikcjk+ sikcjk= 111(-1)0, 因此因此dij =0.整理课件28 定理定理2 连通图连通图G的完全割集矩阵的完全割集矩阵Se的秩是的秩是n-

21、1. 定理定理3 连通图连通图G 的割集矩阵的割集矩阵S的任意一个的任意一个n-1阶子阵行列式非零阶子阵行列式非零当且仅当当且仅当这些列对应于这些列对应于G的的某棵树某棵树 (与回路矩阵类似与回路矩阵类似) 定理定理4 设设Sf和和Cf分别连通图分别连通图G中关于某棵树中关于某棵树T的基本割集和基本回路矩阵的基本割集和基本回路矩阵,且边次序一致且边次序一致.若若Sf=(Sf11,I),Cf=(I,Cf12),则则Sf11=-Cf12T 。( 由由SeCeT=0 可得可得)整理课件293.5 支撑树的生成支撑树的生成 (1) 两树的距离两树的距离: 设设t1,t2是连通图是连通图G的两棵生的两棵

22、生成树。若成树。若t1中共有中共有k 条边不属于条边不属于t2, 则说则说t1与与t2的的距离距离d(t1,t2)=k。若若d(t1,t2)=k，则，则d(t2,t1)=k.基本树变换基本树变换: 设设t1是连通图是连通图G的一棵生成树，的一棵生成树，边边e t1, 边边e t1, 若对若对t1 加边加边e、去边、去边e后得后得G的的新生成树新生成树 t2= t1 (e, e), 这称为是这称为是t1到到t2的的基本基本树变换树变换。 在在基本树变换基本树变换中，中，t1到到t2的距离为的距离为1.整理课件30 基本割集基本割集Se(t0) :对于连通图对于连通图G的一的一棵生成树棵生成树t0

23、,t0的一条边的一条边e 对应一个基本对应一个基本割集割集Se(t0)，于是树，于是树t0 共对应共对应n-1个基本割个基本割集集. 例例 设设 t0 e1, e2, e3 .Se1(t0)= e1,e4,e6 ,Se2(t0)= e2,e5,e6 ,Se3(t0)= e3,e4,e5 ,v1v4v3v2e1e6e4e3e5e2整理课件31(2) 定理定理1 设设t1是连通图是连通图G的生成树。的生成树。 若若对于对于b Se(t1)(b e)，则则t1-e+b可得一棵距可得一棵距离为离为1的新树。反之，若的新树。反之，若t1-e+b是一棵树，是一棵树， e t1 且且b e ，则则b Se(

24、t1)。eb整理课件32定理定理2 对于对于G的一棵生成树的一棵生成树t0, e t0, 若若Se(t0) = e, b1, b2, , bp ,则则t0-e+b1, t0-e+b2, t0-e+bp是不含是不含e且与且与t0 距离距离为为1的的G的全部生成树。的全部生成树。 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

25、 , 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 的全部生成树的全部生成树)上例中，上例中，Te=t1, t2, Te=t3, t4, Te=t5, t6. 定理定理3 设设t0=(e1,e2,.,ek) 是是G中的一棵生成中的一棵生成树树, 则则G中与中与t0 距离为距离为1的树恰在的树恰在Te, Te, , Te 的某个集合之中。的某个集合之中。eib整理课件34对于对于G 的

26、生成树的生成树t0 及及t0 的边的边e和和f，记，记(不含不含e, f 且与且与t0 距离为距离为2的的G 的全部生成树的全部生成树)即对树即对树t0 中的一条边中的一条边e，用，用Se(t0)中的每条边替换中的每条边替换e后得到后得到Te, 然后对然后对Te中的每棵树中的每棵树t, 再用再用中的每条边替换中的每条边替换f 后得到树集后得到树集Tt, 这样所有的这样所有的Tt的并就是的并就是Tef ，即，即Tef t Tt.ebf整理课件35定义定义 T,1 i n-11 ij n-11 ijw1)比离根更远，则互换树比离根更远，则互换树叶叶i,1的权值后，新树的带权路径总长比的权值后，新树

27、的带权路径总长比T小，这小，这与与T是最优二叉树矛盾。是最优二叉树矛盾。 若若w1无兄弟，则删除相应于的树叶树枝，将无兄弟，则删除相应于的树叶树枝，将权赋给的父亲，所得新树的带权路径总长比权赋给的父亲，所得新树的带权路径总长比T小，小，这与这与T是最优二叉树矛盾。是最优二叉树矛盾。所以所以w1有兄弟，且必须是有兄弟，且必须是w2 。 2) WPL(T)=l1w1+l2w2+lnwn =l1(w1+w2)+l3 w3+lnwn= WPL(T).整理课件42上述定理告诉我们：要画一棵带有上述定理告诉我们：要画一棵带有n个权的最个权的最优二叉树，可简化为一棵带有优二叉树，可简化为一棵带有n-1个权的

28、最优二个权的最优二叉树，而这又可简化为画一棵带有叉树，而这又可简化为画一棵带有n-2个权的最个权的最优二叉树，优二叉树，.。 构造最优二叉树的构造最优二叉树的Huffman算法算法 1) 将权值排序：将权值排序： w1 w2 wn, 要求以上权值的最优二叉树要求以上权值的最优二叉树T。 2) 作一个由公共分枝点的两树枝，两树叶作一个由公共分枝点的两树枝，两树叶分别带最小权分别带最小权w1,w2 ; 3) 再考虑权值为再考虑权值为w1+w2 , w3 , , wn的最优二的最优二叉树；叉树；反复执行反复执行1)2)3), 直到权值只剩一个为止。直到权值只剩一个为止。 整理课件43 例例“一地在要

29、工上是中国同和的有一地在要工上是中国同和的有”在某在某文的频率如下：文的频率如下：2,3,5,7,11,13,17,19,23,29,31,37,41，用用Huffman方法构造相应的最优二叉树方法构造相应的最优二叉树,分别分别对以上汉字编码，写出对以上汉字编码，写出“中国一地要工有中国一地要工有”的的编码，译出编码，译出“101011”的对应的汉字。的对应的汉字。 解解：首先组合：首先组合2+3，寻找，寻找5,5,7,.,41的最优二的最优二叉树，然后组合叉树，然后组合5+5,寻找寻找10,7,11,.,41最优二叉最优二叉树。依此继续。这个过程综合为：树。依此继续。这个过程综合为：例例 (

30、p57)整理课件44整理课件453.7 最短树最短树 1. 对于赋权连通图，有时要寻找生成树对于赋权连通图，有时要寻找生成树各边权之和最小或最大的某一棵。各边权之和最小或最大的某一棵。 权可为长度、运输量、费用等。权可为长度、运输量、费用等。 最小生成树最小生成树： 在赋权连通图的所有生成在赋权连通图的所有生成树中权之和最小的生成树，称为树中权之和最小的生成树，称为G的最小的最小生成树。生成树。 整理课件46 2. Kruskal算法算法 设赋权连通图设赋权连通图G 有有n个结点个结点. (1) 将全部边按权值由小到大排序：将全部边按权值由小到大排序： e1 e2 en; (2) 初始化：令初

31、始化：令T:=, i:=1; (3) 迭代：迭代：若若|T|=n-1, 则结束；则结束；若若T+ei 不含回路，则不含回路，则T:=T+ei ; i:=i+1, 返回返回(3). Kruskal算法的思路算法的思路是，开始是，开始T 为空，而后将为空，而后将边边e1,e2, , en 依次试放入依次试放入T，如果含回路则拿出，如果含回路则拿出，否则正式放入否则正式放入T, 直到直到T 有有n-1条边为止。条边为止。 整理课件47例例1 给定一个赋权的连通图，用给定一个赋权的连通图，用Kruskal算法求最小生成树。算法求最小生成树。 该生成树的边数该生成树的边数= 6-1=5， 树权树权=生成

32、树的边权和生成树的边权和=18 .整理课件48例例2 求下列赋权连通图的一棵最小生成树。求下列赋权连通图的一棵最小生成树。11212122 权有相同的时，最小权有相同的时，最小生成树可能不唯一。生成树可能不唯一。或：或：整理课件49(3) Prim算法算法 首先任选一结点首先任选一结点v0 , 构成集合构成集合U。然后选。然后选V-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)

33、, U=U+u, end整理课件50例例用用Prim算法求下列图的一个最小生成树。算法求下列图的一个最小生成树。15101020153040251510103020v1v2v5v3v4v1v2v5v3v4迭代：迭代：(0) U=v1, V-U= v2, v3, v4, v5 (1) U=v1 , v2, V-U=v3, v4, v5 (2) 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是赋权

34、连通图是赋权连通图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 最大分枝最大分枝上节讨论无向图的最短树和最长树上节讨论无向图的最短树和最长树, 最大权最大权根树等问题根树等问题. 由于有的图并不存在根树由于有的图并不存在根树, 所以也所以也不可能存在最大权根树不可能存在最大权根树.分枝分