图的矩阵表示精选PPT.ppt

《图的矩阵表示精选PPT.ppt》由会员分享，可在线阅读，更多相关《图的矩阵表示精选PPT.ppt（91页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关于图的矩阵表示第1页，讲稿共91张，创作于星期日电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程143-143-2 2图的矩阵表示图的矩阵表示 由由于于矩矩阵阵的的行行和和列列有有固固定定的的次次序序，因因此此在在用用矩矩阵阵表表示示图图时时，先先要要将将图图的的结结点点进进行行排排序序，若若不不具具体体说说明明排排序序，则则默默认认为为书书写写集集合合V V时时结结点点的顺序。的顺序。用图形表示图是图论的一种表示方法。它的优点是形象直观，但是这种表用图形表示图是图论的一种表示方法。它的优点是形象直观，但是这种表示在结点与边的数目很多时是不方便的。示在结点与边的数

2、目很多时是不方便的。在学习中常常需要分析图并在图上执行各种过程和算法，也许在学习中常常需要分析图并在图上执行各种过程和算法，也许必须用计算机来执行这些算法，因此必须把图的结点和边传输给计必须用计算机来执行这些算法，因此必须把图的结点和边传输给计算机，由于集合与图形都不适合计算机处理，所以要找到一种新的算机，由于集合与图形都不适合计算机处理，所以要找到一种新的表示图的方法，这就是图的矩阵表示。表示图的方法，这就是图的矩阵表示。利用这种方法，我们能把图用利用这种方法，我们能把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有关性质。矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有

3、关性质。第2页，讲稿共91张，创作于星期日第六章 图的矩阵表示一个图可以按定义描述出来，也可以用图形表示出来，还可以同二元关系一样，用矩阵来表示。图用矩阵表示有很多优点，既便于利用代表知识研究图的性质、构造算法，也便于计算机处理。图的矩阵表示常用的有两种形式：邻接矩阵和关联矩阵。邻接矩阵常用于研究图的各种道路的问题，关联矩阵常用于研究子图的问题。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，需将图的结点和边加以编号（定序），以确定与矩阵元素的对应关系。3第3页，讲稿共91张，创作于星期日 本章的教学内容本章的教学内容6.1 关联矩阵关联矩阵6.2 圈矩阵圈矩阵6.3 割集矩阵割集矩阵6.

4、5 图的邻接图的邻接矩阵矩阵 第4页，讲稿共91张，创作于星期日图的矩阵表示图的矩阵表示 计算机科学领域有许多算法涉及图。计算机存储计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。性质的有效工具和手段。第5页，讲稿共91张，创作于星期日6.1 6.1 无向图的完全关联矩阵无向图的完全关联矩阵无向图的完全

5、关联矩阵无向图的完全关联矩阵定义定义 给定无向图给定无向图G，令，令v1,v2,vp,e1,e2,eq分别记分别记为为M(G)的顶点和边，则矩阵的顶点和边，则矩阵M(G)=(mij)pq，其中，其中称称M(G)为图为图G的的完全关联矩阵。完全关联矩阵。第6页，讲稿共91张，创作于星期日例例 下图下图G的完全关联矩阵为：的完全关联矩阵为：v1v2v3v4v5e1e2e3e4第7页，讲稿共91张，创作于星期日实例实例实例实例1 1例例1 求下图的完全关联矩阵。求下图的完全关联矩阵。e1e2e3e4e5e6v1110011v2111000v3001101v4000110v5000000第8页，讲稿共

