图的基本概念及其矩阵表示.ppt

《图的基本概念及其矩阵表示.ppt》由会员分享，可在线阅读，更多相关《图的基本概念及其矩阵表示.ppt（128页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学大连理工大学软件学院大连理工大学软件学院陈志奎陈志奎2 2/128/128第第9章章 图的基本概念及其矩阵表示论图的基本概念及其矩阵表示论3/128/128 图论（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。4 4/128/128图论的起源图论的起源哥尼斯堡七桥问题：17

2、世纪的东普鲁士有一座哥尼斯堡（Konigsberg）城，城中有一条普雷格尔（Pregel）河，全城共有七座桥将河中的岛及岛与河岸联结起来，如下图所示，a,b,c,d表示陆地。从四块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？5 5/128/128图论的起源图论的起源 1736年瑞士大数学家列昂哈德欧拉（LeonhardEuler）解决了这一问题，他用了科学研究中最一般的方法抽象。用四个字母a,b,c,d表示四块陆地，并用7条线表示7座桥，从而将七桥问题抽象为图的问题，寻找经过图中每边一次且仅一次的回路，后来人们把有这样回路的图称为欧拉图。6/128/128图论的起源图论的

3、起源 欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论的创始人。欧拉被称为图论之父，1736年也被称为“图论元年”。图论部分共分为三章：图的基本概念及其矩阵表示，几种图的介绍，树。本章将首先讨论图论中的一些基本概念，继之阐述图的基本性质，而后介绍图的矩阵表示方法。7 7/128/128主要内容主要内容图的基本概念图的基本概念子图和图的运算子图和图的运算路径、回路、连通性路径、回路、连通性图的矩阵表示图的矩阵表示欧拉图欧拉图哈密尔顿图哈密尔顿图二部图、平面图二部图、平面图网络网络树树基础知识特殊图8 8/128/1289.1图

4、的基本概念图的基本概念图是由一些顶点和连接这些顶点的一些边所组成的离散结构。根据连接顶点对的边的种类和数目的不同，图有多种类型。几乎每一门可以想到的学科，都有用图模型来解决的问题。9 9/128/128图的种类图的种类(1)如果，则称为无向图。(2)如果，则称为有向图。无论是无向图还是有向图，都统称为图，其中V的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为图的阶。可以用几何图形表示上面定义的图。用小圆圈表示结点。在无向图中，若，就用连接结点v1和v2的无向线段表示边e。在有向图中，若，就用v1指向v2的有向线段表示边e。1010/128/128图的基本概念图的基本概念定义：定义

5、：设无向图，(1)如果，则称e与v1(或v2)互相关联。e连接v1和v2，v1和v2既是e的起点，也是e的终点，也称v1和v2为点邻接点邻接。(2)如果两条不同的边e1和e2与同一个结点关联，则称e1和e2为边邻接边邻接。也就是说，共边的点称为点邻接；共点的边称为边邻接。1111/128/128图的基本概念图的基本概念定义：定义：设有向图。如果，则称e连接v1和v2，e与v1(或v2)互相关联，分别称v1和v2是e的起点和终点，也称v1和v2邻接。例：例：无向图e1连接v1和v2，v1和v2邻接，e1和e2邻接。1212/128/128图的基本概念图的基本概念例：例：有向图v2和v1分别是e1

6、的起点和终点，v2与v1邻接。1313/128/128图的基本概念图的基本概念定义：定义：设图,e1和e2是G的两条不同的边。(1)如果与e1关联的两个结点相同，则称e1为自圈(或称环和回路)。(2)如果，则称e1与e2平行。(3)如果图G没有自圈，也没有平行边，则称G为简单图。(4)如果图G没有自回路，有平行边，则称G为多重边图。(5)如果图G既有自回路，又有平行边，则称G为伪图。1414/128/128图的种类图的种类例：例：中国主要城市通讯图1515/128/128图的种类图的种类类型边允许平行边允许自环简单图无向否否多重图无向是否伪图无向是是有向图有向否是有向多重图有向是是1616/1

