图的矩阵表示讲稿.ppt

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

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

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

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

4、矩阵 第四页，讲稿共九十一页哦图的矩阵表示图的矩阵表示 计算机科学领域有许多算法涉及图。计算机存储图计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。有效工具和手段。第五页，讲稿共九十一页哦6.1 无向图的完全关联矩阵无向图的完全关联矩阵定义定义 给定无向图给定无向图G，令，令v1,v2,vp,e1,

5、e2,eq分别记为分别记为M(G)的顶点和边，则矩阵的顶点和边，则矩阵M(G)=(mij)pq，其中，其中 jijiijevevm不关联若关联若01称M(G)为图G的完全关联矩阵。第六页，讲稿共九十一页哦例例 下图下图G的完全关联矩阵为：的完全关联矩阵为：v1v2v3v4v5e1e2e3e412341234511011010()011000010000eeeevvM Gvvv 第七页，讲稿共九十一页哦实例实例1例例1 求下图的完全关联矩阵。求下图的完全关联矩阵。e1e2e3e4e5e6v1110011v2111000v3001101v4000110v5000000第八页，讲稿共九十一页哦无向图

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

7、100000111110011)(54321654321vvvvveeeeeeGM第十页，讲稿共九十一页哦一个图的完全关联矩阵是不是唯一的一个图的完全关联矩阵是不是唯一的?完全关联矩阵是不是唯一的确定一个图完全关联矩阵是不是唯一的确定一个图?用完全关联矩阵来表示图有什么好处用完全关联矩阵来表示图有什么好处?图的哪些性质可以从完全关联矩阵上一目了然图的哪些性质可以从完全关联矩阵上一目了然?矩阵的运算是否会有相应的图的变化矩阵的运算是否会有相应的图的变化?反过来反过来,图的哪些变化对应着完全关联矩阵的哪些变图的哪些变化对应着完全关联矩阵的哪些变化化?第十一页，讲稿共九十一页哦 一般地说，我们把一个

8、一般地说，我们把一个n阶方阵阶方阵A的某些列作一置的某些列作一置换，再把相应的行作同样的置换，得到一个新的换，再把相应的行作同样的置换，得到一个新的n阶方阶方阵阵A，我们称，我们称A和和A为置换等价。按不同次序所写出为置换等价。按不同次序所写出来的邻接矩阵是彼此置换等价的，今后我们略去这种来的邻接矩阵是彼此置换等价的，今后我们略去这种元素次序的任意性，可取任何一个邻接矩阵作为该图元素次序的任意性，可取任何一个邻接矩阵作为该图的矩阵表示。的矩阵表示。第十二页，讲稿共九十一页哦201000101001010002000 010001010000001000100001000001AA课堂练习课堂练

9、习1 1、写出下图所示无向图的完全关联矩阵、写出下图所示无向图的完全关联矩阵v2v3e2v4e5e4e3e1v1第十三页，讲稿共九十一页哦有向图的关联矩阵有向图的关联矩阵定义定义 给定简单有向图给定简单有向图D=，V=v1,v2,vp,E=e1,e2,eq,pq阶矩阵阶矩阵M(D)=(mij)pq，其中其中 jijijiijevevevm不关联若的终点是若的起点是若01-1称M(G)为D的完全关联矩阵。第十四页，讲稿共九十一页哦v1v2v3v4e6e1e2e3e5e4011100111000000011100111vvvveeeeee4321654321第十五页，讲稿共九十一页哦例例 求下图的

10、完全关联矩阵求下图的完全关联矩阵e1e2e3e4e5e6e7v11000111v2-1 100000v30-1 100-1 0v400-1 100-1v5000-1-1 00第十六页，讲稿共九十一页哦 jiijmjiijmjiijniijmnivdmvdmmjm,1110)3(,.,2,1),()1(),()1()2(),.,2,1(0)1(有向图的完全关联矩阵的性质有向图的完全关联矩阵的性质(4)平行边对应的列相同。平行边对应的列相同。(5)不能表示自环。不能表示自环。第十七页，讲稿共九十一页哦v2v3e2v4e5e4e3e1v11111111111)(432154321vvvveeeeeG

11、M第十八页，讲稿共九十一页哦完全关联矩阵的秩完全关联矩阵的秩定理定理 如果连通图如果连通图G有有p个顶点，则其完全关联矩个顶点，则其完全关联矩阵的秩为阵的秩为p-1，即，即rank M(G)=p-1。证明证明 对无向图进行证明对无向图进行证明 (1)因为因为M(G)中的每一列只有两个中的每一列只有两个1，若把，若把M(G)的其余所有行加到最后一行上，则最后一行全的其余所有行加到最后一行上，则最后一行全为为0（模（模2的运算，相当于各点邻集的环合），的运算，相当于各点邻集的环合），故故rank M(G)p-1。第十九页，讲稿共九十一页哦(2)应用行变换使得应用行变换使得M(G)第第1列（边列（边

12、e）中的）中的1个非个非零元在第零元在第1行第行第1列的位置，然后把第列的位置，然后把第1行加到第行加到第1列另一个非零元所在行上，使得第列另一个非零元所在行上，使得第1列中只有列中只有在首行上为在首行上为1，其余全为，其余全为0，得到矩阵，得到矩阵M(G)。100111001110011110001100001011011010110101101001100000000000第二十页，讲稿共九十一页哦v2v3e2v4e5e4e3e1v1100111001110011110001100001011011010110101101001100000000000v3v4e2 e5e4e3V1,v2第

13、二十一页，讲稿共九十一页哦由于由于G1是将是将M(G)的第的第1行与另一个首个元素为行与另一个首个元素为1的行加起的行加起来，对应的是将图的两个顶点放在一起，因此来，对应的是将图的两个顶点放在一起，因此G1必是必是连通图，所以连通图，所以M(G1)中没有全零行。若中没有全零行。若M(G1)的第的第1列列全零，则将全零，则将M(G1)中的非零列与它对换，然后再用交中的非零列与它对换，然后再用交换行和一行加到另一行，使换行和一行加到另一行，使M(G1)中第中第1列首元素为列首元素为1，其余元素为零，得到其余元素为零，得到M(G)，如图所示，如图所示 )(001)(1GMGM100111001111

14、0000101101101000110110101010第二十二页，讲稿共九十一页哦10111101011010111011011000111001110011110000011010001100100111001100110110000000第二十三页，讲稿共九十一页哦 00)(0101)(2GMGM10100100100000 (p-1)M(G)继续上述过程，并不改变矩阵秩，最终在经过继续上述过程，并不改变矩阵秩，最终在经过p-1-1次，次，将将M(G)变换成变换成M(p p-1)-1)(G)，如上图所示，如上图所示,显然显然rank rank M(G)=rank)=rank M(p-1)

