《图论》第7章-回路矩阵与割集矩阵.pptVIP

人工智能 华中科技大学水电与数字化工程学院 7.1 回路矩阵 [回路矩阵] 设有向连通图 G=(V, A)，A={ai | i=1..m}，G中有确定方向的简单回路C1、 C2、 … Ck ，定义回路矩阵 C=(cij)k?m 1 aj ?A在Ci中且方向一致 cij = -1 aj ?A在Ci中且方向相反 0 其他 [完全回路矩阵] 若C1、C2、… 、Ck 包括了G的所有回路，则称C为G的完全回路矩阵，记为 Ce 。 7.1 回路矩阵 [例] 7.1 回路矩阵 [回路的数目] 对连通图G的一棵生成树T，余树边有 m-n+1条，故G中至少有 m-n+1条回路。 在上述生成树T的余树中任取 k ? m-n+1 条边，都可能与生成树中的若干条边构成一条回路，且G中所有回路均可如此构成（或说G的每一条回路至少含有一条T的余树边），故G中回路数目最多有： 7.1 回路矩阵 [基本回路] 设T为有向连通图G的一棵生成树，T的余树的每一边都与T中若干边构成唯一的回路，称之为G关于T的一条基本回路。规定基本回路的方向与相应的余树边的方向一致。 [基本回路矩阵] 由所有基本回路构成的回路矩阵称为基本回路矩阵，记为 Cf 。显然G的基本回路的定义与生成树T的选择有关。 7.1 回路矩阵 调整上述矩阵弧的位置后，得矩阵： 7.1 回路矩阵 [定理7-1-2] 有向连通图 G=(V, A) 的关联矩阵B和回路矩阵C中各弧的排列次序一致时，有 B?CT=0 （即B和C正交）。 [证明] 观察 (B?CT)ij= bi1cj1+ bi2cj2+ …+ bimcjm ，m=|A| 各项中当且仅当边 al 关联于 vi 且 al?Cj 时，bilcjl ?0。满足条件的 vi 的关联边在 Cj上两两配对，4种关系示意如下： 7.1 回路矩阵 ① bikcjk+ bilcjl =(-1)?1+1?1=0 ② bikcjk+ bilcjl = (-1)?1+(-1)?(-1)=0 ③ bikcjk+ bilcjl =1?(-1)+1?1=0 ④ bikcjk+ bilcjl =1?(-1)+(-1)?(-1)= 0 故 (B?CT)ij= 0 ，从而得 B?CT= 0 7.1 回路矩阵 [结论1] 将列适当排列后，Cf =( I(m-n-1)?(m-n+1) , C12), 考察C12各列对应边的拓扑结构解释。 将Bk的列按Cf 排列并分块，记为Bk =(B11, B12)，由上述定理证明过程易知基本关联矩阵Bk和基本回路矩阵的正交性也成立：Bk?CfT=0 。 故 B11+ B12 ?C12T=0 即 B11= -B12 ?C12T 故 Bk =( -B12 ?C12T , B12) = B12 ?( -C12T , I ) 而 r(Bk ) = n-1，故 r(B12 ) = n-1，即 | B12 | ? 0 由[定理3-2-5]知此时B12各列对应的弧构成G的一棵树。 也即 C12各列对应的弧构成G的一棵树。 7.1 回路矩阵 [结论2] 由基本关联矩阵可求基本回路矩阵 由：B11+ B12 ?C12T=0 以及 B12可逆（| B12 | ? 0） 得：C12T = -B12-1 ? B11 故：C12 = -B11T ? B12-T 即：Cf =( I(m-n-1)?(m-n+1) , C12)= =( I(m-n-1)?(m-n+1) , -B11T ? B12-T) 7.1 回路矩阵 [结论3] 完全回路矩阵 Ce 的秩 已知 r(Cf ) = m-n+1 故： r(Ce) ? r(Cf ) = m-n+1 又： r(B ?CeT) ? r(B)+r(CeT)-m（因 Bn?m，CeT m?L） 即： 0 ? (n-1)+r(CeT)-m (B ?CeT=0，r(B) = n-1) 得： r(Ce) ? m-n+1 故： r(Ce) = m-n+1 结论3的拓扑意义：在图的 Euler子图集合中独立的回路有 (m-n+1) 个，所有回路可由这些独立回路表出。 7.1 回路矩阵 [定理7-1-3] 从图G的基本回路矩阵中任取(m?n+1)列组成一个(m-n+1) 阶行列式，它的值非零的充要条件是：这些列正好对应于G的某一余树的