7、28/128度度定义：定义：。(1)如果如果G是无向图，是无向图，G中与中与v关联的边和与关联的边和与v关联关联的自回路的数目之和称为的自回路的数目之和称为v的度的度(或次或次)，记为，记为 。(1)如果如果G是有向图，是有向图，G中以中以v为起点的边的数目为起点的边的数目称为称为v的出度，记为的出度，记为 ；G中以中以v为终点的为终点的边的数目称为边的数目称为v的入度，记为的入度，记为 ；v的出度的出度与入度之和称为与入度之和称为v的度，记为的度，记为 。注意，在计算无向图中结点的度时，自回路要注意，在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。考虑两遍，因为自回路也是边。1

8、717/128/128度度例：例：计算下图中各结点的度。1818/128/128度度定理定理：在无向图中，所有节点的度数之和等于边数的2倍。证：因为每条边给图G带来两度，设图G有m条边，所以图G共有2m度，等于图G的所有结点的度数之和。定理：定理：在有向图中，所有顶点的度数之和等于边的2倍；所有顶点的入度之和等于所有节点的出度之和，都等于边数。度例：结点的度。19/128/1282020/128/128结点结点定义：定义：度数为奇数的结点称为奇结点奇结点，度数为偶数的结点称为偶结点偶结点。定理：定理：任何图都有偶数个奇结点。定义：定义：度为0的结点称为孤立结点孤立结点，度为1的结点称为端点端点

9、。2121/128一些特殊的简单图一些特殊的简单图零图：零图：结点都是孤立结点的图称为零图零图。平凡图：平凡图：一阶零图称为平凡图平凡图。圈图（圈图（Cn(n3)）：）：是由n个顶点v1,v2,vn以及边v1,v2,v2,v3,vn-1,vn,vn,v1组成的。2222/128一些特殊的简单图一些特殊的简单图轮图：轮图：对来说，当给圈图Cn添加一个顶点，并且把这个新顶点与Cn里的n个顶点逐个连接，可以得到轮图Wn。2323/128一些特殊的简单图一些特殊的简单图正则图：正则图：所有结点的度均为自然数d的无向图称为d d度正则图度正则图。2424/128一些特殊的简单图一些特殊的简单图完全无向图

10、：完全无向图：设，如果n阶简单无向图G是n-1度正则图，则称G为完全无向图完全无向图，记为Kn。注意：注意：完全无向图的任意两个不同结点都邻接。一至五阶完全无向图2525/128一些特殊的简单图一些特殊的简单图注意：注意：完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接。完全有向图：完全有向图：设，每个结点的出度和入度均为n-1的n阶简单有向图称为完全有向图完全有向图。一至三阶完全有向图2626/128一些特殊的简单图一些特殊的简单图2727/128特殊类型的图的一些应用特殊类型的图的一些应用局域网：局域网：在一座大楼里，像小型计算机和个人电脑这样的计算机，以及像打印机这样的外设

11、，可以用局域网来连接。有三种常见的局域网拓扑结构。2828/128/128图的同构图的同构从图的定义可以看出，图的最本质的内容是结点和边的关联关系。两个表面上看起来不同的图，可能表达相同的结点和边的关联关系。2929/128/128图的同构图的同构实际中，利用图的同构可以研究是否有可能用同样的方式画两个图。例如化学里，表示过去已知化合物的图可以用来判定想象中的新化合物是否已经研究过了。3030/128/128图的同构图的同构定义：定义：设图和。如果存在双射和双射,使得对于任意的，都满足则称G与G同构，记作，并称f和g为G和G之间的同构映射同构映射，简称同构。3131/128/128图的同构图的

12、同构换一种更简单的方法来描述：设图和图，若存在从到的双射函数f，对于V中所有的结点a和b来说，在G中有a到b的边当且仅当在G中有f(a)和f(b)的边，就说G与G同构。也就是说，两个同构的图有同样多的结点和边，并且映射f保持结点间的邻接关系，映射g保持边之间的邻接关系。图同构的直观含义，是将其中一个图经过旋转、平移、拉伸等变形后与另一个图完全重合。3232/128/128图的同构图的同构例：例：求证下图和同构。证明：两个图点、边的数目都相同。设函数f为f(u1)=v1,f(u2)=v4,f(u3)=v3,f(u4)=v2。G中相邻的点是u1与u2，u2与u4，u4与u3，u3与u1，对应的像点