6、91张，创作于星期日无向图的完全关联矩阵有下列性质：无向图的完全关联矩阵有下列性质：（1）M(G)中每列恰有两个中每列恰有两个1，即每条边与两个顶点关联；，即每条边与两个顶点关联；（2）每一行元素之和等于对应顶点的度数；）每一行元素之和等于对应顶点的度数；（3）M(G)中元素之和等于中元素之和等于G中中顶顶点点的度数总和；的度数总和；（4）多重边对应的列相同；）多重边对应的列相同；（5）若）若G有有w w个连通分支个连通分支G1,G2,Gw w,则有准分块对角阵则有准分块对角阵第9页，讲稿共91张，创作于星期日e5e4e3e2e1e6v5v1v4v3v2第10页，讲稿共91张，创作于星期日一个

7、图的完全关联矩阵是不是唯一的一个图的完全关联矩阵是不是唯一的?完全关联矩阵是不是唯一的确定一个图完全关联矩阵是不是唯一的确定一个图?用完全关联矩阵来表示图有什么好处用完全关联矩阵来表示图有什么好处?图的哪些性质可以从完全关联矩阵上一目了然图的哪些性质可以从完全关联矩阵上一目了然?矩阵的运算是否会有相应的图的变化矩阵的运算是否会有相应的图的变化?反过来反过来,图的哪些变化对应着完全关联矩阵的哪些变图的哪些变化对应着完全关联矩阵的哪些变化化?第11页，讲稿共91张，创作于星期日 一一般般地地说说，我我们们把把一一个个n阶阶方方阵阵A的的某某些些列列作作一一置置换换，再再把把相相应应的的行行作作同同

8、样样的的置置换换，得得到到一一个个新新的的n阶阶方方阵阵A，我我们们称称A和和A为为置置换换等等价价。按按不不同同次次序序所所写写出出来来的的邻邻接接矩矩阵阵是是彼彼此此置置换换等等价价的的，今今后后我我们们略略去去这这种种元元素素次次序序的的任任意意性性，可可取取任任何何一一个邻接矩阵作为该图的矩阵表示。个邻接矩阵作为该图的矩阵表示。第12页，讲稿共91张，创作于星期日课堂练习课堂练习1 1、写出下图所示无向图的完全关联矩阵、写出下图所示无向图的完全关联矩阵v2v3e2v4e5e4e3e1v1第13页，讲稿共91张，创作于星期日有向图的关联矩阵有向图的关联矩阵有向图的关联矩阵有向图的关联矩阵

9、定义定义 给定简单有向图给定简单有向图D=，V=v1,v2,vp,E=e1,e2,eq,pq阶矩阵阶矩阵M(D)=(mij)pq，其中其中称称M(G)为为D的的完全关联矩阵。完全关联矩阵。第14页，讲稿共91张，创作于星期日v1v2v3v4e6e1e2e3e5e4第15页，讲稿共91张，创作于星期日例例例例 求下图的完全关联矩阵求下图的完全关联矩阵求下图的完全关联矩阵求下图的完全关联矩阵e1e2e3e4e5e6e7v11000111v2-1 100000v30-1 100-1 0v400-1 100-1v5000-1-1 00第16页，讲稿共91张，创作于星期日有向图的完全关联矩阵的性质有向图

10、的完全关联矩阵的性质有向图的完全关联矩阵的性质有向图的完全关联矩阵的性质(4)平行边对应的列相同。平行边对应的列相同。(5)不能表示自环。不能表示自环。第17页，讲稿共91张，创作于星期日v2v3e2v4e5e4e3e1v1第18页，讲稿共91张，创作于星期日完全关联矩阵的秩完全关联矩阵的秩完全关联矩阵的秩完全关联矩阵的秩定理定理 如果连通图如果连通图G有有p个顶点，则其完全关联矩个顶点，则其完全关联矩阵的秩为阵的秩为p-1，即，即rank M(G)=p-1。证明证明 对无向图进行证明对无向图进行证明 (1)因为因为M(G)中的每一列只有两个中的每一列只有两个1，若把，若把M(G)的其余所有行

