回路矩阵与割集矩阵.ppt

《回路矩阵与割集矩阵.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论(Ⅴ)刘晓华13.4回路矩阵与割集矩阵有向连通图G=(V,E)的回路矩阵和割集矩阵，与G的支撑树有密切联系。回路矩阵及其性质(1)概念设T是有向连通图G的一棵支撑树,对于不在T上的边e，T+e必含一个唯一回路C.如果给回路C定一个参考方向,那么C中方向与回路方向一致的边,就称为正向边,否则称为反向边.2将G的全部初级回路对应的向量构成一个矩阵，这就是G的完全回路矩阵Ce。设G的全部边为e1,e2,…,em，则初级回路Ci对应向量(ci1,ci2,…,cim),其中3例(p.46)求右图的完全回路矩阵.c1V1V2V4e2e1e3e4e5e6c2C4c3c5c6c7V34一个图的初级

2、回路很多，其中哪些是最基本的呢？或者说,Ce中哪些行构成全部行的极大无关组呢？定义设T是图G的一棵支撑树，则T以外的每条边对应的回路(一条边恰好对应一个回路，回路的方向规定为此边的方向)均称为基本回路，全部m-n+1个基本回路构成的矩阵Cf，称为G的基本回路矩阵。支撑树Ｔ的余边:Ｔ以外的任何一边5V4V1V2V3e2e1e3e4e5e6C1C2C3例(p.46)对图G的支撑树T={e1,e5,e6}，求其基本回路矩阵。T的余边e2,e3,e4,分别对应回路C1,C2,C3,故T外各边对应列6重新排列行和列的顺序(相当于对各回路和各边重新编号)，可以得到一个含m-n+1阶单位矩阵(对应于

3、T以外的各边)新基本回路矩阵，而新矩阵的秩不变。T外各边对应列T各边对应列7(2)基本回路矩阵和完全回路矩阵的秩定理1有向连通图的基本回路矩阵秩是m-n+1.证：设Cf是对应于支撑树T的基本回路矩阵，则T的一条余边仅在其对应基本回路中出现，而不会在别的基本回路中出现。换言之，全部余边在矩阵Cf中对应的列构成的子阵中，每行每列恰含一个1，其余元素均为0。因为Cf共m-n+1行，而以上证明其行向量组线性无关，故它的秩是m-n+1。8定理2有向连通图G的关联矩阵B与完全回路矩阵Ce的边次序一致时，恒有BCeT=0。证明:设B的第i行为(bi1,bi2,…,bim)，Ce的第j行为(cj1,c

4、j2,…,cjm)，则BCeT中第i行第j个元素为dij=bi1cj1+bi2cj2+…+bimcjm.因为B的第i行对应结点vi，Ce的第j行对应回路Cj。当Cj不经过vi时,对于满足bik≠0的k,必有cjk=0，因此dij=0;当Cj经过vi时,恰有Cj的两条边ek,el经过vi(不妨设一进一出)，则dij=bikcjk+bilcjl=1×1＋1×(-1)＝0.9定理3有向连通图G的完全回路矩阵Ce的秩是m-n+1.证明：由于基本回路矩阵Cf是完全回路矩阵的Ce的子阵,而Cf的秩是m-n+1,故秩(Ce)>=m-n+1.由Sylvester定理,若有AnmDms=0,则秩(A

5、)+秩(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)基本回路矩阵Cf是回路矩阵。(2)BCT=0(B与C中边的顺序排列一致)(3)C=PCf，P是某个满秩方阵。(C与Cf中边的顺序排列一致)11G的余树与回路矩阵间的关系定理4连通图G的回路矩阵C的任一m-n+1阶子阵行列式非零，当且仅当这些列对应于G的某一棵余树(删去这些列的对应边后，所得图是一棵树)。

6、证明：充分性.已知G的某支撑树T,使得此子阵中那些列对应的全部边就是T以外的全部边。于是，T的基本回路矩阵中这些边对应的各列，适当重排顺序后为m-n+1阶单位矩阵，故该子阵的行列式非零。12必要性.将这m-n+1列换到最前面(通过重新对边编号)，则C=(C11,C12)。现在只需证明C12对应G的一棵支撑树。如果C12对应边不是树，则其中必含有回路，从而必含有一个初级回路。即有一个初级回路C’，全由C12中的某些列的对应边构成。于是在回路矩阵C前m-n+1列(即C11)中，初级回路C’对应的那行全为0，所以det(C11)=0,这与题设矛盾。13已知基本关联矩阵Bk，求基本回路矩阵Cf

7、定理5若已知有向连通图的基本关联矩阵Bk=(B11,B12)，其中B12是非奇异方阵，则可得基本回路矩阵Cf=(IC12)，其中C12=-B11TB12-1T.这里Cf与Bk的边次序一致。证明:由定理4知B11对应G的一个余树,即B12各列对应一棵支撑树T。因此T对应的基本回路矩阵Cf前m-n+1列构成的子方阵中，每行每列恰含一个1，其余元素为0。重排各行顺序(即给各基本回路重新编号)，14可使前m-n+1阶子方阵成为单位矩阵I。因此，可设Cf