单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2014/12/1,#,图的矩阵表示,1.,邻接矩阵：,设,G=,是一个简单图，是,G,的,n,个结点,，,则,n,阶方阵,A(G)=(a,ij,),称为,G,的邻接矩阵。其中：,adj,表是邻接，,nadj,表示不邻接。,v,3,v,4,v,5,v2,v1,简单图是无向图，邻接矩阵是对称的；,简单图是有向图时，邻接矩阵不一定对称。,对于,给定,集合,A,上的关系,R,，可以用有向图来表示，而对于关,系图，又可以用一个矩阵表示，所以对于一般形式的图，也,给出其矩阵表示。,在邻接矩阵,A,中，第,i,行中值为,1,的元素个数等于,v,i,的出度；,第,j,列中值为,1,的元素个数等于,v,j,的入度。,零矩阵对应零图；,(,仅有孤立结点组成的图称为零图,),设有向图,G,的结点集合 ，它的邻接矩阵为,，,现在我们想计算从结点 到 结点 的长度为,2,的路的数目,分析：从 到 长度为,2,的路，中间必须经过 如果图,G,中有路 存在，则肯定有 ，反之如果图,G,中不存在路 ，那么 或者 ，即,于是从结点 到 的长度为,2,的路的数目就等于：,按照矩阵的乘法规则，上式恰好等于矩阵 中第,i,行，第,j,列的元素，即 ；,表示从 到 的长度为,2,的路的数目,定理：,A(G),是图,G,的邻接矩阵，则,(A(G),l,中的,i,行，,j,列元素,a,ij,(l),等于,G,中联结,v,i,与,v,j,的长度,为,l,的,路的数目。,证明：用数学归纳法,当,l=2,时，由上面证明知显然成立,假设命题对,l,成立,，,只需证明当,l=l+1,时也成立即可,由 所以,在实际问题中，常需要考虑到结点之间是否存在路的问题。,可以通过计算,A,A,2,.,A,n,.,，当发现某个,A,l,的第,i,行,第,j,列不为,0,，,就表明,v,i,到,v,j,可达。,由,前面的,定理,7-2.1,的,推论可知，如果在,v,i,到,v,j,之间存在路，必定存在,一,条长度不超过,n,的通路,，所以,l,只需计算到,n,就可以,了,。,推论：,G,有,n,个结点，,A,是邻接矩阵，,b,ij,为,B,n,的,i,行，,j,列元素，若,b,ij,0,，则表明,v,i,，,v,j,中存在路。,对于简单有向图的任意两个结点之间的可达性，也可以用矩阵,表示出来，即可达性矩阵,2,、,可达性矩阵：,G=,是简单有向图，,|V|=n,，定义,nxn,矩阵,P=(p,ij,),为可达性矩阵，其中,将,B,n,中不为零的元素值改为,1,，就可得到可达性矩阵,P,。,例,1,：,设图,G,的邻接矩阵为 ，求,G,的可达性矩阵。,解：,对于无向图，邻接矩阵是一个对称矩阵，其可达性矩阵也是对称的。,上面我们介绍了图的邻接矩阵表示和可达性矩阵表示，可知,这两种表示方法都是跟结点相关的。,还可以给出结点和边的关联矩阵，在给出点和边的关联关系,时，假定图中无自回路。下面给出完全关联矩阵的概念。,（,a,）,G,为无向图 设,为,G,的结点集，,为,G,的边集，称矩阵,M(G)=(m,ij,),为,完全,关联矩阵,，其中：,3,、,完全关联矩阵：,v,4,v,1,v,2,v,3,e,1,e,2,e,3,e,4,e,5,e,6,v,5,完全关联矩阵为：,e,1,e,2,e,3,e,4,e,5,e,6,1 0 0 1 1,1 1 1 0 0 0,0 0 1 1 0 1,0 0 0 1 1 0,0 0 0 0 0 0,v,1,v,2,v,3,v,4,v,5,例：,（,1,）,M,（,G,）中每一列中有且仅有两个,1,，对应图中每一边关联两,个结点。,（,2,）每一行中元素的和为对应结点的度数。,（,3,）一行中若元素全为,0,，则其对应的结点为孤立结点,。,（,4,）平行边对应的列相同。,（,5,）结点或边编序不同，对应完全关联矩阵只有行序、列序的,差别。,从关联矩阵中看出图形的一些性质,：,类似，给出有向图的完全关联矩阵的定义：,（,b,）,G,为有向图,G=,，,p,X,q,阶矩阵,M(G)=(m,ij,),为,G,的完全关联矩阵，其中：,v,4,v,1,v,2,v,3,e,1,e,2,e,3,e,4,e,5,e,6,v,5,e,1,e,2,e,3,e,4,e,5,e,6,1 0 0 1 1,1 1 1 0 0 0,0 0 1 1 0 1,0 0 0 1 1 0,0 0 0 0 0 0,v,1,v,2,v,3,v,4,v,5,v,2,v,5,v,1,v,3,v,4,e,1,e,2,e,3,e,4,e,5,e,7,e,6,e,1,e,2,e,3,e,4,e,5,e,6,e,7,0 0 0 1 1 1,-1 1 0 0 0 0 0,0 -1 1 0 0 -1 0,0 0 -1 1 0 0 -1,0 0 0 -1 -1 0 0,v,1,v,2,v,3,v,4,v,5,关联矩阵：,有向图的完全 关联矩阵也有类似于无向图的一些性质,（,1,）,M,（,G,）中每一列中有且仅有两个,1,，对应图中每一边关联,两个,结点。,（,2,）每一行中元素的和为对应结点的度数。,（,3,）一行中若元素全为,0,，则其对应的结点为孤立结点,。,（,4,）平行边对应的列相同。,（,5,）结点或边编序不同，对应完全关联矩阵只有行序、列序的差别。,（,1,）每一列中一个值为,1,，一个为,-1,，对应图中的一条有向边。,（,2,）把一行中的值为,1,的元素相加，得到顶点的出度，把值为,-1,的元素相加，得到顶点的入度。,（,3,）一行中元素全为,0,，对应孤立结点。,（,4,）平行边对应的列相同。,（,5,）结点或边编序不同，对应完全关联矩阵只有行序、列序的差别。,例,行相加运算：,有向图：对应分量普通加法运算；,无向图：对应分量模,2,加法运算。,行相加相当于,G,中对应结点的合并。,，说明,v,i,和,v,j,中只有一个结点是边,e,r,的端点，合并,后仍是,e,r,的端点。,，有两种情况：,a,、,v,i,，,v,j,都不是,e,r,的端点；,b,、,v,i,，,v,j,都是,e,r,的端点，合并后删去自回路。,若合并后完全关联矩阵中出现元素全为,0,的列，表明对应的,边消失。,有了这种运算，就可以运用这种运算求关联矩阵的秩,矩阵的秩：矩阵中所有非零子式的最高阶数；就是将矩阵通过初等变换化为行阶梯后非零行的行数。,定理,：,G,为连通图，有,r,个结点，则其完全关联矩阵,M(G),的秩为,r-1,，即,rank M(G)=r-1,。,例：,计算右图对应的完全关联矩阵的秩。,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,5,e,4,e,6,e,7,推论：,G,有,r,个结点，,w,个极大连通子图，则图,G,的完全关联矩阵的秩为,r-w,。,可用之求图的最大连通子图数目。,谢谢,