资源描述：
《《图的矩阵表示》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八章图论8.1图的基本概念8.2路径和回路8.3图的矩阵表示8.4二部图8.5平面图8.6树8.7有向树8.3图的矩阵表示1.邻接矩阵2.可达性矩阵3.可达性矩阵的应用4.关联矩阵1、邻接矩阵定义1设G=有向（无向）线图，有n个标定了次序的结点v1,v2,…vnV，则n阶方阵A=(aij)称为G的邻接矩阵，这里例1左下图的邻接矩阵：注①图的邻接矩阵与n个结点的标定次序有关，对于V中各元素不同的标定次序，可得出不同的邻接矩阵。不过这些矩阵可以通过交换行和列而相互得出。具有这样性质的矩阵称它们置换等价。例如，左下图的两个置换等价邻接矩阵：②有向简单图在标定次序后得到
2、唯一邻接矩阵;零图的邻接矩阵的元素全为0，称为零矩阵。完全图Kn的邻接矩阵是恰有n个0并全在对角线上的n阶(0,1)方阵。当有向线图代表关系，关系矩阵就是邻接矩阵。有向线图G=V,E的邻接矩阵是A，则G的逆图G~=V,E~的邻接矩阵是A的转置矩阵，记为AT。无向简单图的邻接矩阵是对称矩阵：A=AT。有n个结点的赋权图G=V,E,W的邻接矩阵是n阶方阵A=(aij)，其中当(vi,vj)E，aij=W(vi,vj)；否则,aij=0。有n个结点的多重图的邻接矩阵是n阶方阵A=(aij)，其中aij代表从vi到vj的边的重数。几个特殊图的邻接矩阵邻接矩阵的图论意义设
3、A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于结点的度。邻接矩阵的图论意义设A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于结点的度。设A为有向简单图G的邻接矩阵。①A的第i行(列)和等于第i个结点的出(入)度，i=1,…n。v3的出度=1+1+0+1=3，v3的入度=0+1+0+0=1邻接矩阵的图论意义设A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于结点的度。设A为有向简单图G的邻接矩阵。①A的第i行(列)和等于第i个结点的出(入)度，i=1,…n。②B=AAT=(bij)的元素bij=ai1aj1+…+ainajn=k表示有k个点，
4、都是从i,j引出的有向边的公共交点。特别地，bii是第i结点的出度。对偶地可讨论ATA的元素的图论意义。ij练习：求AAT，ATA，并由此求每个结点的出度与入度练习：求AAT，ATA，并由此求每个结点的出度与入度③定理1设简单有向图G=的邻接矩阵为A，则矩阵A(k)中的第i行第j列元素等于G中从vi到vj长度为k的不同路径的数目。例A(2)中的第2行第1列元素等于2，说明从v2到v1长度为2的路的有两条：v2v4v1，v2v3v1。分析:a21(2)=a21a11+a22a21+a23a31+a24a41=0•0+0•0+1•1+1•1=2注意从v2到v1长度为2的
5、路中间必经由一个结点vk,即v2vkv1(1k4)。一般地,A(m)中从i到j长为m的路径总数是aij(m)条，过i的长为m的回路共有aii(m)条。④Br=A+A(2)+A(3)+…+A(r)的元素bij表示从vi到vj长度小于等于r的不同路径总数。在n个结点的简单有向图中，基本路径长度不超过n-1，基本回路长度不超过n，故可用Bn-1=A+A(2)+A(3)+…+A(n-1)(ij时)Bn=A+A(2)+A(3)+…+A(n)(i=j时)研究vi到vj的可达性和经vi是否存在回路的问题。bij0(ij)表示从vi到vj可达，否则从vi到vj不可达，分属不同强
6、分图。bij0(i=j)表示经vi存在回路，否则表示不存在经vi的回路。例2根据有向图和矩阵B5，验证(a)b52=0，所以v2和v5分属两个强分图。(b)b11=0，所以没有经过v1的回路。(c)b53=3，所以从v5到v3长度不超过5的路径有3条。v1v1v12、可达性矩阵定义2设G=为简单有向图，V={v1,v2,…vn}，定义矩阵P=(pij)，其中有向图G中从vi到vj是否有路可达可通过矩阵运算而得到。P称为图G的可达性矩阵。方法①利用矩阵Bn（Bn-1）确定P：当bij=0时，pij=0；否则，pij=1。方法②直接由邻接矩阵确定可达矩阵：P=A∨A2
7、∨…∨An，其中Ak为A的布尔方幂。方法1：先由邻接矩阵A求B4，B4=A+A(2)+A(3)+A(4)然后写出可达矩阵P。计算可达矩阵举例：方法2：将A、A(2)、A(3)、A(4)转换为布尔矩阵A、A2、A3、A4则P=AA2A3A4。例3求例2的图的可达性矩阵v13.可达矩阵的应用利用一个图的可达性矩阵，求出这个图的所有强分图。方法：图G的强分图可从矩阵P∧PT求得可求得G的强连通分支对应结点集为：{1}，{2}，{3,4,5}。4关联矩阵定义3设G=是无向图，V={v1,v2…，