13、f(u1)=v1与f(u2)=v4,f(u2)=v4与f(u4)=v2,f(u4)=v2与f(u3)=v3,f(u3)=v3与f(u1)=v1在H中相邻。因此，二图同构。3333/128/128图的同构图的同构两个图同构必须满足的必要条件是：(1)顶点个数相同(2)边数相同(3)度数相同的顶点个数相同(4)K度顶点的导出子图同构判定图的同构比较难，但是却可以通过上述四点证明图不同构。3434/128/128图的同构图的同构例：例：判断下列两图是否同构。3535/128/128图的同构图的同构例：例：判断下列两图是否同构。3636/128/128上面两个图不是同构的，因为左图中度结点都和两个度结

14、点相关联，而右图中的度结点和一个度结点相关联还和一个度结点相关联。3737/128/128图的同构图的同构例：例：判断下列两图是否同构。38/128/128上面两个图是同构的。我们只要构造双射函数f:a1,b1,c1,d1,e1,f1a2,b2,c2,d2,e2,f2并且f(a1)=f2 ,f(b1)=b2,f(c1)=c2 f(d1)=d2,f(e1)=a2 ,f(f1)=e2 f是个双射函数,并且保持了边的邻接关系3939/128/128图的同构图的同构判定两个图是否同构，已知的最好算法具有指数的最坏情形时间复杂度（对图的结点来说）。不过，解决这个问题的线性平均情形时间复杂度的算法已经找到

15、，而且有希望找到判定两个图是否同构的多项式最坏情形时间复杂度算法。一个名叫NAUTY的最佳算法，目前可以在个人电脑上秒之内判定带有100个结点的两个图是否同构。4040/128/128图模型图模型图可以用在各种模型里，用于不同的行业。栖息地重叠图：栖息地重叠图：顶点表示物种，若两个物种竞争（他们共享某些食物来源），则用无向边连接表示他们的顶点。4141/128/128图模型图模型熟人图：熟人图：可以用模型表示人与人之间的各种关系。顶点表示人，当两个人互相认识时，用一条无向边连接这两个人。据估计，世界上所有人的熟人图有超过60亿个顶点和可能超过1万亿条边。好莱坞图：好莱坞图：好莱坞图用顶点表示演

16、员，当两个顶点的演员共同出演一部电影时，就用一条无向边连接这两个顶点。根据无联网电影数据库，在2001年11月，好莱坞图有574724个顶点和超过1600万条边，这些顶点所表示的演员出现在292609部电影中。42/128/1284343/128/128图模型图模型循环赛图循环赛图：每个队其其他所有队各有一次的比赛称为循环赛。其中每个顶点表示每个队，若a队击败b队，则有一条从a指向b的有向边。4444/128/128图模型图模型合作图：合作图：合作图可以用来为学术论文的合作者关系建立模型。顶点表示某个文章的某个作者（人），如果两个人合作论文，则用无向边连接这两个人。已经发现在数学研究论文上合作

17、的合作图有超过337000个顶点和496000条边。网络图网络图：互联网可以用有向图来建模，用顶点表示网页，若有从网页a指向网页b的链接，则做一条从a指向b的有向边。网络图几乎是连续变化的，几乎每秒都有新页面产生而又有其他页面被删除。目前网络图有超过10亿个顶点和几百亿条边。许多研究者正在研究网络图的性质，以便更好的理解网络的特性。4545/128/128图模型图模型优先图与并发处理：优先图与并发处理：通过并发的执行某些语句，计算机程序可能执行的更快。但重要的是，要避免语句执行时还要用到尚未执行语句的结果。语句与前面语句的相关性可以表示成有向图。用顶点表示某个语句，若在a语句执行完之前不能执行

18、b语句，则引出一个从a到b的有向边，这样的图称为优先图。4646/128/128图模型图模型4747/1289.2子图和图的运算子图和图的运算 定义：定义：设和为图。(1)如果，则称G是G的子图子图，记作，并称G是G的母图母图。(2)如果，则称G是G的真子图真子图，记作。(3)如果，则称G是G的生成子图。平凡生成子图：平凡生成子图：对于图，G本身以及零图都是G的平凡生成子图。4848/128子图子图定义定义：设图，且。以V为结点集合，以起点和终点均在V中的边的全体为边集合的G的子图，称为由V导出的G的子图，记为GV。若，导出子图，记为。是从G中去掉V中的结点以及与这些结点关联的边而得到的图G的

