离散数学 图论-矩阵表示.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,图,的矩阵表示,14.4,图的,矩阵表示,图可用集合或图形表示，也可用矩阵表示，便于用代数方法研究图的性质。,用,矩阵表示图之前，必须将图的顶点或边,标定顺序,，使其成为标定图,1,、无向图的,关联矩阵,1,）,定义：设,无向图,G,，,V,v,1,v,2,，,v,n,。,E=e,1,e,2,e,3,，,e,m,令,m,ij,为顶点,v,i,与边,e,j,的关联次数,，则称,(m,ij,),nxm,为,G,的关联矩阵，记作,M(G),2,）性质,:,关联矩阵,是,n,行（结点数）,m,列（边数）,的矩阵,3,）,M(G),每列元素之和均为,2,，这正说明每条边关联两个顶点,(,环所关联的两个端点重合,),i,m,ij,=2,(,j=1,，,2,，,，,m),4,）,M(G),第,i,行元素之和为结点,vi,的,度数,，,j,m,ij,=,d(vi)(i,=1,，,2,，,，,n),5,),所有行的和（即矩阵所有元素之和）等于边数的,2,倍,d(vi),m,ij,2m,，,（即各顶点的度数之和等于边数的,2,倍）,6,）第,j,列与第,k,列相同，当且仅当边,ej,与,ek,是平行边,7,）,j,m,ij,=0,第,i,行,元素,和,为,0,当且仅当,vi,是,孤立点,2 1 1 1 0,M(G)=0 1 1 0 0,0 0 0 1 1,0 0 0 0 1,v4,v1,v2,v3,e1,e2,e3,e4,e5,2,、有向图的,关联矩阵,1),定义：,设有向图,D,中无环，,V,v,1,，,v,2,，,，,v,n,E,e,l,，,e,2,，,e,m,，,令,1 v,i,为边,e,j,的,起点,(,始点,),m,ij,=,0 v,i,为边,e,j,不关联,1 v,i,为边,e,j,的,终点,则,称,(m,ij,),nxm,，为,D,的关联矩阵，记作,M(D,）,2),有向图关联矩阵的性质,(,1),每列恰好一个,+1,和一个,-1,；,j,m,ij,=0,，,j,1,，,2,，,，,m,，从而,m,ij,=0,这说明,M(D),中所有元素之和为,0,(2)M(D),中，负,1,的个数等于正,1,的个数，都等于边数,m,，这正是有向图握手定理的内容（入度之和等于出度之和）,(3)第i,行中，正,1,的个数等于,d,+,(v,i,),（结点的出度），负,1,的个数等于,d,-,(v,i,),（结点的,入度,）,（,4,）平行边所对应的列相同,e5,v1,v2,v3,e1,e2,e3,e4,v4,-1,1,0 0 0,M(D)=1,-1 1,0 0,0 0 0,1 1,0 0,-1,-,1,-1,3,、有向图的,邻接矩阵,1,）定义：设有向图,D,，,V,v,1,，,v,2,，,，,v,n,，,E,e,1,，,e,2,，,，,e,m,令：,a,ij,为顶点,v,i,邻接到顶点,v,j,边的条数,称,(,a,ij,),nxn,为,D,的邻接矩阵，记作,A(D),，,或简记为,A,2,）邻接矩阵的性质,（,1,）,每列元素之和,为结点的,入度,，,即,j,a,ij,=,d,-,(,v,i,),，,i=1,，,2,，,，,n,所有,列的和,a,ij,d,-,(v,i,),m,，,等于边数,每,行元素之和,为结点的,出度,，所有行的和也等于边数,（,2,）邻接矩阵中元素,a,ij,反映了有向图中结点,v,i,到,v,j,通路长度为,1,的条数,（,3,）,A(D),中所有元素之和为,D,中长度为,1,的（边）通路总条数,。,主,对角线的元素值为图中结点,v,i,长度为,1,的,环的条,数。,利用,A(D),确定,D,中长度为,L,的通路数和回路数,就需要用到邻接矩阵的幂次,运算,（,4,）,A,2,中的元素值,b,ij,是结点,v,i,到,v,j,长度为,2,的通路条,数,;,说明：由矩阵的乘积定义,b,ij,=,k,a,ik,*a,kj,由此可推断，,A,3,矩阵中,的,c,ij,元素值，表示从,v,i,到,v,j,到长度恰为,3,的,通路,数,;,（,5,）定理,14,11,设,A,为有向图,D,的邻接矩阵，,V,v,1,，,v,2,，,，,v,n,为,D,的顶点集，,则,A,的,L,次幂,A,L,(L1),中元素,c,ij,为,D,中,v,i,到,v,j,长度为,L,的通路数,，,其中,c,ii,为,v,i,到自身长度为,L,的回路,数,c,ij,(,所有元素之和,),为,D,中长度为,L,的,通路总数,，,其中,c,ii,为,D,中长度为,L,的,回路总数,推论,:,设,B,L,A+A,2,十,+A,L,(L1),，,则,B,L,中元素,b,ij,为,D,中,从,v,i,到,v,j,长度小于或等于,L,的,通路数,，,其中主对角线上元素值为,D,中长度小于或等于,L,的,回路,数,。,4,、有向图的可达矩阵,1,）定义：设,D,为有向图,V,v,1,，,v,2,，,，,v,n,令,1,vi,可达,vj,p,ij,0,否则,称,(p,ij,),nxn,为,D,的,可达矩阵,，记作,P(D),，简记为,P,2,）可达矩阵的性质,（,1,）主对角线元素均为,1,（每个结点自身可达）,（,2,）,可通过图的邻接矩阵,A,的,n-1,次,幂,A,n-1,得到,（,将其非零元素换为,1,，主对角线元素均设为,1,即可）,例：给定有向图,D,，,4,个顶点,7,条边,邻接矩阵为,0 1 0 0,A=0 0 1 1,1 1 0 1,1 0 0 0,4*4矩阵中有,7,个,1,（边）,0 0 1 1,A,2,=2 1 0 1,1 1 1 1,0 1 0 0,反映图中任意两个顶点间,有多少,长度为,2,的通路,2 1 0 1,A,3,=1 2 1 1,2 2 1 2,0 0 1 1,反映图中任意两个顶点间,有多少,长度为,3,的通路,1 2 1 1,A,4,=2 2 2 3,3 3 2 3,2 1 0 1,反映图中任意两个顶点间,有多少,长度为,4,的通路,返回,3,4 2 3,B,4,=5 5 4 6,7 7 4 7,3 2 1 2,反映图中任意两个顶点,间有,多少,长度为小于等于,4,的通路,返回,返回,1)确定该有向图的邻接矩阵A（D）,2)D中v2到v4长度为1，2，3，4的通路分别,为,条,3,)v,4到自身长度为1，2，3，4的回路分别为,条,.,4)D中v3到v4长度小于或等于4的通路有,条,.,5)D中v1到v4长度小于或等于4的通路有,条,.,返回,小结,无向图的关联矩阵,有向图的关联矩阵,有向图的邻接矩阵,幂,运算求长度,L,的通路数,有向图的可达矩阵,邻接矩阵,A,的,n-1,次幂,A,n-1,得到,