11、加到最后一行上，则最后一行全的其余所有行加到最后一行上，则最后一行全为为0（模（模2的运算，相当于各点邻集的环合），的运算，相当于各点邻集的环合），故故rank M(G)p-1。第19页，讲稿共91张，创作于星期日(2)应用行变换使得应用行变换使得M(G)第第1列（边列（边e）中的）中的1个非个非零元在第零元在第1行第行第1列的位置，然后把第列的位置，然后把第1行加到第行加到第1列另一个非零元所在行上，使得第列另一个非零元所在行上，使得第1列中只有列中只有在首行上为在首行上为1，其余全为，其余全为0，得到矩阵，得到矩阵M(G)。第20页，讲稿共91张，创作于星期日v2v3e2v4e5e4e3e

12、1v1v3v4e2 e5e4e3V1,v2第21页，讲稿共91张，创作于星期日由于由于G1是将是将M(G)的第的第1行与另一个首个元素为行与另一个首个元素为1的行加起的行加起来，对应的是将图的两个顶点放在一起，因此来，对应的是将图的两个顶点放在一起，因此G1必是必是连通图，所以连通图，所以M(G1)中没有全零行。若中没有全零行。若M(G1)的第的第1列列全零，则将全零，则将M(G1)中的非零列与它对换，然后再用交中的非零列与它对换，然后再用交换行和一行加到另一行，使换行和一行加到另一行，使M(G1)中第中第1列首元素为列首元素为1，其余元素为零，得到，其余元素为零，得到M(G)，如图所示，如图

13、所示第22页，讲稿共91张，创作于星期日第23页，讲稿共91张，创作于星期日继续上述过程，并不改变矩阵秩，最终在经过继续上述过程，并不改变矩阵秩，最终在经过p-1-1次，次，将将M(G)变换成变换成M(p p-1)-1)(G)，如上图所示，如上图所示,显然显然rank rank M(G)=rank)=rank M(p-1)-1)(G)p-1-1。综上所述，有。综上所述，有rank rank M(G)=)=p-1-1。第24页，讲稿共91张，创作于星期日例例例例 计算完全关联矩阵计算完全关联矩阵计算完全关联矩阵计算完全关联矩阵MM(G G)的秩。的秩。的秩。的秩。e1e2e3e4e5e6e7v1

14、0000011v20001110v30111000v41100000v51010101(4)(1)第25页，讲稿共91张，创作于星期日(1)(5)(2)(3)(2)(5)(3)(4)第26页，讲稿共91张，创作于星期日(3)(5)(4)(6)(4)(5)这个矩阵的秩为这个矩阵的秩为4，即即rank M(G)=5-1=4。第27页，讲稿共91张，创作于星期日推论推论推论推论推论推论 设图设图G有有p个结点，个结点，k个连通分支，则图个连通分支，则图G完全关完全关联矩阵的秩为联矩阵的秩为p-k。证明证明 设图设图G有有p个结点，个结点，k个连通分支，则通过对个连通分支，则通过对M(G)进行行交换和

15、列交换，总能得到如下分块矩阵。进行行交换和列交换，总能得到如下分块矩阵。第28页，讲稿共91张，创作于星期日其中其中M(Gi)是连通子图是连通子图Gi的关联矩阵，其对应的的关联矩阵，其对应的结点个数设为结点个数设为pi。rank M(Gi)=pi-1，则，则 rank M(G)=(p1-1)+(p2-1)+(pk-1)=p-k第29页，讲稿共91张，创作于星期日v2v3e2v4e5e4e3e1v1图的完全关联矩阵可以去掉一行，图的完全关联矩阵可以去掉一行，改称关联矩阵，去掉那一行所对应改称关联矩阵，去掉那一行所对应的点称为参考点。的点称为参考点。完全关联矩阵完全关联矩阵 v1为参考点为参考点

