离散数学-图的矩阵表示省名师优质课获奖课件市赛课一等奖课件.pptVIP

图矩阵表示第1页

1.邻接矩阵：设G=V,E是一个简单图，是Gn个结点，则n阶方阵A(G)=(aij)称为G邻接矩阵。其中：adj表是邻接，nadj表示不邻接。v3v4v5v2v1?简单图是无向图，邻接矩阵是对称；简单图是有向图时，邻接矩阵不一定对称。对于给定集合A上关系R，能够用有向图来表示，而对于关系图，又能够用一个矩阵表示，所以对于普通形式图，也给出其矩阵表示。第2页

在邻接矩阵A中，第i行中值为1元素个数等于vi出度；第j列中值为1元素个数等于vj入度。零矩阵对应零图；(仅有孤立结点组成图称为零图)设有向图G结点集合，它邻接矩阵为，现在我们想计算从结点到结点长度为2路数目????分析：从到长度为2路，中间必须经过假如图G中有路存在，则必定有，反之假如图G中不存在路，那么或者，即于是从结点到长度为2路数目就等于：????????????第3页

按照矩阵乘法规则，上式恰好等于矩阵中第i行，第j列元素，即；表示从到长度为2路数目??????第4页

定理：A(G)是图G邻接矩阵，则(A(G))l中i行，j列元素aij(l)等于G中联结vi与vj长度为l路数目。证实：用数学归纳法当l=2时，由上面证实知显然成立假设命题对l成立，只需证实当l=l+1时也成马上可由所以??在实际问题中，常需要考虑到结点之间是否存在路问题。能够经过计算A,A2,...,An,...，当发觉某个Al第i行,第j列不为0，就表明vi到vj可达。由前面定理7-2.1推论可知，假如在vi到vj之间存在路，必定存在一条长度不超出n通路，所以l只需计算到n就能够了。第5页

推论：G有n个结点，A是邻接矩阵，，bij为Bni行，j列元素，若bij0，则表明vi，vj中存在路。对于简单有向图任意两个结点之间可达性，也能够用矩阵表示出来，即可达性矩阵2、可达性矩阵：G=V,E是简单有向图，|V|=n，定义nxn矩阵P=(pij)为可达性矩阵，其中将Bn中不为零元素值改为1，就可得到可达性矩阵P。第6页

例1：设图G邻接矩阵为，求G可达性矩阵。解：对于无向图，邻接矩阵是一个对称矩阵，其可达性矩阵也是对称。第7页

上面我们介绍了图邻接矩阵表示和可达性矩阵表示，可知这两种表示方法都是跟结点相关。还能够给出结点和边关联矩阵，在给出点和边关联关系时，假定图中无自回路。下面给出完全关联矩阵概念。（a）G为无向图设为G结点集，为G边集，称矩阵M(G)=(mij)为完全关联矩阵，其中：3、完全关联矩阵：v4v1v2v3e1e2e3e4e5e6v5完全关联矩阵为：e1e2e3e4e5e610011111000001101000110000000v1v2v3v4v5例：第8页

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