19、子图。定义：定义：设图，且，。以为结点集合，以为边集合的G的子图称为由E导出的子图。4949/128子图子图从图示看，图G的子图是图G的一部分，G的真子图的边数比G的边数少，G的生成子图与G有相同的结点，G的导出子图是G的以为结点集合的最大子图。例：例：(b)是(a)的子图、真子图和生成子图，(c)是(a)的由1,2,3,4导出的子图。子图50/1285151/128图的运算图的运算定义：定义：设图和同为无向图或同为有向图。(1)如果对于任意具有，则称G和是可运算的可运算的。(2)如果，则称G和是不相交不相交的的。(3)如果，则称G和是边不相交的边不相交的。5252/128图的运算图的运算设图

20、和为可运算的。(1)称以为结点集合，以为边集合的G1和G2的公共子图为G1和G2的交，记为。(2)称以为边集合，以与这些边关联的结点集合为点集的G1和G2的公共母图为G1和G2的并，记为。(3)称以为结点集合，以为边集合的的子图为G1和G2的环和，记为。图的运算图的运算53/1285454/128图的运算图的运算并不是任何两个图都有交、并和环和。如上图，(a)和(b)没有交和并，因为边e1在(a)中连接v1和v2，而在(b)中连接v2和v3。5555/128图的运算图的运算定理：定理：设图和为可运算的。(1)如果，则存在唯一的。(2)存在唯一的和。证：证：设G1和G2同为有向图，若同为无向图也

21、可同样证明。(1)定义为：对任意的，。显然，.设图和均为G1和G2的交。因为，对任意.因为，对任意。这表明。因此，。5656/128图的运算图的运算证证：（2）定义如下：显然，。设和均为G1和G2的并。因为且，所以对任意，这表明，因此。对于存在唯一的可同样证明。5757/128图的运算图的运算定义：定义：设图,记为，对任意，记为。是从G中去掉E中的边所得到的G的子图。定义：定义：设图和同为无向图或同为有向图，并且边不相交，记为。是由G增加E中的边所得到的图，其中指出E中的边与结点的关联关系。5858/128图的运算图的运算5959/128上面的例子中，(a)和(b)分别为G1和G2,则图c,d

22、,e分别是(G1 G2)-v5,v6,(G1 G2)-g,h,G2+E其中g=g,v1,v3图的运算图的运算6060/1289.3路径、回路和连通性路径、回路和连通性 6161/128路径和回路路径和回路例：例：分析下列无向图在该无向图中，是路径，但不是简单路径；是简单路径，但不是基本路径；是闭路径，但不是简单闭路径。另外，如果从路径中去掉闭路径就得到基本路径。6262/128路径和回路路径和回路例：例：分析下列有向图在该有向图中，是路径，但不是简单路径；是简单路径，但不是基本路径。从中去掉闭路径1a1就得到基本路径1c4。可以看出，从2至1存在多条路径，但从1至2没有路径。6363/128路

23、径和回路路径和回路注意：注意：单独一个结点v也是路径，它是长度为0的基本路径。因此，任何结点到其自身总存在路径。在无向图中，若从结点v至结点v存在路径，则从v至v必存在路径。而在有向图中，从结点v至v结点存在路径，而从v至v却不一定存在路径。设路径和，用P1P2记路径路径和回路路径和回路64/128例：例：“摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？65/128路径和回路路径和回路解：解：河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊

24、、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，得到上图。这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的简单路。容易看出，只有两条简单路符合要求，即：（1）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空；（2）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。对于简单路（1）的安排为：人带羊过河；人回来；带狼过河；放下狼再将羊带回；人再带菜过河；人回来；带羊过河。对于简单路（2）的安排为：人带羊过河；人回来；带菜过河；放下菜再将羊带回；人再带狼过河；

25、人回来；带羊过河。上述的两种方案都是去4次、回3次，且不会再有比这更少次数的渡河办法了。6666/128路径和回路路径和回路定理：定理：设v和v是图G中的结点。如果存在从v至v的路径，则存在从v至v的基本路径。证：证：设当从v至v存在长度小于的路径时，从v至v必存在基本路径。如果存在路径，其中，并且有i和j满足且，则是从v至v的长度为l-j+i的路径。根据归纳假设，存在从v至v的基本路径。l6767/128路径和回路路径和回路定理：定理：n阶图中的基本路径的长度小于或等于n-1。证：证：在任何基本路径中，出现于序列中的各结点都是互不相同的。在长度为l的任何基本路径中，不同的结点数目是l+1。因

