有向图邻接矩阵 设D=<V,E>是有向图={V1,V2,n 邻按矩阵( adjacence matrix) A(D)ana=从W到v的边数 A(D)=n2|0010 0011 《集合论与图论》第22讲 16
《集合论与图论》第22讲 16 有向图邻接矩阵 设D=<V,E>是有向图,V={v1,v2,…,vn} 邻接矩阵(adjacence matrix): A(D)=[aij]n×n, aij = 从vi到vj的边数 v1 v2 v4 v3 ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = 0 0 1 1 0 0 0 1 0 0 1 0 0 2 1 0 ( ) 1 2 3 4 4 3 2 1 v v v v v v v v A D
有向图邻接矩阵(性质) 每行和为出度:=a=() 每列和为入度:∑=ad( 握手定理:E2)+E=1d(y)=m 秦环个数:∑=an AD)=1,0010 0011 《集合论与图论》第22讲
《集合论与图论》第22 讲 17 有向图邻接矩阵 (性质 ) 每行和为出度: Σ n j=1 aij=d +(vi) 每列和为入度: Σ n i=1 aij=d -(vj ) 握手定理: Σ n i=1 Σ n j=1 aij = Σ n i=1 d -(vj)=m 环个数: Σ n i=1 aii v1 v 2 v 4 v 3 ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 0 0 1 1 0 0 0 1 0 0 1 0 0 2 1 0 ( ) 1 2 3 4 4 3 2 1 v v v v v v v v A D
邻接矩阵与通路数 ●设A(D)=A=⊙A+A2+…+A=sn A=A·A、(2) A=[a0, Br 定理4:a=从到v长度为r的通路总数入 //q()=长度为r的通路总数∧ ∑a=长度为r的回路总数 推论:b=从v到v长度≤r的通路总数入 ∑1②∑n=b=长度≤r的通路总数∧ ∑1b0=长度s的回路总数、# 《集合论与图论》第22讲 8
《集合论与图论》第22讲 18 邻接矩阵与通路数 设A(D)=A=[aij]n×n, Ar=Ar-1•A,(r≥2), Ar=[a(r)ij]n×n, Br=A+A2+…+Ar= [b(r)ij]n×n 定理4: a(r)ij=从vi到vj长度为r的通路总数∧ Σni=1Σnj=1a(r)ij=长度为r的通路总数 ∧ Σni=1a(r)ii=长度为r的回路总数 推论: b(r)ij=从vi到vj长度≤r的通路总数∧ Σni=1Σnj=1b(r)ij=长度≤r的通路总数 ∧ Σni=1b(r)ii=长度≤r的回路总数. #