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

《离散数学-图的矩阵表示.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的矩阵表示1.邻接矩阵：设G=是一个简单图，是G的n个结点，则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中：adj表是邻接，nadj表示不邻接。v3v4v5v2v1简单图是无向图，邻接矩阵是对称的；简单图是有向图时，邻接矩阵不一定对称。对于给定集合A上的关系R，可以用有向图来表示，而对于关系图，又可以用一个矩阵表示，所以对于一般形式的图，也给出其矩阵表示。在邻接矩阵A中，第i行中值为1的元素个数等于vi的出度；第j列中值为1的元素个数等于vj的入度。零矩阵对应零图；(仅有孤立结点组成的图称为零图)

2、设有向图G的结点集合，它的邻接矩阵为，现在我们想计算从结点到结点的长度为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

3、=l+1时也成立即可由所以在实际问题中，常需要考虑到结点之间是否存在路的问题。可以通过计算A,A2,...,An,...，当发现某个Al的第i行,第j列不为0，就表明vi到vj可达。由前面的定理7-2.1的推论可知，如果在vi到vj之间存在路，必定存在一条长度不超过n的通路，所以l只需计算到n就可以了。推论：G有n个结点，A是邻接矩阵，，bij为Bn的i行，j列元素，若bij>0，则表明vi，vj中存在路。对于简单有向图的任意两个结点之间的可达性，也可以用矩阵表示出来，即可达性矩阵2、可达性矩阵：G=是简

4、单有向图，

5、V

6、=n，定义nxn矩阵P=(pij)为可达性矩阵，其中将Bn中不为零的元素值改为1，就可得到可达性矩阵P。例1：设图G的邻接矩阵为，求G的可达性矩阵。解：对于无向图，邻接矩阵是一个对称矩阵，其可达性矩阵也是对称的。上面我们介绍了图的邻接矩阵表示和可达性矩阵表示，可知这两种表示方法都是跟结点相关的。还可以给出结点和边的关联矩阵，在给出点和边的关联关系时，假定图中无自回路。下面给出完全关联矩阵的概念。（a）G为无向图设为G的结点集，为G的边集，称矩阵M(G)=(mij)为完全关联矩阵，其中：3、完全关联矩

7、阵：v4v1v2v3e1e2e3e4e5e6v5完全关联矩阵为：e1e2e3e4e5e610011111000001101000110000000v1v2v3v4v5例：（1）M（G）中每一列中有且仅有两个1，对应图中每一边关联两个结点。（2）每一行中元素的和为对应结点的度数。（3）一行中若元素全为0，则其对应的结点为孤立结点。（4）平行边对应的列相同。（5）结点或边编序不同，对应完全关联矩阵只有行序、列序的差别。从关联矩阵中看出图形的一些性质：类似，给出有向图的完全关联矩阵的定义：（b）G为有向图G=，

8、，pXq阶矩阵M(G)=(mij)为G的完全关联矩阵，其中：v4v1v2v3e1e2e3e4e5e6v5e1e2e3e4e5e610011111000001101000110000000v1v2v3v4v5v2v5v1v3v4e1e2e3e4e5e7e6e1e2e3e4e5e6e7000111-11000000-1100-1000-1100-1000-1-100v1v2v3v4v5关联矩阵：有向图的完全关联矩阵也有类似于无向图的一些性质（1）M（G）中每一列中有且仅有两个1，对应图中每一边关联两个结点。（2）每一行

9、中元素的和为对应结点的度数。（3）一行中若元素全为0，则其对应的结点为孤立结点。（4）平行边对应的列相同。（5）结点或边编序不同，对应完全关联矩阵只有行序、列序的差别。（1）每一列中一个值为1，一个为-1，对应图中的一条有向边。（2）把一行中的值为1的元素相加，得到顶点的出度，把值为-1的元素相加，得到顶点的入度。（3）一行中元素全为0，对应孤立结点。（4）平行边对应的列相同。（5）结点或边编序不同，对应完全关联矩阵只有行序、列序的差别。例行相加运算：有向图：对应分量普通加法运算；无向图：对应分量模2加法运算。行相

10、加相当于G中对应结点的合并。，说明vi和vj中只有一个结点是边er的端点，合并后仍是er的端点。，有两种情况：a、vi，vj都不是er的端点；b、vi，vj都是er的端点，合并后删去自回路。若合并后完全关联矩阵中出现元素全为0的列，表明对应的边消失。有了这种运算，就可以运用这种运算求关联矩阵的秩矩阵的秩：矩阵中所有非零子式的最高阶数；就是将矩阵通过初等变换化