16、关联矩阵关联矩阵第30页，讲稿共91张，创作于星期日定义：连通图定义：连通图G=(p,q)的一个阶为的一个阶为minp,q的方的方阵称为阵称为pq矩阵的一个大子阵，大子阵的行矩阵的一个大子阵，大子阵的行列式称为大行列式。列式称为大行列式。第31页，讲稿共91张，创作于星期日定理：连通图定理：连通图G的关联矩阵的关联矩阵M的一个大子阵的一个大子阵是非奇异的充要条件是与这个大子阵的列是非奇异的充要条件是与这个大子阵的列相应的边，组成相应的边，组成G的一颗生成树的一颗生成树.第32页，讲稿共91张，创作于星期日v2v3e2v4e5e4e3e1v1第33页，讲稿共91张，创作于星期日v2v3e2v4e

17、5e4e3e1v1生成树的边数为顶点数生成树的边数为顶点数4-1=3，因此若，因此若对应的边是一棵生成树（连通图的秩为对应的边是一棵生成树（连通图的秩为顶点数减顶点数减1）其秩必为）其秩必为3（树中有（树中有4个顶点个顶点3条边且是连通图，）条边且是连通图，）第34页，讲稿共91张，创作于星期日第35页，讲稿共91张，创作于星期日6.5 图的邻接矩阵图的邻接矩阵第36页，讲稿共91张，创作于星期日邻接矩阵邻接矩阵邻接矩阵邻接矩阵 定义定义 设设G=是一个无向简单图，它有是一个无向简单图，它有p个个顶点顶点V=v1,v2,vp,则则p阶方阵阶方阵A(G)=(aij)称称为为G的邻接矩阵，其中的邻

18、接矩阵，其中第37页，讲稿共91张，创作于星期日v1v4v2v3第38页，讲稿共91张，创作于星期日e2e5v1v2v3v4e1e4e3 第39页，讲稿共91张，创作于星期日例例 已知无向图的邻接矩阵如下，已知无向图的邻接矩阵如下，试画出相应的无试画出相应的无向图。向图。v1v6v5v4v3v2第40页，讲稿共91张，创作于星期日第第7 7章章 图论图论(Graph Theory)计算机科学与工程系 10.已知图已知图G的邻接矩阵如下的邻接矩阵如下请画出请画出G的图形。的图形。第41页，讲稿共91张，创作于星期日v1v6v5v4v3v2解：画法：解：画法：先确定结点再用行确定边。先确定结点再用

19、行确定边。第42页，讲稿共91张，创作于星期日有向图的邻接矩阵有向图的邻接矩阵 设有向图设有向图D=的顶点集的顶点集V=v1，v2，vp 则则n阶方阵阶方阵A(D)=(aij)pp称为称为D的邻接矩阵，其中的邻接矩阵，其中 第43页，讲稿共91张，创作于星期日v4v3v2v1第44页，讲稿共91张，创作于星期日v1v4v3v2第45页，讲稿共91张，创作于星期日课堂练习：课堂练习：写出下图所示有向图的邻接矩阵写出下图所示有向图的邻接矩阵v2v3e2v4e5e4e3e1v1第46页，讲稿共91张，创作于星期日邻接矩阵的性质邻接矩阵的性质邻接矩阵的性质邻接矩阵的性质n无向简单图的邻接矩阵是对称的；

20、有向图的邻接矩无向简单图的邻接矩阵是对称的；有向图的邻接矩阵不一定对称。阵不一定对称。n邻接矩阵与结点的标定顺序有关，不同标定顺序对邻接矩阵与结点的标定顺序有关，不同标定顺序对应的邻接矩阵是彼此置换等价的。应的邻接矩阵是彼此置换等价的。n在无向图的邻接矩阵中，第在无向图的邻接矩阵中，第i行中非零元的个数等于行中非零元的个数等于vi的度，第的度，第i列中非零元的个数等于列中非零元的个数等于vi的度。的度。n在有向图的邻接矩阵中，第在有向图的邻接矩阵中，第i行中所有元素之和等于行中所有元素之和等于vi的出度，第的出度，第i列中所有元素之和等于列中所有元素之和等于vi的入度。的入度。第47页，讲稿共

