回路矩阵与割集矩阵.ppt
《回路矩阵与割集矩阵.ppt》由会员分享,可在线阅读,更多相关《回路矩阵与割集矩阵.ppt(55页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、图图 论论()刘晓华刘晓华13.4回路矩阵与割集矩阵回路矩阵与割集矩阵 有向连通图有向连通图G=(V,E)的回路矩阵和割集矩的回路矩阵和割集矩阵,与阵,与G的支撑树有密切联系。的支撑树有密切联系。1.回路矩阵及其性质回路矩阵及其性质(1)概念概念设设T是有向连通图是有向连通图G的一棵支撑树的一棵支撑树,对于不对于不在在T上的边上的边e,T+e必含一个唯一回路必含一个唯一回路C.如果给回路如果给回路C定一个参考方向定一个参考方向,那么那么C中方中方向与回路方向一致的边向与回路方向一致的边,就称为就称为正向边正向边,否则称否则称为为反向边反向边.2将将G的全部初级回路对应的向量构成的全部初级回路对
2、应的向量构成一个矩阵,这就是一个矩阵,这就是G的的完全回路矩阵完全回路矩阵Ce。设设G的全部边为的全部边为e1,e2,em,则则初级回路初级回路Ci对应向量对应向量(ci1,ci2,cim),其中其中3例例(p.46)求右求右图的完全回路图的完全回路矩阵矩阵.c c1 1V1V2V4e2e1e3e4e5e6c c2 2C C4 4c c3 3c c5 5c c6 6c c7 7V34一个图的初级回路很多,其中哪些是一个图的初级回路很多,其中哪些是最基本的呢?或者说最基本的呢?或者说,Ce中中哪些行构成哪些行构成全部行的极大无关组呢?全部行的极大无关组呢?定义定义设设T是图是图G的一棵支撑树,则
3、的一棵支撑树,则T以外以外的每条边对应的回路的每条边对应的回路(一条边恰好对一条边恰好对应一个回路,应一个回路,回路的方向规定为此边的回路的方向规定为此边的方向方向)均称为均称为基本回路基本回路,全部,全部m-n+1个个基基本回路构成的矩阵本回路构成的矩阵Cf,称为称为G的的基本回基本回路矩阵路矩阵。支撑树的支撑树的余边余边:以外的任何一边以外的任何一边5V4V1V2V3e2e1e3e4e5e6C1C2C3例例(p.46)对图对图G的支的支撑树撑树T=e1,e5,e6,求其求其基本回路矩阵。基本回路矩阵。T的余边的余边e2,e3,e4,分别分别对应回路对应回路C1,C2,C3,故故T外各边对应
4、列外各边对应列6重新排列行和列的顺序重新排列行和列的顺序(相当于对各相当于对各回路和各边重新编号回路和各边重新编号),可以得到一个,可以得到一个含含m-n+1阶单位矩阵阶单位矩阵(对应于对应于T以外的以外的各边各边)新基本回路矩阵,而新矩阵的秩新基本回路矩阵,而新矩阵的秩不变。不变。T外各边对应列外各边对应列T各边对应列各边对应列7(2)基本回路矩阵和完全回路矩阵的秩基本回路矩阵和完全回路矩阵的秩定理定理1有向连通图的基本回路矩阵有向连通图的基本回路矩阵秩是秩是m-n+1.证证:设:设Cf是是对应于支撑树对应于支撑树T的基本回的基本回路矩阵,则路矩阵,则T的一条余边仅在的一条余边仅在其对应基其
5、对应基本回路中出现,而不会在别的基本回路本回路中出现,而不会在别的基本回路中出现。换言之,全部余边在矩阵中出现。换言之,全部余边在矩阵Cf中中对应的列构成的子阵中,每行每列恰含对应的列构成的子阵中,每行每列恰含一个一个1,其余元素均为,其余元素均为0。因为因为Cf共共m-n+1行,而以上证明其行行,而以上证明其行向量组线性无关,故它的秩是向量组线性无关,故它的秩是m-n+1。8定理定理2有向连通图有向连通图G的关联矩阵的关联矩阵B与完全回与完全回路矩阵路矩阵Ce的的边次序一致时,恒有边次序一致时,恒有BCeT=0。证明证明:设设B的第的第i行为行为(bi1,bi2,bim),Ce的第的第j行为
6、行为(cj1,cj2,cjm),则则BCeT中第中第i行行第第j个元素为个元素为dij=bi1cj1+bi2cj2+bimcjm.因为因为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.9定理定理3有向连通图有向连通图G的完全回路矩阵的完全回路矩阵Ce的秩是的秩是m-n+1.证明证明:由于基本回
7、路矩阵:由于基本回路矩阵Cf是是完全回路矩阵完全回路矩阵的的Ce的的子阵子阵,而而Cf的的秩是秩是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。10(3)回路矩阵回路矩阵定义定义由连通图由连通图G的有的有m-n+1个互相独个互相独立的回路组成的矩阵,称为立的回路组成的矩阵,称为G的的回路矩阵回路矩阵,记记为为C。性质性质:(1
8、)基本回路矩阵基本回路矩阵Cf是回路矩阵。是回路矩阵。(2)BCT=0(B与与C中边的顺序排列一致中边的顺序排列一致)(3)C=PCf,P是某个满秩方阵。是某个满秩方阵。(C与与Cf中边的顺序排列一致中边的顺序排列一致)11G的余树与回路矩阵间的关系的余树与回路矩阵间的关系定理定理4连通图连通图G的回路矩阵的回路矩阵C的任一的任一m-n+1阶子阵行列式非零,当且仅当阶子阵行列式非零,当且仅当这些列对应于这些列对应于G的某一棵的某一棵余树余树(删去这些列的对应边后,所得图删去这些列的对应边后,所得图是一棵树是一棵树)。证明:证明:充分性充分性.已知已知G的某支撑树的某支撑树T,使得此子使得此子阵
9、中那些列对应的全部边就是阵中那些列对应的全部边就是T以外的全部边。以外的全部边。于是,于是,T的基本回路矩阵中这些边对应的各的基本回路矩阵中这些边对应的各列,适当重排顺序后为列,适当重排顺序后为m-n+1阶单位矩阵,故阶单位矩阵,故该子阵的行列式非零。该子阵的行列式非零。12必要性必要性.将这将这m-n+1列换到最前面列换到最前面(通过重新通过重新对边编号对边编号),则,则C=(C11,C12)。现在只需证明现在只需证明C12对应对应G的一棵支撑树。的一棵支撑树。如果如果C12对应边不是树,则其中必含有回路,对应边不是树,则其中必含有回路,从而必含有一个初级回路。即有一个初级回路从而必含有一个
10、初级回路。即有一个初级回路C,全由全由C12中的某些列的对应边构成。中的某些列的对应边构成。于是在回路矩阵于是在回路矩阵C前前m-n+1列列(即即C11)中,初中,初级回路级回路C对应的那行全为对应的那行全为0,所以,所以det(C11)=0,这与题设矛盾。这与题设矛盾。13已知基本关联矩阵已知基本关联矩阵Bk,求基本回路矩阵求基本回路矩阵Cf定理定理5若已知有向连通图的基本关联矩阵若已知有向连通图的基本关联矩阵Bk=(B11,B12),其中其中B12是非奇异方阵,则可得是非奇异方阵,则可得基本回路矩阵基本回路矩阵Cf=(IC12),其中其中C12=-B11TB12-1T.这里这里Cf与与Bk
11、的的边次序一致。边次序一致。证明证明:由定理由定理4知知B11对应对应G的一个余树的一个余树,即即B12各列对应一棵支撑树各列对应一棵支撑树T。因此因此T对应的基本对应的基本回路矩阵回路矩阵Cf前前m-n+1列构成的子方阵中,每行列构成的子方阵中,每行每列恰含一个每列恰含一个1,其余元素为,其余元素为0。重排各行顺序重排各行顺序(即给各基本回路重新编号即给各基本回路重新编号),14可使前可使前m-n+1阶子方阵成为单位矩阵阶子方阵成为单位矩阵I。因此,可设因此,可设Cf=(IC12)。由定理由定理2知知BkCfT=0,即即15例例已知图已知图3.11的基本关联矩阵,其中的基本关联矩阵,其中e1
12、,e5,e6所对应的子阵行列式非零,求所对应的子阵行列式非零,求Cf.16172.割集矩阵及其性质割集矩阵及其性质(1)定义定义设设S是有向图是有向图G=(V,E)的边子集,若的边子集,若1、G=(V,E-S)比比G的连通支数多的连通支数多1(去掉这去掉这S包含的边集后,图包含的边集后,图G恰好多恰好多1个分枝个分枝).2、对任意、对任意S S,G与与G=(G,E-S)的连通支的连通支数一样数一样(少去一条边,仍是连通的少去一条边,仍是连通的)则称则称S为为割集割集。连通连通连通连通某连通支某连通支有向割集的有向割集的方向方向(任意规定的一个方向任意规定的一个方向)18例例:S1=e2,e3,
13、e4和和S2=e4,e5是割集是割集,而而S3=e6,e7不是割集不是割集。V1V3V2V4V5V6e1e2e3e4e5e6e7S1S2S319(2)完全割集矩阵完全割集矩阵有向图有向图G的的全部割集全部割集组成的矩阵,称为组成的矩阵,称为完全割集矩阵完全割集矩阵,记作,记作Se,其元素的定义:其元素的定义:Sij=1,ej在在Si中且方向一致中且方向一致;Sij=-1,ej在在Si中且方向相反中且方向相反;Sij=0,其它其它.20V1V2V3V4e1e2e3e4e5e6s1s2s3s4s5s6s721(3)基本割集基本割集设设T是连通图是连通图G的一棵支撑树,的一棵支撑树,ei是是T的一个
14、边。对应的一个边。对应ei存在存在G的割集的割集Si,Si只只包包括一条树枝边括一条树枝边ei及某些余树枝,且与及某些余树枝,且与ei的的方方向一致。这时称向一致。这时称Si为为G的对应树的对应树T的一个的一个基基本割集本割集。ei割集割集Si的的方向规定为方向规定为ei的方向。的方向。22定义定义给定有向连通图的一棵树给定有向连通图的一棵树T,则由全部基本割集组成的矩阵为则由全部基本割集组成的矩阵为基本基本割集矩阵割集矩阵,记作,记作Sf.对于不同的支撑树对于不同的支撑树T,其对应的基本其对应的基本割集矩阵割集矩阵Sf会不同。会不同。23V1V2V3V4e1e2e3e4e5e6s2s4s5对
15、于树对于树Te2,e3,e4,24将将Sf中边的中边的排列次序作调整:把排列次序作调整:把T的边放的边放在最前面,非在最前面,非T的边放在后面;的边放在后面;T的边适当的边适当排列,可使对应矩阵块为一单位矩阵排列,可使对应矩阵块为一单位矩阵I。注意注意T的边的边非非T的边的边25(4)割集矩阵及性质割集矩阵及性质定理定理1当有向连通图当有向连通图G的完全回路矩阵的完全回路矩阵Ce和和完全割集矩阵完全割集矩阵Se的边次序一致时,有的边次序一致时,有SeCeT=0.证明证明:设设Se的第的第i行为行为(si1,si2,sim),Ce的的第第j行为行为(cj1,cj2,cjm),则则SeCeT中第中
16、第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.26当当Cj与与Sj相交时相交时,它们有偶数条共同的边:它们有偶数条共同的边:其中一半的边与割集方向相同,另一半边则与其中一半的边与割集方向相同,另一半边则与割集方向相反。割集方向相反。对于对于Sj经过但
17、经过但Cj不经过的边不经过的边ek,有有sikcjk=100。对于对于Sj和和Cj均经过的一对边均经过的一对边ek,ek(一边与一边与割集方向相同,一边与割集方向相反割集方向相同,一边与割集方向相反),有,有sikcjk+sikcjk=111(-1)0,因此因此dij=0.27定理定理2连通图连通图G的完全割集矩阵的完全割集矩阵Se的秩是的秩是n-1.定理定理3连通图连通图G的割集矩阵的割集矩阵S的任意一个的任意一个n-1阶子阵行列式非零阶子阵行列式非零当且仅当当且仅当这些列对应于这些列对应于G的的某棵树某棵树(与回路矩阵类似与回路矩阵类似)定理定理4设设Sf和和Cf分别连通图分别连通图G中关
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回路 矩阵
限制150内