离散数学PPT课件3图的矩阵表示.ppt

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.,图的矩阵表示,图的矩阵表示不仅是给出图的一种表示方法,还可以通过,这些矩阵讨论有关图的若干性质,更重要的是可以用矩阵,形式将图存入计算机中,在计算机中对图作处理,.,这里主要讨论图的三种矩阵,.,一,.,邻接矩阵,这是以结点与结点之间的邻接关系确定的矩阵,.,1.,定义,:,设,G=,是个简单图,V=v,1,v,2,v,3,v,n,一个,nn,阶矩阵,A=(,a,ij,),称为,G,的邻接矩阵.其中:,a,ij,=,1 v,i,与,v,j,邻接,即(,v,i,v,j,)E,或 E,0,否则,例如,给定无向图,G,1,和有向图,G,2,如图所示,:,2.,从邻接矩阵看图的性质,:,无向图,:,每行,1,的个数,=,每列,1,的个数,=,对应结点的度,有向图,:,每,行,1,的个数,=,对应结点的,出度,每,列,1,的个数,=,对应结点的,入度,v,1,v,5,v,4,v,2,v,3,G,1,v,3,v,2,v,4,v,5,v,1,G,2,3.,邻接矩阵的乘积,在,(A(G,1,),2,中,a,34,2,=2,表示从,v,3,到,v,4,有长度为,2,的路有,2,条,:,在,(A(G,1,),3,中,a,23,3,=6,表示从,v,2,到,v,3,有长度为,3,的路有,6,条,:,v,2,v,1v,2,v,3,v,2,v,4,v,2,v,3,v,2,v,3,v,2,v,3,v,2,v,3,v,1,v,3,v,2,v,3,v,5,v,3,v,2,v,4,v,5,v,3,.,v,1,v,5,v,4,v,2,v,3,G,1,v,3,v,2,v,4,v,3,v,5,v,4,定理,8-3.1,设,G=,是简单图,令,V=v,1,v,2,v,3,v,n,G,的,邻接矩阵,(A(G),k,中的第,i,行第,j,列元素,a,ij,k,=m,表示在图,G,中从,v,i,到,v,j,长度为,k,的路有,m,条.,可以用归纳法证明,.,在实际应用中,有时只关心从一个结点到另一个结点是否,有路,而不关心路有多长,比如电话网络,.,这就促使我们定,义可达矩阵,.,二,.,可达性矩阵,1.,定义,:,设,G=,是个简单图,V=v,1,v,2,v,3,v,n,一个,nn,阶矩阵,P=(,p,ij,),称为,G,的可达性矩阵.其中:,p,ij,=,1 v,i,到,v,j,可达,(至少有一条路),0,否则,2.,求可达矩阵,可以根据邻接矩阵,A,求可达矩阵,.,设,|V(G)|=n,令,A,(k),是将,A,k,中的非0元素都写成1,而得到的只含有0和,1的0-1矩阵.于是可达矩阵,P,为:,P=AA,(2),A,(3),.A,(n),其中,是逻辑或,.,有两种方法求,P,方法,1.,按照矩阵相乘分别求出,A,(k),(k2),然后再,.,方法,2.,用求传递闭包的,Warshall,算法,请自行查询,.,例,如,G,2,如图所示,求它的,可达矩阵,P.,v,3,v,2,v,4,v,5,v,1,G,2,P=AA,(2),A,(3),A,(4),A,(5),3*.,用可达矩阵求强分图.,以,G,2,为例,从图看出有两个强分图,:v,1,v,3,和,v,2,v,4,v,5,下面看怎样用,P,求强分图,.,00100,00010,10010,01001,00010,A=,10010,01011,01101,00010,01001,A,(2),=,01101,01011,10010,01000,00010,A,(3),=,10010,01011,01101,00010,01001,A,(4),=,=A,(2),A,(5),=A,(3),11111,01011,11111,01011,01011,P=,v,3,v,2,v,4,v,5,v,1,G,2,先将,P=(,p,ij,),转置得,P,T,=(,p,T,ij,),如果,v,i,与,v,j,相互可达,则,p,ij,=,p,T,ij,=1,对,PP,T,进行初等变换,第,2,行与第,3,行交换,再第,2,列与第,3,列交换,最后得两个强分图,:v,1,v,3,和,v,2,v,4,v,5,三,.,完全关联矩阵,此矩阵是按照,结点,与,边,之间的关联关系确定的矩阵,.,1.,无向图的完全关联矩阵,11111,01011,11111,01011,01011,P=,10100,11111,10100,11111,11111,P,T,=,P,P,T,=,10100,01011,10100,01011,01011,11,000,11,000,00,111,00,111,00,111,初等,变换,得,v,1,v,3,v,2,v,4,v,5,1.,无向图的完全关联矩阵,1).,定义,:,设,G=,是个无向图,V=v,1,v,2,v,3,v,m,E=e,1,e,2,e,3,e,n,一个,mn,阶矩阵,M=(,m,ij,),称为,G,的完全,关联矩阵.其中:,2).,从关联矩阵看图的性质,:,a),每列只有二个1.,(因为每条边只关联两个结点),b),每行中1的个数为对应结点,的度数.,c),如果两列相同,则说明对应的,两条边是平行边.,m,ij,=,1 v,i,与,e,j,关联,0,否则,v,1,v,5,v,4,v,2,v,3,e,1,e,2,e,3,e,5,e,7,e,6,e,4,e,1,e,2,e,3,e,4,e,5,e,6,e,7,v,1,1 1 0 0 0 0 0,v,2,1 0 1 1 1 0 0,v,3,0 1 1 1 0 1 0,v,4,0 0 0 0 1 0 1,v,5,0 0 0 0 0 1 1,M=,2.,有向图的完全关联矩阵,1).,定义,:,设,G=,是个简单有向图,V=v,1,v,2,v,3,v,m,E=e,1,e,2,e,3,e,n,一个,mn,阶矩阵,M=(,m,ij,),称为,G,的完全,关联矩阵.其中:,2).,从关联矩阵看图的性质,:,a),每列只有一个1和一个-1.,(每条边有一个起点一个终点),b),每行中1的个数为对应结点,的出度.-1个数是结点入度,m,ij,=,1,v,i,是,e,j,的起点,-1,v,i,是,e,j,的终点,0,v,i,与,e,j,不关联,e,1,e,2,e,3,e,4,e,5,e,6,e,7,v,1,-1 1 0 0 0 0 0,v,2,1 0-1 0-1 0 0,v,3,0-1 1-1 0-10,v,4,0 0 0 1 1 0 1,v,5,0 0 0 0 0 1-1,M=,v,1,v,5,v,4,v,2,v,3,e,1,e,2,e,3,e,5,e,7,e,6,e,4,本节重点掌握,:,图的三个矩阵的求法,由图的矩阵,看图的性质,.,