无向图关联矩阵(例) e1 e2e MG= 10010 V3 《集合论与图论》第22讲
《集合论与图论》第22讲 6 无向图关联矩阵(例) ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 ( ) 1 2 3 4 5 6 4 3 2 1 e e e e e e v v v v M G v1 v2 v4 v3 e1 e2 e3 e4 e6 e5
无向图关联矩阵(性质) 每列和为2=m2(1mmn=2m) 每行和为d):0v)=∑mn ●每行所有1对应的边构成断集: 平行边:相同两列 秦伪对角阵:对角块是连通分支 1110 G MG) 1001 MG M(G2) MG) V4 《集合论与图论》第22讲
《集合论与图论》第22讲 7 无向图关联矩阵(性质) 每列和为2: Σni=1mij=2 ( Σni=1Σmj=1mij=2m ) 每行和为d(v): d(vi)=Σmj=1mij 每行所有1对应的边构成断集: [{vi}, {vi}] 平行边: 相同两列 伪对角阵: 对角块是连通分支 ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 ( ) 1 2 3 4 5 6 4 3 2 1 e e e e e e v v v v M G ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = ( ) ( ) ( ) ( ) 2 1 M Gk M G M G M G O
无向图关联矩阵的秩 定理101:G连通→(M(G)=n1(F=0,1) 秦证明:(1)M(G)每行对应1个断集,断集空 间C辉的维数是n-1,所以r(M(G)n-1 (2)M(G)的前n-1行M1M2…,M线性 无 关,所以(M(G)2n-1.(反证)若前s行 线性相关,M④M2.M=0m,则M 每列有2个1或全是0 令V=W1V2,y则N,V)=②,即G不 连通,矛盾!# 《集合论与图论》第22讲
《集合论与图论》第22讲 8 无向图关联矩阵的秩 定理10.1: G连通⇒r(M(G))=n-1 (F={0,1}) 证明: (1) M(G)每行对应1个断集, 断集空 间C断的维数是n-1, 所以r(M(G))≤n-1. (2) M(G)的前n-1行M1,M2,…,Mn-1线性无 关, 所以r(M(G))≥n-1. (反证)若前s行 线性相关, M1⊕M2⊕…⊕Ms=01×m, 则 每列有2个1或全是0. 令V1={v1,v2,…,vs}, 则(V1,V1)=∅, 即G不 连通, 矛盾! # ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = MS MM M M21 '
无向图基本关联矩阵 设G=<V,E>是无环无向图,V{v1V2,w E={e1,e2…,em} 参考点:任意1个顶点 秦基本关联矩阵( fundamental incidence matx:从M(G)删除参考点对应的行,记 作MG) 《集合论与图论》第22讲
《集合论与图论》第22讲 9 无向图基本关联矩阵 设G=<V,E>是无环无向图,V={v1,v2,…,vn}, E={e1,e2,…,em} 参考点: 任意1个顶点 基本关联矩阵(fundamental incidence matrix): 从M(G)删除参考点对应的行, 记 作Mf(G)
无向图基本关联矩阵的秩 定理102:G连通→r(M(G)=n1# 推论1:G有p个连通分支→r(M(G)=np, 其中M(G)是从MG)的每个对角块中删除 任意1行而得到的# 推论2:G连通rMG)=(M(G)=n-1.# 《集合论与图论》第22讲
《集合论与图论》第22讲 10 无向图基本关联矩阵的秩 定理10.2: G连通⇒r(Mf(G))=n-1. # 推论1: G有p个连通分支⇒r(Mf(G))=n-p, 其中Mf(G)是从M(G)的每个对角块中删除 任意1行而得到的. # 推论2: G连通⇔r(M(G))=r(Mf(G))=n-1. #