无向图关联矩阵(性质) 每列和为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