[数学]4图的矩阵表示.pptVIP

图的表示 一个图可以用数学定义来描述，也可以用图形表示；还可以用矩阵来表示图，这样便于用代数知识来研究图的性质，同时也便于用计算机处理。 图的矩阵表示 1. 关联矩阵M(D), M(G) 2. 邻接矩阵A(D), 邻接矩阵A(G) 3. 用A的幂求不同长度通路(回路)总数 4. 可达矩阵P(D), 连通矩阵P(G) 无向图关联矩阵 设G=V,E是无向图,V={v1,v2,…,vn}, E={e1,e2,…,em} 关联矩阵(incidence matrix): M(G)=[mij]n?m,(每个顶点确定一行,每条边确定一列), mij = vi与ej的关联次数 2, vi与ej关联，且ej是环 mij = 1, vi与ej关联，且ej不是环 0, vi不与ej关联 无向图关联矩阵(例) 无向图关联矩阵(性质) 每列和为2: ?ni=1mij=2 ( ?ni=1?mj=1mij=2m ) 每行和为d(v): d(vi)=?mj=1mij 孤立点:全0行 平行边: 相同两列 环：对应列中只有一个2其余是0 有向图关联矩阵 设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的终点 有向图关联矩阵(例) 有向图关联矩阵(性质) 每列和为零: ?ni=1mij=0 每行绝对值和为d(v): d(vi)=?mj=1mij, 其中1的个数为d+(v), -1的个数为d-(v) 握手定理: ?ni=1?mj=1mij=0 平行边: 相同两列 无向图邻接矩阵 设G=V,E是无向简单图,V={v1,v2,…,vn} 邻接矩阵(adjacence matrix): A(G)=[aij]n?n, aii=0, 1, vi与vj相邻,i?j aij = 0, vi与vj不相邻 无向图邻接矩阵(性质) A(G)对称: aij= aji 每行(列)和为顶点度: ?ni=1aij=d(vj) 握手定理: ?ni=1?nj=1aij=?ni=1d(vj)=2m Problem? 通路在矩阵中如何表现？ 关系图、关系矩阵 R?S = { x,y | ?z( xRz ? zSy ) } 邻接矩阵与通路数 设A(D)=A=[aij]n?n, Ar=Ar-1?A (r?2), Ar=[a(r)ij]n?n, 定理1: a(r)ij=从vi到vj长度为r的通路总数??ni=1?nj=1a(r)ij=长度为r的通路总数 ? ?ni=1a(r)ii=长度为r的回路总数. # 邻接矩阵与通路数 设Ar=Ar-1?A,(r?2), Ar=[a(r)ij]n?n, 推论1: a(2)ii=d(vi). # 推论2: G连通?距离d(vi,vj)=min{r|a(r)ij?0，i?j}. # 用邻接矩阵求通路数(例) 用邻接矩阵求通路数(例,续) v1到v2长度为4的通路数: 6 14142,14242,14232,12412, 14212,12142 v1到v3长度为4的通路数: 4 12423,12323,14123,12123 v1到v1长度为4的回路数: 7 14141,14241,14121,12121, 12421,12321,12141, 连通矩阵 只考虑有无，不考虑有多少条 设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 连通矩阵(例) 有向图邻接矩阵 设D=V,E是有向图,V={v1,v2,…