26、为集合V仅有n个不同的结点，所以任何基本路径的长度不会大于n-1。对于长度为l的基本循环来说，序列中有l个不同的结点。因为是n阶图，所以任何基本循环的长度，都不会超过n，综上所述，在n阶图中，基本路径的长度不会超过n-1。6868/128路径和回路路径和回路路径可以表示很多图模型中的有用信息：熟人关系图中的通路（最小世界原理）合作图中的通路（数学家的埃德斯数）好莱坞图中的通路（演员的培根数（著名演员凯文.培根）69/128路径和回路路径和回路定理：定理：设v是图G的任意结点，G是回路或有向回路，当且仅当G的阶与边数相等，并且在G中存在这样一条从v到v的闭路径，使得除了v在该闭路径中出现两次外，

27、其余结点和每条边都在该闭路径上恰出现一次。证：证：见书上。70/128路径和回路路径和回路71/128路径和回路路径和回路72/128路径和回路路径和回路例：例：判断图(a)有没有有向回路。7373/128连通性连通性定义：定义：设v1和v2是图G的结点。如果在G中存在从v1至v2的路径，则称在G中从v1可达可达v2或v1和v2是连通的连通的，否则称在G中从v1不可达不可达v2。对于图G的结点，用R(v)表示从v可达的全体结点的集合。注意：注意：在无向图中，若从v1可达v2，则从v2必可达v1；而在有向图中，从v1可达v2不能保证从v2必可达v1。无论无向图还是有向图，任何节点到自身都是可达的

28、。7474/128连通性连通性7575/128连通性连通性7676/128连通性连通性7777/128连通图连通图7878/128连通图连通图无向图是连通的，当且仅当对于任意，。7979/128连通图连通图由于可达性的非对称性，有向图的连通概念要复杂得多，这里需要用到基础图的概念。8080/128连通图连通图定义：定义：设G是有向图。(1)如果G中任意两个结点都互相可达，则称G是强强连通的连通的。(2)如果对于G的任意两结点，必有一个结点可达另一个结点，则称G是单向连通的单向连通的。(3)如果G的基础图是连通的，则称G是弱连通的弱连通的。8181/128子图和分支子图和分支定义：定义：设G是G

29、的具有某种性质的子图，并且对于G的具有该性质的任意子图G，只要GG，就有G=G，则称G相对于该性质是G的极大子图极大子图。定义：定义：无向图G的极大连通子图称为G的分支分支。定义：定义：设G是有向图：（1）G的极大强连通子图称为G的强分支强分支。（2）G的极大单向连通子图称为G的单向分支单向分支。（3）G的极大弱连同子图称为G的弱分支弱分支。8282/128子图和分支子图和分支定理：定理：连通无向图恰有一个分支。非连通无向图有一个以上分支。定理：定理：强连通（单向连通，弱连通）有向图恰有一个强分支（单向分支，弱分支）；非强连通（非单向连通，非弱连通）有向图有一个以上强分支（单向分支，弱分支）。

30、8383/128子图和分支子图和分支例：例：有4个强分支，即每个结点恰处于一个强分支中，而边不在任何强分支中。G有两个单向分支，即和。显然，处于两个单向分支中，G只有一个弱分支，即其本身。8484/128子图和分支子图和分支注意：注意：无向图的每个结点和每条边都恰在一个连通分支中；有向图中，并不是每个边都恰在一个强分支中。在简单有向图中，每个结点每条边都恰在一个弱分支中。在简单有向图中，每个结点每条边至少位于一个单项分支中。8585/128由结点集合v1，v2，v3，v4，v5，v6和v7形成的诱导子图都是强分图;由结点集合v1，v2，v3，v4，v5，v7，v4，v5和v6，v5所成的诱导子

31、图都是单向分图；由结点集合v1，v2，v3，v4，v5，v6，v7形成的诱导子图是弱分图。子图和分支子图和分支8686/128资源分配图资源分配图下面给出简单有向图的一个应用资源分配图。在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。8787/128死锁状态死锁状态对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲

32、突的请求必须解决，资源分配图有助发现和纠正死锁。8888/128假设条件假设条件假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。8989/128分析分析令Pt=p1，p2，pm表示计算机系统在时间t的程序集合，Qt Pt是运行的程序集合，或者说在时刻t至少分配一部分所请求的资源的程序集合。Rt=r1，r2，rn是系统在时刻t的资源集合。资源分配图Gt=是有向图，它表示了时间t系统中资源分配状态。把每个资源ri看作图中一个结点，其中i=1，2，n。表示有向边，E当且仅当程序pkPt已分

33、配到资源ri且等待资源rj。9090/128分析（续）分析（续）例如，令Rt=r1，r2，r3，r4，Qt=p1，p2，p3，p4。资源分配状态是：p1占用资源r4且请求资源r1，p2占用资源r1且请求资源r2和r3，p3占用资源r2且请求资源r3，p4占用资源r3且请求资源r1和r4，于是，可得到资源分配图Gt=如图所示。能够证明，在时刻t计算机系统处于死锁状态iff资源分配图Gt中包含强连通图。9191/128前例资源分配图前例资源分配图9292/128割集割集有时删除一个结点和它所关联的边，就产生带有比原图更多的连通分支的子图。把这样的结点称为割点。有时删除一条边，就产生带有比原图更多的

34、连通分支的子图，把这样的边叫做割边或者桥。9393/1289.4图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵定义：设是一个简单有向图，其中的结点集合，并且假定各结点已经有了从结点v1到vn的次序。试定义一个nn的矩阵A，使得其中的元素则称这样的矩阵A是图G的邻接矩阵。9494/128邻接矩阵邻接矩阵定义：定义：元素或为0或为1的任何矩阵，都称为比特矩比特矩阵阵或布尔矩阵布尔矩阵。邻接矩阵也是布尔矩阵，第i行上值为1的元素的个数，等于结点vi的出度；第j列上值为1的元素的个数，等于结点vj的入度。9595/128邻接矩阵邻接矩阵图的邻接矩阵不具有唯一性。对于给定简单有向图来说，其邻接矩阵依赖于集合

35、V中的各元素间的次序关系。给定两个有向图和相对应的邻接矩阵，如果首先在一个图的邻接矩阵中交换一些行，而后交换相对应的各列，从而有一个图的邻接矩阵，能够求得另外一个图的邻接矩阵，则事实上这样的两个有向图，必定是互为同构的。9696/128邻接矩阵邻接矩阵例：例：写出下图的邻接矩阵，并计算各个节点的出度和入度。解：解：首先给各结点安排好一个次序，譬如说是。得出邻接矩阵如下：9797/128邻接矩阵邻接矩阵上例中，如果重新把各结点排列成，就能写出另外一个矩阵如下：9898/128邻接矩阵邻接矩阵对于给定图G，显然不会因结点编序不同而使其结构会发生任何变化，即图的结点所有不同编序实际上仍表示同一个图。

36、换句话说，这些结点的不同编序的图都是同构的，并且它们的n！个邻接矩阵都是相似的。今后将略去这种由于V中结点编序而引起邻接矩阵的任意性。而取该图的任一个邻接矩阵作为该图的矩阵表示。9999/128邻接矩阵邻接矩阵由邻接矩阵判断有向图的性质：如果有向图是自反的，则邻接矩阵的主对角线上的各元素，必定都是1。如果有向图是反自反的，则邻接矩阵的主对角线上的各元素，必定都是0。对于对称的有向图来说，其邻接矩阵也是对称的，也就说，对于所有的i和j而言，都应有aij=aji。如果给定有向图是反对称的，则对于所有的i和j和ij而言，aij=1蕴含aji=0。100100/128邻接矩阵邻接矩阵可以把简单有向图的

37、矩阵表示的概念，推广到简单无向图、多重边图和加权图。对于简单无向图来说，这种推广会给出一个对称的邻接矩阵，在多重边图或加权图的情况下，可以令其中的wij，或者是边的重数，或者是边的权。另外，若，则。在零图的邻接矩阵中，所有元素都应该是0，亦即其邻接矩阵是个零矩阵。101101/128邻接矩阵邻接矩阵逆图的邻接矩阵：如果给定的图是一个简单有向图，并且其邻接矩阵是A，则图G的逆图的邻接矩阵是A的转置。对于无向图或者对称的有向图来说，应有。102102/128在图上的意义在图上的意义定义矩阵。设是邻接矩阵中的第i行和第j列上的元素，是矩阵中的第i行和第j列上的元素(i,j)。于是，对于来说，有如果边