21、91张，创作于星期日 由邻接矩阵的定义可知，邻接矩阵是表示图的顶点之间由邻接矩阵的定义可知，邻接矩阵是表示图的顶点之间相邻关系的矩阵，无向图的邻接矩阵是对称矩阵，而有向相邻关系的矩阵，无向图的邻接矩阵是对称矩阵，而有向图的邻接矩阵则未必是对称矩阵；当图的邻接矩阵则未必是对称矩阵；当G为有为有k个连通分支个连通分支G1,1,G2,2,Gk的分离图时，适当调整顶点的顺序，则邻接的分离图时，适当调整顶点的顺序，则邻接矩阵为准分块对角阵。矩阵为准分块对角阵。第48页，讲稿共91张，创作于星期日电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程143-143-4949例例试写出

22、下图所示图试写出下图所示图G G的邻接矩阵。的邻接矩阵。v v1 1v v2 2v v5 5v v4 4v v3 3v v6 6分分析析 首首先先将将图图中中的的6 6个个结结点点排排序序，然然后后利利用用定定义义9.2.29.2.2写写出出其其邻邻接接矩矩阵阵。初初学学时时可可先先在在矩矩阵阵的的行行与与列列前前分分别别按按结结点点排排序序标标上上结结点点，若若第第i i行行前前的的结结点点到到第第j j列列前前的的结结点点有有边边相相连连，则则在在邻邻接接矩矩阵阵的的第第i i行行第第j j列列元元素素为为1 1，否否则则为为0 0。若若结结点点排序为排序为v v1 1v v2 2v v3

23、 3v v4 4v v5 5v v6 6，则可标记如下：，则可标记如下：解解 若若结结点点排排序序为为v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6，则则其其邻邻接矩阵接矩阵第49页，讲稿共91张，创作于星期日电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程143-143-5050说明说明 由由例例题题可可看看出出，图图G G=V,E的的邻邻接接矩矩阵阵依依赖赖于于V V中中元元素素的的次次序序。对对于于V V中中各各元元素素不不同同的的排排序序，可可得得到到同同一一图图G G的的不不同同邻邻接接矩矩阵阵。但但是是，G G的的任任何何一一个

24、个邻邻接接矩矩阵阵可可以以从从G G的的另另一一邻邻接接矩矩阵阵中中通通过过交交换换某某些些行行和和相相应应的的列列而而得得到到，其其交交换换过过程程与与将将一一个个排排序序中中的的结结点点交交换换位位置置变变为为另另一一个个排排序序是是一一致致的的。如如果果我我们们略略去去由由结结点点排排序序不不同同而而引引起起的的邻邻接接矩矩阵阵的的不不同同，则则图图与与邻邻接接矩矩阵阵之之间间是是一一一一对对应应的的。因因此此，我我们们略略去去这这种种由由于于V V中中元元素素的的次次序序而而引引起起的的邻邻接接矩矩阵阵的的任任意意性性，只只选选V V中中元元素素的的任任一一种种次次序序所所得得出出的的