15、-1)(G)p-1-1。综上所述，有。综上所述，有rank rank M(G)=)=p-1-1。第二十四页，讲稿共九十一页哦例例 计算完全关联矩阵计算完全关联矩阵M(G)的秩。的秩。e1e2e3e4e5e6e7v10000011v20001110v30111000v41100000v51010101(4)(1)10101011100000000111001110000000011第二十五页，讲稿共九十一页哦(1)(5)(2)(3)(2)(5)(3)(4)10101101100000000111001110000000011 10101101100000011100000011100000011

16、 10110001100000011100000011100000011 10101001100000011010000011100000011第二十六页，讲稿共九十一页哦(3)(5)(4)(6)(4)(5)这个矩阵的秩为这个矩阵的秩为4，即即rank M(G)=5-1=4。11000001100000011010000011100000011 10010001001000001110001001100000011 00000001001000001110001001100000011第二十七页，讲稿共九十一页哦推论推论推论推论 设图设图G有有p个结点，个结点，k个连通分支，则图个连通分支，则

17、图G完全关完全关联矩阵的秩为联矩阵的秩为p-k。证明证明 设图设图G有有p个结点，个结点，k个连通分支，则通过对个连通分支，则通过对M(G)进行行交换和列交换，总能得到如下分块矩进行行交换和列交换，总能得到如下分块矩阵。阵。000000012kM(G)M(G)M(G)M(G)第二十八页，讲稿共九十一页哦000000012kM(G)M(G)M(G)M(G)其中其中M(Gi)是连通子图是连通子图Gi的关联矩阵，其对应的结的关联矩阵，其对应的结点个数设为点个数设为pi。rank M(Gi)=pi-1，则，则 rank M(G)=(p1-1)+(p2-1)+(pk-1)=p-k第二十九页，讲稿共九十一