38、，则有，如果边，则有。对于某一个确定的k来说，如果和都是给定图的边，则在表示的上述求和表达式中，应该引入基值1。从结点vi和vj二者引出的边，如果能共同终止于一些结点的话，那么这样的一些结点的数目，就是元素的值。103103/128在图上的意义在图上的意义例：例：如图，求解：解：简单算法：原矩阵A中，第i行和第j行相交，有几个1，AAT的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的出度。104104/128在图上的意义在图上的意义设是邻接矩阵A中的(i,j)元素；是矩阵C中的元素。于是，对于对于某一个确定的k来说，如果都是给定图的边，则在上式中应引入基值1。可得从图中的一些点所引出

39、的边，如果能够同时终止于结点vi和vj的话，那么这样的一些结点的数目，就是元素Cij的值。105105/128在图上的意义在图上的意义例：例：如图，求解：解：简单算法：原矩阵A中，第i列和第j列相交，有几个1，ATA的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的入度。106106/128邻接矩阵的幂邻接矩阵的幂对于来说，考察邻接矩阵A的幂An可知，邻接矩阵A中的第i行和第j列上的元素值1，说明了图G中存在一条边，也就是说，存在一条从结点vi到vj长度为1的路径。试定义矩阵A2，使得A2中的各元素为元素值等于从vi到vj长度为2的不同路径的数目。显然，矩阵中主对角线上的元素的值，表示

40、了结点上长度为2的循环的个数。矩阵A3中的元素值(i,j)依次类推。107107/128邻接矩阵的幂邻接矩阵的幂例：例：108108/128邻接矩阵的幂邻接矩阵的幂定理：定理：设是一简单有向图，并且A是G的邻接矩阵。对于来说，矩阵Am中的元素(i,j)的值，等于从vi到vj长度为m的路径数目。证：证：对于m进行归纳证明。当m=1时，由邻接矩阵的定义中能够得到Am=A。设矩阵Ak中的元素(i,j)值是，且对于m=k来说结论为真。因为，所以应有 是从结点vi出发，经过结点vk到vj的长度为k+1的各条路径的数目。这里vk是倒数第二个结点。因此，应是从结点vi出发，经过任意的倒数第二个结点到vj的长

41、度为k+1的路径总数。因此，对于m=k+1，定理成立。109109/128邻接矩阵的幂邻接矩阵的幂根据上述定理，可得出结论：能使矩阵Am中的元素(i,j)值是非零的最小正整数m，就是距离。对于和来说，如果矩阵中的(i,j)元素值和(j,i)元素值都为0，那么就不会有任何路径连通结点vi和vj。因此，结点vi和vj必定是属于图G的不同分图。110110/128邻接矩阵的幂邻接矩阵的幂例：例：给定一个简单有向图，如下图所示，其中的结点集合。试求出图G的邻接矩阵A和A的幂A2，A3,A4。111/128邻接矩阵的幂解：112112/128可达性矩阵可达性矩阵给定一个简单有向图，并且设结点。可知，由图

42、G的邻接矩阵A能够直接确定G中是否存在一条从vi到vj的边。设，由矩阵能够求得从结点vi到vj长度为r的路径数目。试构成矩阵矩阵Bk的(i,j)元素值表示了从结点vi到vj长度小于或等于r的路径数目。当图中的结点数目为n时，矩阵Bn都能够提供足够的信息，以表明从图中的任何结点到其它结点的可达性。113113/128可达性矩阵可达性矩阵定义：定义：给定一个简单有向图，其中|V|=n，并且假定G中的各结点是有序的。试定义一个nn的路径矩阵路径矩阵P，使得其元素为路经矩阵P仅表明了图中的任何结点偶对之间是否至少存在一条路径，以及在任何结点上存在循环与否；它并不能指明存在的所有路径。114114/12