25、邻邻接接矩矩阵，作为图阵，作为图G G的邻接矩阵。的邻接矩阵。第50页，讲稿共91张，创作于星期日第第7 7章章 图论图论(Graph Theory)计算机科学与工程系 如图所示如图所示G，其邻接矩阵其邻接矩阵A为为 显然无向图的邻接矩阵必是对称的。显然无向图的邻接矩阵必是对称的。下下面面的的定定理理说说明明，在在邻邻接接矩矩阵阵A的的幂幂A2，A3，等矩阵中，等矩阵中，每个元素有特定的含义。每个元素有特定的含义。第51页，讲稿共91张，创作于星期日利用邻接矩阵计算两点间途径的数目利用邻接矩阵计算两点间途径的数目利用邻接矩阵计算两点间途径的数目利用邻接矩阵计算两点间途径的数目定理定理 设设A(

26、G)是图是图G的邻接矩阵，则的邻接矩阵，则(A(G)l中的中的i行，行，j列元素列元素aij(l)等于等于G中联结中联结vi与与vj的长度为的长度为l的途径的数目。的途径的数目。分析：分析：(1)A(G)中所有元素之和为中所有元素之和为G中长度为中长度为1的路的数目。的路的数目。第52页，讲稿共91张，创作于星期日(2)G中有长度为中有长度为2的路的路vivkvj存在存在aik=akj=1，所以从结，所以从结点点vi到结点到结点vj的长度为的长度为2的路的数目等于的路的数目等于第53页，讲稿共91张，创作于星期日v2v3e2v4e5e4e3e1v1v1v3v2v4第54页，讲稿共91张，创作于

27、星期日v2v3e2v4e5e4e3e1v1第55页，讲稿共91张，创作于星期日第56页，讲稿共91张，创作于星期日v2v3e2v4e5e4e3e1v1第57页，讲稿共91张，创作于星期日v2v3e2v4e5e4e3e1v1v1v3v2v4v1v3v2v4第58页，讲稿共91张，创作于星期日利用邻接矩阵计算途径的数目利用邻接矩阵计算途径的数目利用邻接矩阵计算途径的数目利用邻接矩阵计算途径的数目从从vi到到vj的长度为的长度为l的路，可以看成是由的路，可以看成是由vi到到vk的一的一条长度为条长度为1的路和的路和vk到到vj的一条长度为的一条长度为l-1的路合的路合成，所以成，所以vi到到vj的长

28、度为的长度为l的路的数目为：的路的数目为：第59页，讲稿共91张，创作于星期日第第7 7章章 图论图论(Graph Theory)计算机科学与工程系 由定理可得出以下结论：由定理可得出以下结论：1)如如果果对对l1，2，n-1，Al的的（i，j）项项元元素素（ij）都都为为零零，那那么么vi和和vj之之间间无无任任何何路路相相连连接接，即即vi和和vj不不连通。因此，连通。因此，vi和和vj必属于必属于G的不同的连通分支。的不同的连通分支。2)结结点点vi 到到vj（ij）间间的的距距离离d（vi，vj）是是使使Al（l1，2，n-1）的（）的（i，j）项元素不为零的最小整数）项元素不为零的最

29、小整数l。3)Al的的（i，i）项项元元素素a(l)ii表表示示开开始始并并结结束束于于vi长长度度为为l的回路的数目。的回路的数目。第60页，讲稿共91张，创作于星期日离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院离散数学离散数学 湖南工学院湖南工学院 计算机与信息科学系计算机与信息科学系例8.8 图图G的的图图形如形如图图8.17所示，求所示，求邻邻接矩接矩阵阵A和和A2，A3，A4，并分析其元素的并分析其元素的图论图论意意义义。解：写出解：写出A的的邻邻接矩接矩阵阵，并求出并求出A2，A3，A4如下，如下，第61页，讲稿共91张，创作于星期日离散数学离散数学 中国地质大

30、学中国地质大学 计算机学院计算机学院离散数学离散数学 湖南工学院湖南工学院 计算机与信息科学系计算机与信息科学系第62页，讲稿共91张，创作于星期日第第7 7章章 图论图论(Graph Theory)计算机科学与工程系 1)由由A中中a(1)121知，知，v1和和v2是邻接的；是邻接的；由由A3中中a(3)122知，知，v1到到v2长度为长度为3的路有两条，的路有两条，从图中可看出是从图中可看出是v1v2v1v2和和v1v2v3v2。2)由由A2的的主主对对角角线线上上元元素素知知，每每个个结结点点都都有有长长度度为为的的回回路路，其其中中结结点点v2有有两两条条：v2v1v2和和v2v3v2