18、页哦v2v3e2v4e5e4e3e1v111000011010011010011110000110100110图的完全关联矩阵可以去掉一图的完全关联矩阵可以去掉一行，改称关联矩阵，去掉那一行，改称关联矩阵，去掉那一行所对应的点称为参考点。行所对应的点称为参考点。完全关联矩阵完全关联矩阵 v1为参考点为参考点 关联矩阵关联矩阵第三十页，讲稿共九十一页哦定义：连通图定义：连通图G=(p,q)的一个阶为的一个阶为minp,q的的方阵称为方阵称为pq矩阵的一个大子阵，大子阵的矩阵的一个大子阵，大子阵的行列式称为大行列式。行列式称为大行列式。1001110011100011001011010110001

19、100001101第三十一页，讲稿共九十一页哦定理：连通图定理：连通图G的关联矩阵的关联矩阵M的一个大子阵是的一个大子阵是非奇异的充要条件是与这个大子阵的列相应非奇异的充要条件是与这个大子阵的列相应的边，组成的边，组成G的一颗生成树的一颗生成树.第三十二页，讲稿共九十一页哦110000110100110110011001123 e e e1完全关联矩阵10011110000110100110关联矩阵(v 为参考点)一个可逆的大子阵v2v3e2v4e5e4e3e1v1第三十三页，讲稿共九十一页哦110000110100110110011001123234 e e evvv1一个可关联矩阵(v 为

20、参考点阵)逆的大子v2v3e2v4e5e4e3e1v1生成树的边数为顶点数生成树的边数为顶点数4-1=3，因此若对应，因此若对应的边是一棵生成树（连通图的秩为顶点数减的边是一棵生成树（连通图的秩为顶点数减1）其秩必为）其秩必为3（树中有（树中有4个顶点个顶点3条边且是连条边且是连通图，）通图，）第三十四页，讲稿共九十一页哦110000110100110110011001123234 e e evvv1一个可关联矩阵(v 为参考点阵)逆的大子第三十五页，讲稿共九十一页哦6.5 图的邻接矩阵图的邻接矩阵第三十六页，讲稿共九十一页哦邻接矩阵邻接矩阵 定义定义 设设G=是一个无向简单图，它有是一个无向

