第10章图的矩阵表示.ppt

? Peking University 3-2 第10章 图的矩阵表示 10.1 关联矩阵 10.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的终点 总结 1. 关联矩阵M(D), M(G) 2. 用基本联矩阵Mf(G)求所有生成树 3. 邻接矩阵A(D), 相邻矩阵A(G) 4. 用A的幂及幂和求不同长度通路(回路)总数 5. 可达矩阵P(D), 连通矩阵P(G) 作业 P163: 2, 3, 4 连通矩阵 设G=V,E是无向简单图,V={v1,v2,…,vn}, 连通矩阵: P(G)=[pij]n?n, 1, 若vi与vj连通 pij = 0, 若vi与vj不连通 连通矩阵(性质) 主对角线元素都是1: ?vi?V, vi与vi连通 连通图: 所有元素都是1 伪对角阵: 对角块是连通分支的连通矩阵 设Br=A+A2+…+Ar= [b(r)ij]n?n, 则?i?j, pij=1 ? b(n-1)ij 0 连通矩阵(例) v1 v4 v3 v2 v6 v5 * * D与M(D)是相互唯一确定的 有向图关联矩阵(例) v1 v2 v4 v3 e1 e2 e3 e5 e4 e6 有向图关联矩阵(性质) 每列和为零: ?ni=1mij=0(每条边关联两个顶点) 每行绝对值和为d(vi): d(vi)=?mj=1mij, 其中1的个数为d+(v), -1的个数为d-(v) 握手定理: ?ni=1?mj=1mij=0(各顶点入度之和等于出度之和) 平行边: 相同两列 无向图关联矩阵 设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关联 G与M(G)是相互唯一确定的 无向图关联矩阵(例) v1 v2 v4 v3 e1 e2 e3 e4 e6 e5 无向图关联矩阵(性质) 每列和为2: ?ni=1mij=2 ( ?ni=1?mj=1mij=2m ) 每行和为d(v): d(vi)=?mj=1mij 每行所有1对应的边构成断集: [{vi}, {vi}] 平行边: 相同两列 伪对角阵: k个连通分支,对角块是连通分支 无向图基本关联矩阵 设G=V,E是无环无向图, V={v1,v2,…,vn}, E={e1,e2,…,em} 参考点: 任意1个顶点 基本关联矩阵(fundamental incidence matrix): 从M(G)删除参考点对应的行, 记作Mf(G) 无向图关联矩阵的秩 定理10.1: n阶无向连通图G 的关联矩阵的秩r(M(G))=n-1 (F={0,1}) 无向图基本关联矩阵的秩 定理10.2: n阶无向连通图G的基本关联矩阵的秩r(Mf(G))=n-1. # 推论1: G有p个连通分支,则r(M(G))= r(Mf(G))=n-p, 其中Mf(G)是从M(G)的每个对角块中删除任意1行而得到的. # 推论2: G连通?r(M(G))=r(Mf(G))=n-1. # 基本关联矩阵与生成树 定理10.3: G连通, M’f是Mf(G)中任意n-1列组成的方阵, M’f中各列对应的边集是{ei1,ei2,…, ei(n-1)}, T是导出子图G[{ei1, ei2, …, ei(n-1)}], 则 T是G的生成树 ? M’f的行列式|M’f|?0 # 用关联矩阵求所有生成树 忽略环, 求关联矩阵 任选参考点, 求基本关联矩阵 求所有n-1阶子方阵,计算行列式,行列式非0的是生成树 求所有生成树(例) v1 v2 v4 v3 e1 e2 e3 e4 e6 e5 求所有生成树(例,续) v1 v2 v4 v3 e1 e2 e3 e4 e6 e5 求所有生成树(例,续) v1 v2 v4 v3 e1 e2 e3 e4 e6 e5 1 3,5,6 1 1,4,6 1 2,3,5 0 1,2,4 1 4,5,6 1 1,5,6 1