31、，其其余余结结点只有一条。点只有一条。第63页，讲稿共91张，创作于星期日第第7 7章章 图论图论(Graph Theory)计算机科学与工程系4)由于由于 所以结点所以结点v3和和v4间无路，间无路，它们属于不同的连通分支。它们属于不同的连通分支。5)d（v1，v3）。）。3)由于由于A3的主对角线上元素全为零，的主对角线上元素全为零，所以所以G中没有长度中没有长度为的回路。为的回路。第64页，讲稿共91张，创作于星期日e2e5v1v2v3v4e1e4e3 例例1 设设G=（V,E）为简单为简单有无有无图图，如下，如下图图，确定，确定v1到到v2有多少有多少条条长长度度为为3的途径的途径?v

32、1到到v3有多少有多少条条长长度度为为2的路的路?v2到自身到自身长长度度为为3回路各多少条回路各多少条?第65页，讲稿共91张，创作于星期日e2e5v1v2v3v4e1e4e3第66页，讲稿共91张，创作于星期日例例2 给定图给定图G=，求，求v1到到v3的长度为的长度为1,2,3,4的路的数目。经的路的数目。经过过v2的回路共有多少条？的回路共有多少条？第67页，讲稿共91张，创作于星期日v1到到v3的长度为的长度为1的路有的路有0条条v1到到v3的长度为的长度为2的路有的路有1条条v1到到v3的长度为的长度为3的路有的路有0条条v1到到v3的长度为的长度为4的路有的路有2条条经过经过v2

33、的回路共有的回路共有a22(2)+a22(3)+a22(4)=2+0+4=6第68页，讲稿共91张，创作于星期日基于邻接矩阵的其它矩阵基于邻接矩阵的其它矩阵第69页，讲稿共91张，创作于星期日1.1.赋权图的邻接矩阵赋权图的邻接矩阵赋权图的邻接矩阵赋权图的邻接矩阵 定义定义 设设G=是一个赋权图，它有是一个赋权图，它有p个顶点个顶点V=v1,v2,vp,则则p阶方阵阶方阵A(G)=(aij)称为赋权称为赋权图图G的邻接矩阵，其中的邻接矩阵，其中其中其中wij是边是边(vi,vj)上的权值上的权值,表示顶点表示顶点i和和j之间没有边相连之间没有边相连.第70页，讲稿共91张，创作于星期日2 5v

34、1v2v3v4436第71页，讲稿共91张，创作于星期日定义定义 令令 G 是一个简单有向图，假定是一个简单有向图，假定 V 的顶点已编序，即的顶点已编序，即 Vv1,v2,vp，定义一个，定义一个 pp 矩阵矩阵P=P(pij)。其中。其中 称矩阵称矩阵 P 是图是图 G 的的可达性矩阵可达性矩阵。2.2.可达性矩阵可达性矩阵可达性矩阵可达性矩阵第72页，讲稿共91张，创作于星期日 在定在定义义中，中，规规定了有向定了有向图图的任何的任何结结点自己和自己可达。点自己和自己可达。所以可达性矩所以可达性矩阵阵P(G)的主的主对对角角线线元素全元素全为为1。可达性矩。可达性矩阵阵用来用来描述有向描

35、述有向图图的一个的一个结结点到另一个点到另一个结结点是否有路，即是否可达。点是否有路，即是否可达。无向无向图图也可以用矩也可以用矩阵阵描述一个描述一个结结点到另一个点到另一个结结点是否有路。在点是否有路。在无向无向图图中，如果中，如果结结点之点之间间有路，称有路，称这这两个两个结结点点连连通。通。由可达性矩由可达性矩阵阵的定的定义义知，知，当当ij时时，如果，如果vi到到vj有路，有路，则则 =1；如果如果vi到到vj无路，无路，则则 =0；又可知，如果；又可知，如果vi到到vj有路，有路，则则必存在必存在长长度小于等于度小于等于p1的路。的路。第73页，讲稿共91张，创作于星期日 用用图图G