21、简单图，它有p个个顶点顶点V=v1,v2,vp,则则p阶方阵阶方阵A(G)=(aij)称为称为G的邻接矩阵，其中的邻接矩阵，其中10ijijijvvavvij邻接不邻接或第三十七页，讲稿共九十一页哦v1v4v2v3 0001001101011110)(GA第三十八页，讲稿共九十一页哦e2e5v1v2v3v4e1e4e312342134vvvvvvvv12213344vv01010111vv10111001A(G)=A(G)=vv01011001vv11101110 第三十九页，讲稿共九十一页哦例例 已知无向图的邻接矩阵如下，已知无向图的邻接矩阵如下，试画出相应的无向试画出相应的无向图。图。01

22、0110101011010001100010110101011010)(GAv1v6v5v4v3v2第四十页，讲稿共九十一页哦第第7 7章章 图论图论(Graph Theory)计算机科学与工程系 10.已知图已知图G的邻接矩阵如下的邻接矩阵如下0101010011000111110101110A 请画出请画出G的图形。的图形。第四十一页，讲稿共九十一页哦v1v6v5v4v3v2解：画法：解：画法：先确定结点再用行确定边。先确定结点再用行确定边。第四十二页，讲稿共九十一页哦有向图的邻接矩阵有向图的邻接矩阵 设有向图设有向图D=的顶点集的顶点集V=v1，v2，vp 则则n阶方阵阶方阵A(D)=(

23、aij)pp称为称为D的邻接矩阵，其中的邻接矩阵，其中 ),(0),(1EvvEvvajijiij第四十三页，讲稿共九十一页哦v4v3v2v112341234vvvvv0100v0011A(G)=v1001v1000第四十四页，讲稿共九十一页哦v1v4v3v2 0110101100011000)(GA第四十五页，讲稿共九十一页哦课堂练习：课堂练习：写出下图所示有向图的邻接矩阵写出下图所示有向图的邻接矩阵v2v3e2v4e5e4e3e1v1第四十六页，讲稿共九十一页哦邻接矩阵的性质邻接矩阵的性质n无向简单图的邻接矩阵是对称的；有向图的邻接矩无向简单图的邻接矩阵是对称的；有向图的邻接矩阵不一定对称

24、。阵不一定对称。n邻接矩阵与结点的标定顺序有关，不同标定顺序对邻接矩阵与结点的标定顺序有关，不同标定顺序对应的邻接矩阵是彼此置换等价的。应的邻接矩阵是彼此置换等价的。n在无向图的邻接矩阵中，第在无向图的邻接矩阵中，第i行中非零元的个数等行中非零元的个数等于于vi的度，第的度，第i列中非零元的个数等于列中非零元的个数等于vi的度。的度。n在有向图的邻接矩阵中，第在有向图的邻接矩阵中，第i行中所有元素之和等行中所有元素之和等于于vi的出度，第的出度，第i列中所有元素之和等于列中所有元素之和等于vi的入度。的入度。第四十七页，讲稿共九十一页哦 由邻接矩阵的定义可知，邻接矩阵是表示图的顶点之由邻接矩阵

25、的定义可知，邻接矩阵是表示图的顶点之间相邻关系的矩阵，无向图的邻接矩阵是对称矩阵，而间相邻关系的矩阵，无向图的邻接矩阵是对称矩阵，而有向图的邻接矩阵则未必是对称矩阵；当有向图的邻接矩阵则未必是对称矩阵；当G为有为有k个连通个连通分支分支G1,1,G2,2,Gk的分离图时，适当调整顶点的顺序，则的分离图时，适当调整顶点的顺序，则邻接矩阵为准分块对角阵。邻接矩阵为准分块对角阵。12()()()()M GM GM GM G 第四十八页，讲稿共九十一页哦电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程143-143-4949例例试写出下图所示图试写出下图所示图G G的邻接矩

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

27、1 1 0 0v vv vv vv vv vv vv vv vv vv vv vv v6 65 54 43 32 21 16 65 54 43 32 21 1 011101101001110100101110000101110010AG解 若结点排序为v1v2v3v4v5v6，则其邻接矩阵第四十九页，讲稿共九十一页哦电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程143-143-5050说明说明 由例题可看出，图由例题可看出，图G=G=的邻接矩阵依的邻接矩阵依赖于赖于V V中元素的次序。对于中元素的次序。对于V V中各元素不同的排序，中各元素不同的排序，可得到同一图

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

29、而引起的邻接矩阵的任意性，只选意性，只选V V中元素的任一种次序所得出的邻接矩中元素的任一种次序所得出的邻接矩阵，作为图阵，作为图G G的邻接矩阵。的邻接矩阵。第五十页，讲稿共九十一页哦第第7 7章章 图论图论(Graph Theory)计算机科学与工程系 如图所示如图所示G，其邻接矩阵其邻接矩阵A为为0111110100110101010110010A 显然无向图的邻接矩阵必是对称的。显然无向图的邻接矩阵必是对称的。下面的定理说明，在邻接矩阵下面的定理说明，在邻接矩阵A的幂的幂A2，A3，等矩阵中，等矩阵中，每个元素有特定的含义。每个元素有特定的含义。第五十一页，讲稿共九十一页哦利用邻接矩阵

30、计算两点间途径的数目利用邻接矩阵计算两点间途径的数目定理定理 设设A(G)是图是图G的邻接矩阵，则的邻接矩阵，则(A(G)l中的中的i行，行，j列元素列元素aij(l)等于等于G中联结中联结vi与与vj的长度为的长度为l的途径的数目。的途径的数目。分析：分析：(1)A(G)中所有元素之和为中所有元素之和为G中长度为中长度为1的路的数目。的路的数目。第五十二页，讲稿共九十一页哦(2)G中有长度为中有长度为2的路的路vivkvj存在存在aik=akj=1，所以从结，所以从结点点vi到结点到结点vj的长度为的长度为2的路的数目等于的路的数目等于(2)11221nijijippjikkjijkaaaa

31、aaaaa。列的元素行、第中第是其中jiGAaij2(2)(11ikjvvv 第五十三页，讲稿共九十一页哦v2v3e2v4e5e4e3e1v1v1v3v2v4第五十四页，讲稿共九十一页哦v2v3e2v4e5e4e3e1v11234123401111010A(G)=11011010vvvvvvvv第五十五页，讲稿共九十一页哦 1234123411223344011101111010101011011101101010103121121221311212vvvvvvvvvvvvvvvv第五十六页，讲稿共九十一页哦v2v3e2v4e5e4e3e1v12A3121121221311212第五十七页，讲

32、稿共九十一页哦v2v3e2v4e5e4e3e1v1v1v3v2v4v1v3v2v42A31211212213112121234123401111010A(G)=11011010vvvvvvvv第五十八页，讲稿共九十一页哦利用邻接矩阵计算途径的数目利用邻接矩阵计算途径的数目从从vi到到vj的长度为的长度为l的路，可以看成是由的路，可以看成是由vi到到vk的一的一条长度为条长度为1的路和的路和vk到到vj的一条长度为的一条长度为l-1的路合的路合成，所以成，所以vi到到vj的长度为的长度为l的路的数目为：的路的数目为：121111121jjnjkjn(l-)(l-)(l-)(l-)(l)iiini

33、kijkaaaaaaaaa第五十九页，讲稿共九十一页哦第第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）项元素不为零的最小整数）项元素不为零的最小整数l。

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

35、算机学院计算机学院离散数学离散数学 湖南工学院湖南工学院 计算机与信息科学系计算机与信息科学系1000001000001010002000101A20100010000000200020200020A31000001000002020004000202A40100010000000100010100010A第六十二页，讲稿共九十一页哦第第7 7章章 图论图论(Graph Theory)计算机科学与工程系 1)由由A中中a(1)121知，知，v1和和v2是邻接的；是邻接的；由由A3中中a(3)122知，知，v1到到v2长度为长度为3的路有两条，的路有两条，从图中可看出是从图中可看出是v1v2v1

36、v2和和v1v2v3v2。2)由由A2的主对角线上元素知，的主对角线上元素知，每个结点都有长度为每个结点都有长度为的回路，的回路，其中结点其中结点v2有两条：有两条：v2v1v2和和v2v3v2，其余结其余结点只有一条。点只有一条。第六十三页，讲稿共九十一页哦第第7 7章章 图论图论(Graph Theory)计算机科学与工程系4)由于由于 所以结点所以结点v3和和v4间无路，间无路，它们属于不同的连通分支。它们属于不同的连通分支。5)d（v1，v3）。）。,0)4(34)3(34)2(34)1(34aaaa由于由于A3的主对角线上元素全为零，的主对角线上元素全为零，所以所以G中没有长度中没有

37、长度为的回路。为的回路。第六十四页，讲稿共九十一页哦e2e5v1v2v3v4e1e4e31234vvvv1234v0101v1011A(G)=v0101v1110 例例1 设设G=（V,E）为简单有无图）为简单有无图，如下图，确定，如下图，确定v1到到v2有多少条有多少条长度为长度为3的途径的途径?v1到到v3有多少条有多少条长度为长度为2的路的路?v2到自身长度为到自身长度为3回路各多少条回路各多少条?第六十五页，讲稿共九十一页哦23,AAA010121212525101113125455010121212525111012135554e2e5v1v2v3v4e1e4e3第六十六页，讲稿共九

38、十一页哦例例2 给定图给定图G=，求，求v1到到v3的长度为的长度为1,2,3,4的路的数目。经的路的数目。经过过v2的回路共有多少条？的回路共有多少条？0100010000000100010100010A第六十七页，讲稿共九十一页哦 10000010000010100020001012A 01000100000002000202000203A 10000010000020200040002024Av1到到v3的长度为的长度为1的路有的路有0条条v1到到v3的长度为的长度为2的路有的路有1条条v1到到v3的长度为的长度为3的路有的路有0条条v1到到v3的长度为的长度为4的路有的路有2条条经过经

39、过v2的回路共有的回路共有a22(2)+a22(3)+a22(4)=2+0+4=6第六十八页，讲稿共九十一页哦基于邻接矩阵的其它矩阵基于邻接矩阵的其它矩阵第六十九页，讲稿共九十一页哦1.赋权图的邻接矩阵赋权图的邻接矩阵 定义定义 设设G=是一个赋权图，它有是一个赋权图，它有p个顶点个顶点V=v1,v2,vp,则则p阶方阵阶方阵A(G)=(aij)称为赋权称为赋权图图G的邻接矩阵，其中的邻接矩阵，其中0ijijijijwvvijavvijij 若 与 邻接,若 与 不邻接,其中其中wij是边是边(vi,vj)上的权值上的权值,表示顶点表示顶点i和和j之间没有边相连之间没有边相连.第七十页，讲稿共

40、九十一页哦2 5v1v2v3v443604240565032630第七十一页，讲稿共九十一页哦定义定义 令令 G 是一个简单有向图，假定是一个简单有向图，假定 V 的的顶点已编序，即顶点已编序，即 Vv1,v2,vp，定义一个，定义一个 pp 矩阵矩阵P=P(pij)。其中。其中 称矩阵称矩阵 P 是图是图 G 的的可达性矩阵可达性矩阵。Vnijijij1,从v 到v 至少存在一条路P=0,从v 到v 不存在路 2.可达性矩阵可达性矩阵第七十二页，讲稿共九十一页哦 在定义中，规定了有向图的任何结点自己和自己可达。所在定义中，规定了有向图的任何结点自己和自己可达。所以可达性矩阵以可达性矩阵P(G

41、)的主对角线元素全为的主对角线元素全为1。可达性矩阵用来描述有。可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通。结点之间有路，称这两个结点连通。由可达性矩阵的定义知，由可达性矩阵的定义知，当当ij时，如果时，如果vi到到vj有路，则有路，则 =1；如果如果vi到到vj无路，则无路，则 =0；又可知，如果；又可知，如果vi到到vj有路，则必有路，则必存在长度小于等

42、于存在长度小于等于p1的路。的路。ijpijp第七十三页，讲稿共九十一页哦 用图用图G的邻接矩阵的邻接矩阵A(G)的幂矩阵来求图的幂矩阵来求图G的可达性矩阵的可达性矩阵P：先计算Bp1=AA2Ap1，设Bp1=()pp。若 0，则令 =1，若 =0，则令pij=0，i,j=1,p。1pijb1pijb1pijbijp第七十四页，讲稿共九十一页哦Vv1v312341234()vvvvvvA Gvv0100000100011000v1v2v3v4第七十五页，讲稿共九十一页哦23AAA0100000110000001100001000001100001001000010000011101110111

43、011101v1v2v3v4第七十六页，讲稿共九十一页哦3.度对角矩阵的定义度对角矩阵的定义 设设G是一个简单图，顶点集合是一个简单图，顶点集合V V=v v1 1，v v2 2，v vp p，定义，定义p p阶方阵阶方阵 称为称为G的度对角矩阵，其中，的度对角矩阵，其中，()()ijF Gf 0iijd vijfij 第七十七页，讲稿共九十一页哦图G和它的度对角矩阵 3000020000300002=F GF Gv2v3e2v4e5e4e3e1v1第七十八页，讲稿共九十一页哦e2e5v1v2v3v4e1e4e31234vvvv1234v0101v1011A(G)=v0101v1110 BF

44、GA第七十九页，讲稿共九十一页哦 BF GA G200001012-10-103001011-13-1-1002001010-12-100031110-1-1-13删去第删去第1行及第行及第1列后得到的矩阵为列后得到的矩阵为B*，则，则*8BGB 3-1-13-1-1-43-12-1-12-18-4-1-13-1-13第八十页，讲稿共九十一页哦图的其它代数特征图的其它代数特征第八十一页，讲稿共九十一页哦图的特征多项式与图的几何特征图的特征多项式与图的几何特征定义定义 图图G的邻接矩阵的邻接矩阵A(G)的行列式称为图的行列式称为图G的行列式，的行列式，记作记作detG，图，图G的邻接矩阵的邻接矩

45、阵A(G)的特征多项式称为图的特征多项式称为图G的的特征多项式，记作特征多项式，记作定理定理 设设G是是r正则图，则正则图，则（1）r是是G的一个特征值；的一个特征值；（2）r的重数等于的重数等于G的分支数；的分支数；（3）G的任一特征值的任一特征值 满足满足r;P G第八十二页，讲稿共九十一页哦v1v2v3v4第八十三页，讲稿共九十一页哦v1v2v3v4 0101-10110101-10010101-11010101-A G=A G-A G=A G-E=E=21234;22022P G 第八十四页，讲稿共九十一页哦思考题思考题.1.无向图无向图G如图所示。如图所示。写出写出G的邻接矩阵。的邻

46、接矩阵。01111011A=11001100第八十五页，讲稿共九十一页哦 求求G中长度为中长度为3的路的总数，其中有多少条回路。的路的总数，其中有多少条回路。45555455A=55225522 根据邻接矩阵求各结点的度数。根据邻接矩阵求各结点的度数。deg(v1)=3 deg(v2)=3 deg(v3)=2 deg(v4)=2第八十六页，讲稿共九十一页哦 求求G的可达性矩阵。的可达性矩阵。11111111P(G)=11111111第八十七页，讲稿共九十一页哦 求求G的完全关联矩阵。的完全关联矩阵。1110010011M(G)=0010101010 由完全关联矩阵求各结点的度数。由完全关联矩阵

47、求各结点的度数。deg(v1)=3 deg(v2)=3 deg(v3)=2 deg(v4)=2第八十八页，讲稿共九十一页哦3402000202002020004000 020002020000001000100001000001AA思考题：思考题：2.有向图有向图G如图所示。如图所示。写出写出G的邻接矩阵。的邻接矩阵。01101000A G=01010000 第八十九页，讲稿共九十一页哦 根据邻接矩阵求各结点的出度和入度。根据邻接矩阵求各结点的出度和入度。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的路的总数，其中有多少条回路。的路的总数，其中有多少条回路。311101101A=01100000共有共有8条，条，3条回路。条回路。第九十页，讲稿共九十一页哦 求求G的可达性矩阵。的可达性矩阵。0123333212311C=A+A+A+A=12210001 可达性矩阵可达性矩阵P=1111111111110001第九十一页，讲稿共九十一页哦