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