离散数学 图的矩阵表示.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,7.3,图的矩阵表示,无向图的关联矩阵,有向图的关联矩阵,有向图的邻接矩阵,有向图的可达矩阵,1,无向图的关联矩阵,定义,设无向图,G,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,令,m,ij,为,v,i,与,e,j,的关联次数，称,(,m,ij,),n,m,为,G,的关联矩阵,，记为,M,(,G,).,2,例,:,求下图,G,的关联矩阵,上图,G,的关联矩阵,:,3,无向图的关联矩阵,性质：,（,5,）当且仅当,v,i,为孤立点。,4,有向图的关联矩阵,定义,设无环有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,令,则称,(,m,ij,),n,m,为,D,的关联矩阵,，记为,M,(,D,).,5,例,:,求图,G,的关联矩阵。,上图,G,的关联矩阵,:,6,有向图的关联矩阵,(,续,),性质,(4),平行边对应的列相同,7,定义,设有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,令 为顶点,v,i,邻接到顶点,v,j,边的条数，称,(),m,n,为,D,的邻接矩阵,记作,A,(,D,),简记为,A,.,有向图的邻接矩阵,8,求下图,G,的邻接矩阵,。,解,上图,G,的邻接矩阵。,给出了图,G,的邻接矩阵，就等于给出了图,G,的全部,信息。图的性质可以由矩阵,A,通过运算而获得,。,9,定义,设有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,令 为顶点,v,i,邻接到顶点,v,j,边的条数，称,(),m,n,为,D,的邻接矩阵,记作,A,(,D,),简记为,A,.,性质,有向图的邻接矩阵,10,D,中的通路及回路数,定理,设,A,为,n,阶有向图,D,的邻接矩阵,则,A,l,(,l,1),中,元素,为,D,中,v,i,到,v,j,长度为,l,的通路数，,为,v,i,到自身长度为,l,的回路数，,为,D,中长度为,l,的通路总数，,为,D,中长度为,l,的回路总数,.,11,D,中的通路及回路数,(,续,),例 有向图,D,如图所示,求,A,A,2,A,3,A,4,并回答诸问题：,(1),D,中长度为,1,2,3,4,的通路各有多,少条？其中回路分别为多少条？,(2),D,中长度小于或等于,4,的通路为多,少条？其中有多少条回路？,推论,设,B,l,=,A,+,A,2,+,A,l,(,l,1),则,B,l,中元素,为,D,中长度小于或等于,l,的通路数，,为,D,中长度小于或等于,l,的回路数,.,12,例,(续),长度 通路 回路,合计,50 8,1,8 1,2,11 3,3,14 1,4,17 3,13,在下图中,v,1,到,v,3,长度为,12,、,3,、,4,的通路分别有多少条，,G,中共有长度为,4,的通路多少条，其中回路多少条，长度小于等于,4,的通路共有多少条，其中回路多少条。,14,解,:,因为,15,所以，由,v,1,到,v,3,长度为,1,、,2,、,3,、,4,的通路分别有,0,、,2,、,2,、,4,条，,G,中共有长度为,4,的通路,43,条，其中回路,11,条，长度小于等于,4,的通路共有,87,条，其中回路,22,条。,注 无向图也有相应的邻接矩阵，一般只考虑简单图，无向图的邻接矩阵是对称的，其性质基本与有向图邻接矩阵的性质相同。,16,例如,:,下图邻接矩阵为：,17,有向图的可达矩阵,称,(,p,ij,),n,n,为,D,的可达矩阵,记作,P,(,D,),简记为,P,.,性质,:,P,(,D,),主对角线上的元素全为,1.,D,强连通当且仅当,P,(,D,),的元素全为,1.,定义,设,D,=,为有向图,V,=,v,1,v,2,v,n,令,18,有向图的可达矩阵,(,续,),例 右图所示的有向图,D,的可达矩阵为,19,设,G,=,V,E,是,n,阶简单有向图，,V,=,v,1,v,2,v,n,，由可达性矩阵的定义知，当,i,j,时，如果,v,i,到,v,j,有路，则,p,ij,=1,；,如果,v,i,到,v,j,无通路，则,p,ij,=0,；,又如果,v,i,到,v,j,有通路，则必存在长度小于等于,n,1,的通路。,又,n,阶图中，任何回路的长度不大于,n,，如下计算图,G,的可达性矩阵,P,：,B,=,E,+,A,+,A,2,+,A,n,-1,=(,b,ij,),n,n,其中,E,是单位矩阵。则,20,图,9.24,邻接矩阵,A,和,A,2,，,A,3,，,A,4,如下：,21,22,则图,G,的可达性矩阵,B,=,A,0,A,A,2,A,3,A,4,=,P,=,23,可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。,24,定义,设,G,=,V,E,是简单无向图，,V,=,v,1,v,2,v,n,P,(,G,)=(,p,ij,),n,n,其中：,i,j,=1,n,称,P,(,G,),为,G,的连通矩阵。简记为,P,。,无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。,25,