43、8可达性矩阵可达性矩阵例：例：试构成下列有向图的路径矩阵P。解：解：设邻接矩阵A=A1。在前面的例中，已经求出过矩阵的幂A2，A3和A4,A5。求出矩阵B5和路径矩阵P如下：115115/128可达性矩阵可达性矩阵注意：注意：对于具有n个结点的图而言，长度为n的路径不可能是基本路径。假定图中的每一个结点，从它本身出发总是可达的，由矩阵Bn-1构成路径矩阵P，或由矩阵Bn构成路径矩阵P，这两种方法都可以采纳。116116/128可达性矩阵可达性矩阵首先构成矩阵，而后由他们构成矩阵Bn，再由矩阵Bn构成路径矩阵P，太麻烦了。为了减少计算工作量，应该设法使得不产生这些不必要的信息。生成路径矩阵的简单

44、方法：生成路径矩阵的简单方法：布尔矩阵法。布尔和和布尔积：布尔和和布尔积：对于两个nn的布尔矩阵A和B，A和B的布尔和是,A和B的布尔积是，并分别称为矩阵C和D，它们也都是布尔矩阵。把矩阵C和D的元素分别定义成117117/128可达性矩阵可达性矩阵邻接矩阵A是个布尔矩阵。路径矩阵P也是个布尔矩阵。对于来说，令于是，可以把路径矩阵P表示成注意：注意：A(m)表示布尔矩阵，如果从vi到vj有长度为m的路径的话，矩阵中(i,j)元素为1；Am中(i,j)元素表示从vi到vj的长度为m的路径的个数。118118/128可达性矩阵可达性矩阵例：例：对于下述的有向图来说，试求出矩阵A(2),A(3),A

45、(4),A(5)和P。119/128可达性矩阵可以用不同的方法解释矩阵。在简单有向图中，应有，因此可以把集合E看成是V中的二元关系。邻接矩阵A是关系E的关系矩阵。在第四章中，曾经把合成关系曾经把合成关系 定义定义成这样一种关系：如果存在一个结点成这样一种关系：如果存在一个结点vk，能使，能使viEvk和和vkEvj，则必有，则必有viE2vj。换句话说，从vi到vj如果至少存在一条长度为2的路径的话，那么E2的关系矩阵中的(i,j)元素值是1。这就说明了，矩阵A(2)是关系E2的关系矩阵。与此类似，A(3)是V中的关系的关系矩阵，类推。设E1和E2是V中的两种关系，并且A1和A2分别是E1和E

46、2的关系矩阵。于是,关系和的关系矩阵分别是和。120120/128闭包闭包对于集合V中的关系E来说，E的可传递闭包E+应是可传递闭包E+的关系矩阵应为：式中的A是关系E的关系矩阵。如果|V|=n，则图中的基本路径或基本循环的长度不会超过n。因此可见，矩阵A+与路径矩阵P相同。计算关系的可传递闭包等同于计算对应关系图的路径矩阵。121121/128可达性矩阵判断强分图可达性矩阵判断强分图由由路径矩阵P可以求得含有给定图的任何特定结点的强分图。设是一个简单有向图，并且G。P是图G的路径矩阵，PT是矩阵P的转置。设矩阵P中的(i,j)元素为Pij，而矩阵PT中的(i,j)元素为PijT。试定义一个矩

47、阵，使得它的(i,j)元素为。于是，矩阵中的第i行，就确定了含有结点vi的强分图。122122/128可达性矩阵判断强分图可达性矩阵判断强分图123123/128利用简单有向图的可达矩阵，能够确定某过程是否为递归的。假设VPrg=p1，p2，pn是程序Prg中的过程集合，做有向图G=，其中piVPrg，i=1，2，n；E iff pi调用pj。如果图G中有包含pi的回路，则断言pi是递归的。为此，由图G的邻接矩阵A=(aij)计算出关系矩阵A+=(aij)。如果A+中的主对角线上的某元素 =1，则pi是递归的可达性矩阵判断递归过程可达性矩阵判断递归过程124124/128例如，已知程序Prg中的过程集合VPrg=p1，p2，p3，p4，p5，其过程的调用关系可表成下图所示的有向图，该图的邻接矩阵A为。A=可达性矩阵判断递归过程可达性矩阵判断递归过程125125/128于是可求得于是可求得A A+:A A+=由此可知，由此可知，p p2 2，p p4 4和和p p5 5是递归的。是递归的。可达性矩阵判断递归过程可达性矩阵判断递归过程126/128关联矩阵127127/128/128关联矩阵例，例，求下图所示的有向图的关联矩阵。128128/128/128关联矩阵