第2讲图的矩阵表示 1.关联矩阵M(①),M(G) 2用基本联矩阵MG求所有生成树 壽3.邻接矩阵A(D,相邻矩阵A(G) 4.用A的幂求不同长度通路(回路)总数 5.可达矩阵P(D,连通矩阵P(G) 6.单源最短路径问题, Dijkstra算法 《集合论与图论》第22讲
《集合论与图论》第22讲 1 第22讲 图的矩阵表示 1. 关联矩阵M(D), M(G) 2. 用基本联矩阵Mf(G)求所有生成树 3. 邻接矩阵A(D), 相邻矩阵A(G) 4. 用A的幂求不同长度通路(回路)总数 5. 可达矩阵P(D), 连通矩阵P(G) 6. 单源最短路径问题, Dijkstra算法
有向图关联矩阵 设D=是无环有向图,={v1,2,n E={e1,e2…,em} 关联矩阵〔 incidence matr×): MD=[m l 1,V是e的起点 0,v与e不关联 1,V是e的终点 《集合论与图论》第22讲
《集合论与图论》第22讲 2 有向图关联矩阵 设D=是无环有向图,V={v1,v2,…,vn}, E={e1,e2,…,em} 关联矩阵(incidence matrix): M(D)=[mij]n×m, 1, vi是ej的起点 mij = 0, vi与ej不关联 -1, vi是ej的终点
有向图关联矩阵(例) e MD 00-1-1 《集合论与图论》第22讲
《集合论与图论》第22讲 3 有向图关联矩阵(例) ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ − − − − − − = 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0 0 ( ) 1 2 3 4 5 6 4 3 2 1 e e e e e e v v v v M D v1 v2 v4 v3 e1 e2 e3 e5 e4 e6
有向图关联矩阵(性质) 每列和为零:∑=m=0 每行绝对值和为d(V):dW)=∑m:m,其中 1的个数为d(0),1的个数为d() 握手定理:∑n=1Σm=1m=0 平行边:相同两列 (D) 00-1-11-1 《集合论与图论》第22讲
《集合论与图论》第22 讲 4 有向图关联矩阵 (性质 ) 每列和为零: Σ n i=1 mij=0 每行绝对值和为d(v): d(vi)= Σ m j=1 mij, 其中 1的个数为 d +(v), -1的个数为 d -(v) 握手定理: Σ n i=1 Σ m j=1 mij=0 平行边: 相同两列 ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − − − = 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0 0 ( ) 1 2 3 4 5 6 4 3 2 1 e e e e e e v v v v M D
无向图关联矩阵 设G=是无环无向图,V{v1V2,w E={e1,e2…,em} 关联矩阵〔 incidence matrix) M(G)=[muI 1,v与e关联 0,v不与e关联 《集合论与图论》第22讲
《集合论与图论》第22讲 5 无向图关联矩阵 设G=是无环无向图,V={v1,v2,…,vn}, E={e1,e2,…,em} 关联矩阵(incidence matrix): M(G)=[mij]n×m, 1, vi与ej关联 mij = 0, vi不与ej关联
无向图关联矩阵(例) 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{v1V2,w E={e1,e2…,em} 参考点:任意1个顶点 秦基本关联矩阵( fundamental incidence matx:从M(G)删除参考点对应的行,记 作MG) 《集合论与图论》第22讲
《集合论与图论》第22讲 9 无向图基本关联矩阵 设G=是无环无向图,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. #