《图的矩阵表》PPT课件.ppt

南京信息工程大学 离散数学教学组 制作离 散 数 学电 子 课 件第八章 图论8.1 图的基本概念8.2 路径和回路8.3 图的矩阵表示8.4 二部图8.5 平面图8.6 树8.7 有向树 8.3 图的矩阵表示1. 邻接矩阵2. 可达性矩阵3. 可达性矩阵的应用4. 关联矩阵1 1、、邻邻接矩阵接矩阵定义定义1 设设G=有向（无向）线图有向（无向）线图，有，有n个个标定了次序标定了次序的结的结点点v1, v2,…vn V，则，则n阶方阵阶方阵A=(aij)称为称为G的邻接矩阵，这里的邻接矩阵，这里例例1 左下图的左下图的邻接矩阵邻接矩阵：：注注①① 图的邻接矩阵与图的邻接矩阵与n个结点的个结点的标定次序有关标定次序有关，对于，对于V中各中各元素不同的标定次序，可得出不同的邻接矩阵不过这些矩元素不同的标定次序，可得出不同的邻接矩阵不过这些矩阵可以通过交换行和列而相互得出具有这样性质的矩阵称阵可以通过交换行和列而相互得出具有这样性质的矩阵称它们它们置换等价置换等价例如，左下图的两个例如，左下图的两个置换等价邻接矩阵置换等价邻接矩阵：：② ② 有向简单图在标定次序后得到唯一邻接矩阵有向简单图在标定次序后得到唯一邻接矩阵; ;•零图零图的邻接矩阵的元素全为的邻接矩阵的元素全为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的邻接矩阵，其的邻接矩阵，其第第i行行(列列)元素为元素为1的个数等于的个数等于结点的度。

结点的度邻接矩阵的邻接矩阵的图论意义图论意义设设A为为无向简单图无向简单图G的邻接矩阵，其的邻接矩阵，其第第i行行(列列)元素为元素为1的个数等于的个数等于结点的度结点的度设设A为为有向简单图有向简单图G的邻接矩阵的邻接矩阵①① A的的第第i行行(列列)和和等于第等于第i个结点的出个结点的出(入入)度度，，i=1,…nv3的出度的出度=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引出的有向边的引出的有向边的公共交点公共交点特别地，特别地，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的的路的有两条：路的有两条： v2 v4 v1 ，， v2 v3 v1 分析分析: a21(2)= a21a11+a22a21+ a23a31+a24a41=0•0+0•0+1•1+1•1=2注意从注意从v2到到v1长度为长度为2的路中间必经由一个结点的路中间必经由一个结点vk,即即v2 vk  v1(1 k 4)一般地一般地, 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) (i j时时)Bn=A+A(2)+A(3)+…+A(n) (i=j时时)研究研究vi到到vj的可达性和经的可达性和经vi是否存在回路的问题。

是否存在回路的问题bij 0(i j)表示表示从从vi到到vj可达，否则从可达，否则从vi到到vj不可达，分属不同强分图不可达，分属不同强分图bij  0(i=j)表表示经示经vi存在回路，否则表示不存在经存在回路，否则表示不存在经vi的回路例例2 根据有向图和矩阵根据有向图和矩阵B5，验证，验证(a) b52=0，所以，所以v2和和v5分属两个强分图分属两个强分图b) b11=0，所以没有经过，所以没有经过v1的回路 (c) b53=3，所以从，所以从v5到到v3长度长度不超过不超过5的路径有的路径有3条v1v1v12 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=A∨∨A2∨∨…∨∨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=A A2 A3 A4 例例3 求例求例2的图的可达性矩阵的图的可达性矩阵v13.3.可达矩阵的应用可达矩阵的应用利用一个图的可达性矩阵，利用一个图的可达性矩阵，求求出这个图的所有出这个图的所有强分图强分图方法：图方法：图G的强分图可从矩阵的强分图可从矩阵P∧∧PT求得求得可求得可求得G的的强连通分支强连通分支对应结点集为：对应结点集为： {1}，，{2}，，{3,4,5}4 关联矩阵定义定义3 设设G=是是无向图无向图，，V={v1,v2…，，vn}，，E={e1,e2…,en}，，一个一个n×m矩阵矩阵M=(mij)称为称为G的的关联矩阵关联矩阵，其中，其中mij是结点是结点vi和和ej的的关联次数。

关联次数定义定义4 设设G=是是有向简单图有向简单图，，V={v1,v2…，，vn}，，E={e1,e2…,en}，一个，一个n×m矩阵矩阵M=(mij)称为称为G的的关联矩阵关联矩阵，其中，其中5 5、课堂练习、课堂练习练练习习 求求如如下下有有向向图图的的邻邻接接矩矩阵阵A，，指指出出从从v1到到v4且且长长度度为为2和和4的路解：从从v1到到v4长度为长度为2的路有的路有1条：条： v1v2v4 从从v1到到v4长度为长度为4的路有的路有3条：条： v1v2v4v2v4，， v1v2v3v2v4，， v1v4v2v3v4作业P284 1P285 3(+关联矩阵关联矩阵) 。