《8.3图的矩阵表示.ppt》由会员分享,可在线阅读,更多相关《8.3图的矩阵表示.ppt(23页珍藏版)》请在三一办公上搜索。
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的边的重数。,几个特殊图的邻接矩阵,邻接矩阵的图论意义,设A为无向简单图G的邻
3、接矩阵,其第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个点,都是从i,j引出的有向边的公共交点。特别
4、地,bii是第i结点的出度。对偶地可讨论ATA的元素的图论意义。,i,j,练习:求AAT,ATA,并由此求每个结点的出度与入度,练习:求AAT,ATA,并由此求每个结点的出度与入度,定理1 设简单有向图G=的邻接矩阵为A,则矩阵A(k)中的第i行第j列元素等于G中从vi到vj长度为k的不同路径的数目。,例 A(2)中的第2行第1列元素等于2,说明从v2到v1长度为2的路的有两条:v2 v4 v1,v2 v3 v1。,分析:a21(2)=a21a11+a22a21+a23a31+a24a41=00+00+11+11=2注意从v2到v1长度为2的路中间必经由一个结点vk,即v2 vk v1(1k4
5、)。一般地,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不可达,分属不同强分图。bij 0(i=j)表示经vi存在回路,否则表示不存在经vi的回路。,例2 根据有向图
6、和矩阵B5,验证(a)b52=0,所以v2和v5分属两个强分图。(b)b11=0,所以没有经过v1的回路。(c)b53=3,所以从v5到v3长度不超过5的路径有3条。,v1,v1,v1,2、可达性矩阵,定义2 设G=为简单有向图,V=v1,v2,vn,定义矩阵 P=(pij),其中,有向图G中从vi到vj是否有路可达可通过矩阵运算而得到。,P称为图G的可达性矩阵。,方法 利用矩阵Bn(Bn-1)确定P:当bij=0时,pij=0;否则,pij=1。方法 直接由邻接矩阵确定可达矩阵:P=AA2An,其中Ak为A的布尔方幂。,方法1:先由邻接矩阵A求B4,B4=A+A(2)+A(3)+A(4)然后
7、写出可达矩阵P。,计算可达矩阵举例:,方法2:将A、A(2)、A(3)、A(4)转换为布尔矩阵A、A2、A3、A4 则 P=AA2A3A4。,例3 求例2的图的可达性矩阵,v1,3.可达矩阵的应用,利用一个图的可达性矩阵,求出这个图的所有强分图。方法:图G的强分图可从矩阵PPT求得可求得G的强连通分支对应结点集为:1,2,3,4,5。,4 关联矩阵,定义3 设G=是无向图,V=v1,v2,vn,E=e1,e2,en,一个nm矩阵M=(mij)称为G的关联矩阵,其中mij是结点vi和ej的关联次数。定义4 设G=是有向简单图,V=v1,v2,vn,E=e1,e2,en,一个nm矩阵M=(mij)称为G的关联矩阵,其中,5、课堂练习,练习 求如下有向图的邻接矩阵A,指出从v1到v4且长度为2和4的路。,解:从v1到v4长度为2的路有1条:v1v2v4 从v1到v4长度为4的路有3条:v1v2v4v2v4,v1v2v3v2v4,v1v4v2v3v4,作业,P284 1P285 3(+关联矩阵),
链接地址:https://www.31ppt.com/p-5881147.html