3.4回路矩阵与割集矩阵-Read.ppt

3.4 回路矩阵与割集矩阵 有向连通图G=(V,E) 的回路矩阵和割集矩阵，与G 的支撑树有密切联系。 回路矩阵及其性质 (1) 概念 设T是有向连通图G的一棵支撑树, 对于不在T上的边e，T+e 必含一个唯一回路C. 　如果给回路C定一个参考方向, 那么C中方向与回路方向一致的边, 就称为正向边,否则称为反向边.　 　　将G的全部初级回路对应的向量构成一个矩阵，这就是G的完全回路矩阵Ce。 一个图的初级回路很多，其中哪些是最基本的呢？或者说, Ce中哪些行构成全部行的极大无关组呢？ 　定义　设T是图G的一棵支撑树，则T以外的每条边对应的回路(一条边恰好对应一个回路，回路的方向规定为此边的方向)均称为基本回路，全部m-n+1个基本回路构成的矩阵Cf ，称为G的基本回路矩阵。 支撑树Ｔ的余边: Ｔ以外的任何一边 (2) 基本回路矩阵和完全回路矩阵的秩 　定理1　有向连通图的基本回路矩阵秩是m-n+1. 　证：设Cf 是对应于支撑树T 的基本回路矩阵，则T的一条余边仅在其对应基本回路中出现，而不会在别的基本回路中出现。换言之，全部余边在矩阵Cf中对应的列构成的子阵中，每行每列恰含一个1，其余元素均为0。 　因为Cf 共m-n+1行，而以上证明其行向量组线性无关，故它的秩是m-n+1 。 定理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 行对应回路Cj 。当Cj 不经过vi时,对于满足bik≠0的k,必有cjk=0，因此dij =0; 当Cj 经过vi时,恰有Cj的两条边ek,el 经过vi(不妨设一进一出)，则 　　　dij= bikcjk+ bilcjl =1×1＋1×(-1)＝0 . 定理3　 有向连通图G的完全回路矩阵Ce的秩是m-n+1. 证明：由于基本回路矩阵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。 (3) 回路矩阵 　定义　由连通图G的有m-n+1个互相独立的回路组成的矩阵，称为G的回路矩阵，记为C。 性质:(1) 基本回路矩阵Cf 是回路矩阵。 (2) BCT=0 (B与C中边的顺序排列一致) 　　 (3) C=PCf，P是某个满秩方阵。 　　　　　(C与Cf 中边的顺序排列一致) G的余树与回路矩阵间的关系 定理4 连通图G 的回路矩阵C 的任一m-n+1阶子阵行列式非零，当且仅当这些列对应于G 的某一棵余树(删去这些列的对应边后，所得图是一棵树)。 　证明：充分性. 已知G的某支撑树T, 使得此子阵中那些列对应的全部边就是T 以外的全部边。 于是，T 的基本回路矩阵中这些边对应的各列，适当重排顺序后为m-n+1 阶单位矩阵，故该子阵的行列式非零。 已知基本关联矩阵Bk ，求基本回路矩阵Cf 定理5 若已知有向连通图的基本关联矩阵Bk =(B11,B12)，其中B12是非奇异方阵，则可得基本回路矩阵 　　Cf = ( I C12) ，其中C12=-B11TB12-1T. 这里 Cf 与Bk的边次序一致。 证明:由定理4 知B11对应G的一个余树, 即B12各列对应一棵支撑树T。因此T对应的基本回路矩阵Cf前m-n+1列构成的子方阵中，每行每列恰含一个1，其余元素为0。 　　重排各行顺序(即给各基本回路重新编号)， 可使前m-n+1阶子方阵成为单位矩阵I。 　因此，可设Cf = ( I C12) 。 　由定理2 知BkCfT=0，即 例 已知图3.11的基本关联矩阵，其中e1,e5,e6所对应的子阵行列式非零，求Cf. 2 . 割集矩阵及其性质 (1)定义　设S是有向图G =(V,E)的边子集，若 1、G’=(V,E-S)比G的连通支数多1 (去掉这S包含的边集后，图G 恰好多1个分枝). 2、对任意S’?