36、的的邻邻接接矩矩阵阵A(G)的的幂幂矩矩阵阵来来求求图图G的可达性矩的可达性矩阵阵P：先计算Bp1=AA2Ap1，设Bp1=()pp。若 0，则令 =1，若 =0，则令pij=0，i,j=1,p。第74页，讲稿共91张，创作于星期日Vv1v3v1v2v3v4第75页，讲稿共91张，创作于星期日v1v2v3v4第76页，讲稿共91张，创作于星期日3.度度对对角矩角矩阵阵的定的定义义 设设G是是一一个个简简单单图图，顶顶点点集集合合V V=v v1 1，v v2 2，v vp p，定，定义义p p阶阶方方阵阵 称称为为G的度的度对对角矩角矩阵阵，其中，其中，第77页，讲稿共91张，创作于星期日图G

37、和它的度对角矩阵v2v3e2v4e5e4e3e1v1第78页，讲稿共91张，创作于星期日e2e5v1v2v3v4e1e4e3 第79页，讲稿共91张，创作于星期日删删去第去第1行及第行及第1列后得到的矩列后得到的矩阵为阵为B*，则则第80页，讲稿共91张，创作于星期日图的其它代数特征图的其它代数特征第81页，讲稿共91张，创作于星期日图图的特征多的特征多项项式与式与图图的几何特征的几何特征定定义义 图图G的的邻邻接矩接矩阵阵A(G)的行列式称的行列式称为图为图G的行列式，的行列式，记记作作detG，图图G的的邻邻接矩接矩阵阵A(G)的特征多的特征多项项式称式称为图为图G的的特征多特征多项项式，

38、式，记记作作定理定理 设设G是是r正则图，则正则图，则（1）r是是G的一个特征值；的一个特征值；（2）r的重数等于的重数等于G的分支数；的分支数；（3）G的任一特征值的任一特征值 满足满足第82页，讲稿共91张，创作于星期日v1v2v3v4第83页，讲稿共91张，创作于星期日v1v2v3v4第84页，讲稿共91张，创作于星期日思考思考题题.1.无向无向图图G如如图图所示。所示。写出写出G的的邻邻接矩接矩阵阵。第85页，讲稿共91张，创作于星期日 求求G中中长长度度为为3的路的的路的总总数，其中有多少条回路。数，其中有多少条回路。根据根据邻邻接矩接矩阵阵求各求各结结点的度数。点的度数。deg(v

39、1)=3 deg(v2)=3 deg(v3)=2 deg(v4)=2第86页，讲稿共91张，创作于星期日 求求G的可达性矩的可达性矩阵阵。第87页，讲稿共91张，创作于星期日 求求G的完全关的完全关联联矩矩阵阵。由完全关由完全关联联矩矩阵阵求各求各结结点的度数。点的度数。deg(v1)=3 deg(v2)=3 deg(v3)=2 deg(v4)=2第88页，讲稿共91张，创作于星期日思考思考题题：2.有向有向图图G如如图图所示。所示。写出写出G的的邻邻接矩接矩阵阵。第89页，讲稿共91张，创作于星期日 根据根据邻邻接矩接矩阵阵求各求各结结点的出度和入度。点的出度和入度。deg(v1)=2 deg(v2)=1 deg(v3)=2 deg(v4)=0deg(v1)=1 deg(v2)=2 deg(v3)=1 deg(v4)=1 求求G中中长长度度为为3的路的的路的总总数，其中有多少条回路。数，其中有多少条回路。共有共有8条，条，3条回路。条回路。第90页，讲稿共91张，创作于星期日 求求G的可达性矩的可达性矩阵阵。可达性矩可达性矩阵阵P=第91页，讲稿共91张，创作于星期日