第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=<V,>是无环有向图,={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,E>是无环有向图,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,E>是无环无向图,V{v1V2,w E={e1,e2…,em} 关联矩阵〔 incidence matrix) M(G)=[muI 1,v与e关联 0,v不与e关联 《集合论与图论》第22讲
《集合论与图论》第22讲 5 无向图关联矩阵 设G=<V,E>是无环无向图,V={v1,v2,…,vn}, E={e1,e2,…,em} 关联矩阵(incidence matrix): M(G)=[mij]n×m, 1, vi与ej关联 mij = 0, vi不与ej关联