第九的基本概念及其矩阵表示

1、离散数学离散数学大连理工大学软件学院大连理工大学软件学院陈志奎陈志奎2第第9章章 图的基本概念及其矩阵表示论图的基本概念及其矩阵表示论3 图论（图论（Graph TheoryGraph Theory）是数学的一个）是数学的一个分支。它以图为研究对象。图论中的图是分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种接两点的线表示相应两个事物间具有这种关系。关系。

2、图论起源于著名的柯尼斯堡七桥问题。图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，中的岛及岛与河岸联结起来，如下图所示，A A、B B、C C，D D表示陆地。表示陆地。 4图论的起源图论的起源 哥尼斯堡七桥问题 ：17世纪的东普鲁士有一座哥尼斯堡（Konigsberg）城，城中有一条普雷格尔（Pregel）河，全城共有七座桥将河中的岛及岛与河岸联结起来，如下图所示，a,b,c,d表示陆地。 从四块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？5图论的起源图论的起源 1736年瑞

3、士大数学家列昂哈德欧拉（Leonhard Euler）解决了这一问题，他用了科学研究中最一般的方法抽象。用四个字母a,b,c,d表示四块陆地，并用7条线表示7座桥，从而将七桥问题抽象为图的问题，寻找经过图中每边一次且仅一次的回路，后来人们把有这样回路的图称为欧拉图。6图论的起源图论的起源 欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论的创始人。 欧拉被称为图论之父，1736年也被称为“图论元年”。 图论部分共分为三章：图的基本概念及其矩阵表示，几种图的介绍，树。本章将首先讨论图论中的一些基本概念，继之阐述图的基本性质，而后

4、介绍图的矩阵表示方法。7主要内容主要内容 图的基本概念图的基本概念 子图和图的运算子图和图的运算 路径、回路、连通性路径、回路、连通性 图的矩阵表示图的矩阵表示 欧拉图欧拉图 哈密尔顿图哈密尔顿图 二部图、平面图二部图、平面图 网络网络 树树基础知识特殊图89.1图的基本概念图的基本概念 图是由一些顶点和连接这些顶点的一些边所组成的离散结构。 根据连接顶点对的边的种类和数目的不同，图有多种类型。几乎每一门可以想到的学科，都有用图模型来解决的问题。9图的种类图的种类(1) 如果 ，则称 为无向图。(2) 如果 ，则称 为有向图。1212: ,Ev vvVvV,GV E :EVV,GV E 无论是

5、无向图还是有向图，都统称为图，其中V的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为图的阶。 可以用几何图形表示上面定义的图。用小圆圈可以用几何图形表示上面定义的图。用小圆圈表示结点。在无向图中，若表示结点。在无向图中，若 ，就用连接，就用连接结点结点v1和和v2的无向线段表示边的无向线段表示边e。在有向图中，。在有向图中，若若 ，就用，就用v1指向指向v2的有向线段表示边的有向线段表示边e。 12( ) ,ev v12( ),ev v 10图的基本概念图的基本概念定义：定义： 设无向图设无向图 ， ， ,GV E 12,e e eE12,v vV(1)如果 ，则称e与v1(或v

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

7、和e2邻接。 12图的基本概念图的基本概念例：有向图例：有向图v2和v1分别是e1的起点和终点，v2与v1邻接。 13图的基本概念图的基本概念定义：定义： 设图设图 ,e1和和e2是是G的两条不同的边。的两条不同的边。 ,GV E (1)如果与e1关联的两个结点相同，则称e1为自圈(或称环和回路)。 (2) 如果 ，则称e1与e2平行。(3)如果图G没有自圈，也没有平行边，则称G为简单图。 (4)如果图G没有自回路，有平行边，则称G为多重边图。(5)如果图G既有自回路，又有平行边，则称G为伪图。12( )( )ee14图的种类图的种类例：中国主要城市通讯图例：中国主要城市通讯图15图的种类图的

8、种类类型边允许平行边允许自环简单图无向否否多重图无向是否伪图无向是是有向图有向否是有向多重图有向是是16度度定义：定义： 。 (1)如果如果G是无向图，是无向图，G中与中与v关联的边和与关联的边和与v关关联的自回路的数目之和称为联的自回路的数目之和称为v的度的度(或次或次)，记，记为为(2) 。 (3)如果如果G是有向图，是有向图，G中以中以v为起点的边的数目为起点的边的数目称为称为v的出度，记为的出度，记为 ；G中以中以v为终点的为终点的边的数目称为边的数目称为v的入度，记为的入度，记为 ；v的出度的出度与入度之和称为与入度之和称为v的度，记为的度，记为 。 ( )Gdv( )Gdv( )G

9、dv注意，在计算无向图中结点的度时，自回路注意，在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。要考虑两遍，因为自回路也是边。 ,GV E( )Gdv17度度例：计算下图中各结点的度。例：计算下图中各结点的度。 v1 v2 v3123( )4 , ()()2GGGdvdvdv123142341234( )()()2( )0,()3()()()1( )2()()3()4DDDDDDDDDDDDdvdvdvdvdvdvdvdvdvdvdvdv18度度定理：在无向图中，所有节点的度数之和等于边定理：在无向图中，所有节点的度数之和等于边数的数的2倍。倍。 证：因为每条边给图G带来两度，设

10、图G有m条边，所以图G共有2m度，等于图G的所有结点的度数之和。 定理：在有向图中，所有顶点的度数之和等于定理：在有向图中，所有顶点的度数之和等于边的边的2倍；所有顶点的入度之和等于所有节点的倍；所有顶点的入度之和等于所有节点的出度之和，都等于边数。出度之和，都等于边数。度 例：结点的度。1920结点结点定义：度数为奇数的结点称为奇结点，度数定义：度数为奇数的结点称为奇结点，度数为偶数的结点称为偶结点。为偶数的结点称为偶结点。 定理：任何图都有偶数个奇结点。定理：任何图都有偶数个奇结点。 1Vv v为奇点2Vv v为偶点12( )( )( )2v Vv Vv Vd vd vd vm2( )v

11、Vd v1( )v Vd v1V定义：定义： 度为度为0的结点称为孤立结点，度为的结点称为孤立结点，度为1的结点称为端点。的结点称为端点。 21一些特殊的简单图一些特殊的简单图零图：结点都是孤立结点的图称为零图。零图：结点都是孤立结点的图称为零图。平凡图：一阶零图称为平凡图。平凡图：一阶零图称为平凡图。圈图（圈图（Cn(n3)）：是由）：是由n个顶点个顶点v1,v2,vn以及以及边边v1,v2,v2,v3,vn-1,vn,vn,v1组成的。组成的。22一些特殊的简单图一些特殊的简单图轮图：对轮图：对来说，当给圈图来说，当给圈图Cn添加一个顶点，添加一个顶点，并且把这个新顶点与并且把这个新顶点与

12、Cn里的里的n个顶点逐个连接，个顶点逐个连接，可以得到轮图可以得到轮图Wn。23一些特殊的简单图一些特殊的简单图正则图：正则图： 所有结点的度均为自然数所有结点的度均为自然数d的无向的无向图称为图称为d度正则图。度正则图。24一些特殊的简单图一些特殊的简单图nI完全无向图：设完全无向图：设 ，如果，如果n阶简单无向图阶简单无向图G是是n-1度正则图，则称度正则图，则称G为完全无向图，记为为完全无向图，记为Kn。注意：完全无向图的任意两个不同结点都邻接。注意：完全无向图的任意两个不同结点都邻接。一至五阶完全无向图 25一些特殊的简单图一些特殊的简单图注意：完全有向图的任意两个不同结点之间都注意：

13、完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接。有一对方向相反的有向边相连接。 完全有向图：设完全有向图：设 ，每个结点的出度和入度均，每个结点的出度和入度均为为n-1的的n阶简单有向图称为完全有向图。阶简单有向图称为完全有向图。nI 一至三阶完全有向图一至三阶完全有向图 26一些特殊的简单图一些特殊的简单图27特殊类型的图的一些应用特殊类型的图的一些应用局域网：在一座大楼里，像小型计算机和个人局域网：在一座大楼里，像小型计算机和个人电脑这样的计算机，以及像打印机这样的外设，电脑这样的计算机，以及像打印机这样的外设，可以用局域网来连接。有三种常见的局域网拓可以用局域网来连接。有

14、三种常见的局域网拓扑结构。扑结构。28图的同构图的同构 从图的定义可以看出，图的最本质的内容是结点和边的关联关系。两个表面上看起来不同的图，可能表达相同的结点和边的关联关系。29图的同构图的同构 实际中，利用图的同构可以研究是否有可能用同样的方式画两个图。例如化学里，表示过去已知化合物的图可以用来判定想象中的新化合物是否已经研究过了。30图的同构图的同构定义：设图定义：设图 和和 。如果存。如果存在双射在双射 和双射和双射 , 使得对于任意使得对于任意的的 ， 都满足都满足 , ,GV E,GV E:f VV:g EEeE12,v vV12121212(),()( ),(),()( ),f v

15、f vev vf vf vev v 若 若(g(e)则称G与G同构，记作 ，并称f和g为G和G之间的同构映射，简称同构。 GG31图的同构图的同构 换一种更简单的方法来描述：设图和图，若存在从到的双射函数f，对于V中所有的结点a和b来说，在G中有a到b的边当且仅当在G中有f(a)和f(b)的边，就说G与G同构。,GV E ,GVE 也就是说，两个同构的图有同样多的结点和边，并且映射f保持结点间的邻接关系，映射g保持边之间的邻接关系。 图同构的直观含义，是将其中一个图经过旋转、平移、拉伸等变形后与另一个图完全重合。32图的同构图的同构例：求证下图和同构。例：求证下图和同构。证明：两个图点、边的数

16、目都相同。设函数f为f(u1)=v1,f(u2)=v4,f(u3)=v3,f(u4)=v2。G中相邻的点是u1与u2，u2与u4，u4与u3，u3与u1，对应的像点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中相邻。因此，二图同构。33图的同构图的同构两个图同构必须满足的必要条件是：(1)顶点个数相同(2)边数相同(3)度数相同的顶点个数相同(4)K度顶点的导出子图同构判定图的同构比较难，但是却可以通过上述四点证明图不同构。34图的同构图的同构例：判断下列两图是否同构。例：判断下列两图是否同

17、构。35图的同构图的同构例：判断下列两图是否同构。例：判断下列两图是否同构。36 上面两个图不是同构的，因为左图中度结点都和两个度结点相关联，而右图中的度结点和一个度结点相关联还和一个度结点相关联。37图的同构图的同构例：判断下列两图是否同构。例：判断下列两图是否同构。38 上面两个图是同构的。我们只要构造双射函数 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是个双射函数,并且保持了边的邻接关系39图的同构图的同构 判定两个图是否同构，已知的最

18、好算法具有指数的最坏情形时间复杂度（对图的结点来说）。不过，解决这个问题的线性平均情形时间复杂度的算法已经找到，而且有希望找到判定两个图是否同构的多项式最坏情形时间复杂度算法。一个名叫NAUTY的最佳算法，目前可以在个人电脑上秒之内判定带有100个结点的两个图是否同构。40图模型图模型 图可以用在各种模型里，用于不同的行业。栖息地重叠图：顶点表示物种，若两个物种竞争栖息地重叠图：顶点表示物种，若两个物种竞争（他们共享某些食物来源），则用无向边连接表示（他们共享某些食物来源），则用无向边连接表示他们的顶点。他们的顶点。41图模型图模型熟人图：可以用模型表示人与人之间的各种关熟人图：可以用模型表示

19、人与人之间的各种关系。顶点表示人，当两个人互相认识时，用一系。顶点表示人，当两个人互相认识时，用一条无向边连接这两个人。据估计，世界上所有条无向边连接这两个人。据估计，世界上所有人的熟人图有超过人的熟人图有超过60亿个顶点和可能超过亿个顶点和可能超过1万万亿条边。亿条边。好莱坞图：好莱坞图用顶点表示演员，当两个好莱坞图：好莱坞图用顶点表示演员，当两个顶点的演员共同出演一部电影时，就用一条无顶点的演员共同出演一部电影时，就用一条无向边连接这两个顶点。根据无联网电影数据库，向边连接这两个顶点。根据无联网电影数据库，在在2001年年11月，好莱坞图有月，好莱坞图有574724个顶点和超个顶点和超过过

20、1600万条边，这些顶点所表示的演员出现在万条边，这些顶点所表示的演员出现在292609部电影中。部电影中。4243图模型图模型循环赛图：每个队其其他所有队各有一次的比赛称循环赛图：每个队其其他所有队各有一次的比赛称为循环赛。其中每个顶点表示每个队，若为循环赛。其中每个顶点表示每个队，若a队击败队击败b队，则有一条从队，则有一条从a指向指向b的有向边。的有向边。44图模型图模型合作图：合作图可以用来为学术论文的合作者关合作图：合作图可以用来为学术论文的合作者关系建立模型。顶点表示某个文章的某个作者系建立模型。顶点表示某个文章的某个作者（人），如果两个人合作论文，则用无向边连接（人），如果两个人

21、合作论文，则用无向边连接这两个人。已经发现在数学研究论文上合作的合这两个人。已经发现在数学研究论文上合作的合作图有超过作图有超过337000个顶点和个顶点和496000条边。条边。网络图：互联网可以用有向图来建模，用顶点表网络图：互联网可以用有向图来建模，用顶点表示网页，若有从网页示网页，若有从网页a指向网页指向网页b的链接，则做一的链接，则做一条从条从a指向指向b的有向边。网络图几乎是连续变化的，的有向边。网络图几乎是连续变化的，几乎每秒都有新页面产生而又有其他页面被删除。几乎每秒都有新页面产生而又有其他页面被删除。目前网络图有超过目前网络图有超过10亿个顶点和几百亿条边。许亿个顶点和几百亿

22、条边。许多研究者正在研究网络图的性质，以便更好的理多研究者正在研究网络图的性质，以便更好的理解网络的特性。解网络的特性。45图模型图模型优先图与并发处理：通过并发的执行某些语句，优先图与并发处理：通过并发的执行某些语句，计算机程序可能执行的更快。但重要的是，要计算机程序可能执行的更快。但重要的是，要避免语句执行时还要用到尚未执行语句的结果。避免语句执行时还要用到尚未执行语句的结果。语句与前面语句的相关性可以表示成有向图。语句与前面语句的相关性可以表示成有向图。用顶点表示某个语句，若在用顶点表示某个语句，若在a语句执行完之前不语句执行完之前不能执行能执行b语句，则引出一个从语句，则引出一个从a到

23、到b的有向边，这的有向边，这样的图称为优先图。样的图称为优先图。46图模型图模型479.2子图和图的运算子图和图的运算 定义：设定义：设 和和 为图。为图。 ,GV E ,GVE (1)如果 ，则称G是G的子图，记作 ，并称G是G的母图。(2)如果 ，则称G是G的真子图，记作 。(3)如果 ，则称G是G的生成子图。 ,VV EEGG,VV EEGG,VV EE平凡生成子图：对于图，平凡生成子图：对于图，G本身以本身以及零图都是及零图都是G的平凡生成子图。的平凡生成子图。,GV E ,GV 48子图子图定义：定义： 设图设图 ， 且且 。以。以V为结为结点集合，以起点和终点均在点集合，以起点和终

24、点均在V中的边的全体为边集中的边的全体为边集合的合的G的子图，称为由的子图，称为由V导出的导出的G的子图，记为的子图，记为GV。若。若 ，导出子图，导出子图 ，记为，记为 。 ,GV E VVV VVG VVG V 是从G中去掉V中的结点以及与这些结点关联的边而得到的图G的子图。 G V定义：设图定义：设图 ， 且且 ， 。以。以 为结点集合，以为结点集合，以 为边集合的为边集合的G的子图称为由的子图称为由E导出的子图。导出的子图。 ,GV E EEE |()()Vv vVe eEve 与 关联VE49子图子图 从图示看，图G的子图是图G的一部分，G的真子图的边数比G的边数少，G的生成子图与G

25、有相同的结点，G的导出子图 是G的以 为结点集合的最大子图。 G VV例：例：(b)是(a)的子图、真子图和生成子图，(c)是(a)的由1,2,3,4导出的子图。 子图5051图的运算图的运算定义：设图定义：设图 和和 同为无向图同为无向图或同为有向图。或同为有向图。 , ,GV E,GV E(1)如果对于任意 具有 ，则称G 和 是可运算的。(2)如果 ，则称G和 是不相交的。(3)如果 ，则称G和 是边不相交的。 eEE( )( )eeGVVEE GEE G52图的运算图的运算设图 和 为可运算的。 1111,GV E 2222,GV E (1)称以 为结点集合，以 为边集合的G1和G2的

26、公共子图为G1和G2的交，记为 。 (2)称以 为边集合，以与这些边关联的结点集合为点集的G1和G2的公共母图为G1和G2的并，记为 。 (3)称以 为结点集合，以 为边集合的 的子图为G1和G2的环和，记为 。 12EE12VV12GG12EE12VV12EE12GG12GG12GG图的运算图的运算5354图的运算图的运算并不是任何两个图都有交、并和环和。如上图 ，(a)和(b)没有交和并，因为边e1在(a)中连接v1和v2，而在(b)中连接v2和v3。 55图的运算图的运算定理：定理： 设图设图 和和 为可运算的。为可运算的。 1111,GV E 2222,GV E (1)如果 ，则存在唯

27、一的 。(2)存在唯一的 和 。12VV 12GG12GG12GG证：设证：设G1和和G2同为有向图，若同为无向图也可同为有向图，若同为无向图也可同样证明。同样证明。 (1)定义 为：对任意的 ， 。显然， .设图 和 均为G1和G2的交。因为 ，对任意 .因为 ，对任意 。这表明 。因此， 。 121212:() ()EEVVVV12eEE12( )( )( )eee121212(),(),VVEEGG 1212,GVV EE 1212,GVV EE1GG121,( )( )eEEee1GG121,( )( )eEEeeGG56图的运算图的运算证：证： （2）定义）定义 如下：如下： 121

28、212() ()EEVVVV12( )( )( )eee121eEeEE显然， 。设 和 均为G1和G2的并。因为 且 ，所以对任意 ， ，这表明 ，因此 。 121212,VV EEGG 1212,GVV EE1212,GVV EE1GG1GG1eE1( )( )( )eeeGG对于存在唯一的 可同样证明。 12GG57图的运算图的运算定义：定义： 设图设图 ,记记 为为 ，对任意，对任意 ，记，记 为为 。 ,GV EEE ,/()V EEEEGEeE GeGe 是从G中去掉E中的边所得到的G的子图。GE定义：设图定义：设图 和和 同为无向图同为无向图或同为有向图，并且边不相交，记或同为有

29、向图，并且边不相交，记 为为 。 ,GV E ,GVE GGGE 是由G增加E中的边所得到的图，其中 指出E中的边与结点的关联关系。GE58图的运算图的运算59上面的例子中，(a)和(b)分别为G1和G2 ,则图c,d,e分别是 (G1 G2)-v5,v6,(G1 G2)-g,h, G2 +E其中g=g,v1,v3图的运算图的运算609.3路径、回路和连通性路径、回路和连通性 61路径和回路路径和回路例：分析下列无向图例：分析下列无向图在该无向图中， 是路径，但不是简单路径； 是简单路径，但不是基本路径； 是闭路径，但不是简单闭路径。另外，如果从路径 中去掉闭路径 就得到基本路径 。 2342

30、3v bv dv ev bv2334v bv cv dv333v cv cv133v gv cv33v cv13v gv62路径和回路路径和回路例：分析下列有向图例：分析下列有向图在该有向图中， 是路径，但不是简单路径； 是简单路径，但不是基本路径。从 中去掉闭路径1a1就得到基本路径1c4。可以看出，从2至1存在多条路径，但从1至2没有路径。 1 4 1 4c b c1 1 4a c1 1 4a c63路径和回路路径和回路注意：注意：单独一个结点单独一个结点v也是路径，它是长度为也是路径，它是长度为0的基本路径。的基本路径。因此，任何结点到其自身总存在路径。因此，任何结点到其自身总存在路径。

31、在无向图中，若从结点在无向图中，若从结点v至结点至结点v存在路径，则从存在路径，则从v至至v必存在路径。而在有向图中，从结点必存在路径。而在有向图中，从结点v至至v结点存结点存在路径，而从在路径，而从v至至v却不一定存在路径。却不一定存在路径。 设路径 和 ，用P1P2记路径 10 1 11nnnPv evve v1111nmmmPv e vvev0 1 11111nnnmmmv evve v e vvev路径和回路路径和回路64例：例：“摆渡问题摆渡问题”：一个人带有一条狼、一头羊和：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一一捆白菜，要从河的左岸渡到右岸去，河上

32、仅有一条小船，而且只有人能划船，船上每次只能由人带条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？留下。问怎样安排摆渡过程？65路径和回路路径和回路解：河左岸允许出现的情况有以下解：河左岸允许出现的情况有以下10种情况：人狼种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这菜、羊及空（各物品已安全渡河），我们把这10种种状态视为状态视为10个点，若一种状态通过一次摆渡后变为个点，若一种状态通过

33、一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，另一种状态，则在两种状态（点）之间画一直线，得到上图。得到上图。这样摆渡问题就转化成在图中找出以这样摆渡问题就转化成在图中找出以“人狼羊菜人狼羊菜”为起点，以为起点，以“空空”为终点的简单路。容易看出，只为终点的简单路。容易看出，只有两条简单路符合要求，即：有两条简单路符合要求，即：（1）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空；人羊、空；（2）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。人羊、空。对于简单路（对于简单路（1）的安排为：人带

34、羊过河；人回来；）的安排为：人带羊过河；人回来；带狼过河；放下狼再将羊带回；人再带菜过河；人带狼过河；放下狼再将羊带回；人再带菜过河；人回来；带羊过河。回来；带羊过河。对于简单路（对于简单路（2）的安排为：人带羊过河；人回来；）的安排为：人带羊过河；人回来；带菜过河；放下菜再将羊带回；人再带狼过河；人带菜过河；放下菜再将羊带回；人再带狼过河；人回来；带羊过河。回来；带羊过河。上述的两种方案都是去上述的两种方案都是去4次、回次、回3次，且不会再有比次，且不会再有比这更少次数的渡河办法了。这更少次数的渡河办法了。66路径和回路路径和回路定理：定理： 设设v和和v是图是图G中的结点。如果存在从中的结

35、点。如果存在从v至至v的路径，则存在从的路径，则存在从v至至v的基本路径。的基本路径。 证：设当从证：设当从v至至v存在长度小于存在长度小于 的路径时，从的路径时，从v至至v必存在基本路径。必存在基本路径。如果存在路径如果存在路径 ，其中，其中 ，并且，并且有有i和和j满足满足 且且 ，则，则 是从是从v至至v的长度为的长度为l-j+i的路径。根据归纳假设，存的路径。根据归纳假设，存在从在从v至至v的基本路径。的基本路径。 0 1 11lllv evv ev0,lvv vv0ijl ijvv0 1 1111ijjlllv evvevv evl67路径和回路路径和回路定理：定理：n阶图中的基本路

36、径的长度小于或等于阶图中的基本路径的长度小于或等于n-1。 证：在任何基本路径中，出现于序列中的各结点都证：在任何基本路径中，出现于序列中的各结点都是互不相同的。在长度为是互不相同的。在长度为l的任何基本路径中，不的任何基本路径中，不同的结点数目是同的结点数目是l+1。因为集合。因为集合V仅有仅有n个不同的结个不同的结点，所以任何基本路径的长度不会大于点，所以任何基本路径的长度不会大于n-1。对于。对于长度为长度为l的基本循环来说，序列中有的基本循环来说，序列中有l个不同的结点。个不同的结点。因为是因为是n阶图，所以任何基本循环的长度，都不会阶图，所以任何基本循环的长度，都不会超过超过n，综上

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

38、出现两次外，其余结点和每条边都在该闭路径上恰出现一次。现一次。证：见书上。证：见书上。70路径和回路路径和回路71路径和回路路径和回路72路径和回路路径和回路例：判断图例：判断图 (a)有没有有向回路。有没有有向回路。73连通性连通性定义：设定义：设v1和和v2是图是图G的结点。如果在的结点。如果在G中存在中存在从从v1至至v2的路径，则称在的路径，则称在G中从中从v1可达可达v2或或v1和和v2是连通的，否则称在是连通的，否则称在G中从中从v1不可达不可达v2。对于图对于图G的结点，用的结点，用R(v)表示从表示从v可达的全体结可达的全体结点的集合。点的集合。 注意：在无向图中，若从注意：在

39、无向图中，若从v1可达可达v2，则从，则从v2必必可达可达v1；而在有向图中，从；而在有向图中，从v1可达可达v2不能保证不能保证从从v2必可达必可达v1。无论无向图还是有向图，任何。无论无向图还是有向图，任何节点到自身都是可达的。节点到自身都是可达的。 74连通性连通性75连通性连通性76连通性连通性77连通图连通图78连通图连通图无向图 是连通的，当且仅当对于任意 ， 。 ,GV E vV( )R vV79连通图连通图由于可达性的非对称性，有向图的连通概念要复杂得多，这里需要用到基础图的概念。 80连通图连通图定义：设定义：设G是有向图。是有向图。 (1)如果G中任意两个结点都互相可达，则

40、称G是强连通的。(2)如果对于G的任意两结点，必有一个结点可达另一个结点，则称G是单向连通的。(3)如果G的基础图是连通的，则称G是弱连通的。81子图和分支子图和分支定义：设定义：设G是是G的具有某种性质的子图，并且对于的具有某种性质的子图，并且对于G的具有该性质的任意子图的具有该性质的任意子图G，只要，只要GG，就有就有G=G，则称，则称G相对于该性质是相对于该性质是G的极大子图。的极大子图。 定义：定义： 无向图无向图G的极大连通子图称为的极大连通子图称为G的分支的分支 。定义：设定义：设G是有向图：是有向图：（1）G的极大强连通子图称为G的强分支。（2）G的极大单向连通子图称为G的单向分

41、支。（3）G的极大弱连同子图称为G的弱分支。82子图和分支子图和分支定理：连通无向图恰有一个分支。非连通无向定理：连通无向图恰有一个分支。非连通无向图有一个以上分支。图有一个以上分支。 定理：强连通（单向连通，弱连通）有向图恰定理：强连通（单向连通，弱连通）有向图恰有一个强分支（单向分支，弱分支）；非强连有一个强分支（单向分支，弱分支）；非强连通（非单向连通，非弱连通）有向图有一个以通（非单向连通，非弱连通）有向图有一个以上强分支（单向分支，弱分支）。上强分支（单向分支，弱分支）。 83子图和分支子图和分支例：例：有4个强分支，即 123123112 , ,v v ve e eev v2233

42、31456, , , , ,ev vev vvvv 每个结点恰处于一个强分支中，而边 不在任何强分支中。G有两个单向分支，即 和 。显然， 处于两个单向分支中，G只有一个弱分支，即其本身。 456,e e e6 Gv56 ,G v v5v84子图和分支子图和分支 注意：注意： 无向图的每个结点和每条边都恰在一个连无向图的每个结点和每条边都恰在一个连通分支中；有向图中，并不是每个边都恰通分支中；有向图中，并不是每个边都恰在一个强分支中。在一个强分支中。 在简单有向图中，每个结点每条边都恰在在简单有向图中，每个结点每条边都恰在一个弱分支中。一个弱分支中。 在简单有向图中，每个结点每条边至少位在简单

43、有向图中，每个结点每条边至少位于一个单项分支中。于一个单项分支中。85由结点集合v1，v2，v3，v4，v5，v6和v7形成的诱导子图都是强分图;由结点集合v1，v2，v3，v4，v5，v7，v4，v5和v6，v5所成的诱导子图都是单向分图；由结点集合v1，v2，v3，v4，v5，v6，v7形成的诱导子图是弱分图。子图和分支子图和分支86资源分配图资源分配图 下面给出简单有向图的一个应用资源分配图。 在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资

44、源，它要发出请求，操作系统必须保证这一请求得到满足。87死锁状态死锁状态 对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。88假设条件假设条件 假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。89分析分析 令Pt = p1，p2，pm表示计算机系统在时间t的程序集合，Qt Pt是运行的程序集合，或者说在时刻t至少分配一部分所请求的资源的程序集合。Rt

45、= r1，r2，rn是系统在时刻t的资源集合。资源分配图Gt = 是有向图，它表示了时间t系统中资源分配状态。把每个资源ri看作图中一个结点，其中i=1，2，n。表示有向边，E当且仅当程序pkPt已分配到资源ri且等待资源rj。90分析（续）分析（续）例如，令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=如图16.2.7所示。能够证明，在时刻t计算机系统处于死锁状态iff资源分配图Gt中包含强连通图

46、。91前例资源分配图前例资源分配图92割集割集有时删除一个结点和它所关联的边，就产生带有比原图更多的连通分支的子图。把这样的结点称为割点。有时删除一条边，就产生带有比原图更多的连通分支的子图，把这样的边叫做割边或者桥。939.4图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵定义： 设 是一个简单有向图，其中的结点集合 ，并且假定各结点已经有了从结点v1到vn的次序。试定义一个nn的矩阵A，使得其中的元素 , ,GV E12 ,nVv vvi j1 ,vvEjvvEija当i (1)0 当则称这样的矩阵A是图G的邻接矩阵。 94邻接矩阵邻接矩阵定义：元素或为定义：元素或为0或为或为1的任何矩阵，都称

47、为比特矩的任何矩阵，都称为比特矩阵或布尔矩阵。阵或布尔矩阵。 邻接矩阵也是布尔矩阵，第i行上值为1的元素的个数，等于结点vi的出度；第j列上值为1的元素的个数，等于结点vj的入度。 95邻接矩阵邻接矩阵图的邻接矩阵不具有唯一性。对于给定简单有向图 来说，其邻接矩阵依赖于集合V中的各元素间的次序关系。,GV E 给定两个有向图和相对应的邻接矩阵，如果首先在一个图的邻接矩阵中交换一些行，而后交换相对应的各列，从而有一个图的邻接矩阵，能够求得另外一个图的邻接矩阵，则事实上这样的两个有向图，必定是互为同构的。 96邻接矩阵邻接矩阵例：写出下图的邻接矩阵，并计算各个节点的出度例：写出下图的邻接矩阵，并计

48、算各个节点的出度和入度。和入度。解：首先给各结点安排好一个解：首先给各结点安排好一个次序，譬如说是次序，譬如说是 。得出邻接矩阵如下：得出邻接矩阵如下： 12345,v v v v v12345123450100000100010111000011010vvvvvvvAvvv97邻接矩阵邻接矩阵上例中，如果重新把各结点排列成 ，就能写出另外一个矩阵如下： 52341,v v v v v52341523410101100100110100000101000vvvvvvvAvvv 98邻接矩阵邻接矩阵 对于给定图G，显然不会因结点编序不同而使其结构会发生任何变化，即图的结点所有不同编序实际上仍表示

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

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

51、j列上的 元素， 是矩阵中的第i行和第j列上的元素(i,j)。于是，对于 来说，有 TBAAija( , )i jijb,1,2,3,i jn1nijikjkkba a如果边 ，则有 ，如果边 ，则有 。对于某一个确定的k来说，如 果 和 都是给定图的边，则在表示 的上述求和表达式中，应该引入基值1。从结点vi和vj二者引出的边，如果能共同终止于一些结点的话，那么这样的一些结点的数目，就是元素 的值。 ,ikv vE1ika ,jkv vE1jka,ikv v,jkv vijbijb103 在图上的意义在图上的意义TBAA例：如图，求例：如图，求TAA解：解：简单算法：原矩阵A中，第i行和第j

52、行相交，有几个1，AAT的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的出度。12345123450100000100010111000011010vvvvvvvAvvv12345123450001110101010000010100100TvvvvvvvAvvv1010101000103020001110213TAA104 在图上的意义在图上的意义TCA A设 是邻接矩阵A中的(i,j)元素； 是矩阵C中的元素。于是，对于 ijaijc1,2, ,in1nijkikjkCa a对于某一个确定的k来说，如果 都是给定图的边，则在上式中应引入基值1。可得从图中的一些点所引出的边，如果能

53、够同时终止于结点vi和vj的话，那么这样的一些结点的数目，就是元素Cij的值。 ,kikjv vv v 105 在图上的意义在图上的意义例：如图，求例：如图，求TA A解：解：简单算法：原矩阵A中，第i列和第j列相交，有几个1，ATA的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的入度。TCA A12345123450100000100010111000011010vvvvvvvAvvv12345123450001110101010000010100100TvvvvvvvAvvv2101013021001001202101011TA A106邻接矩阵的幂邻接矩阵的幂对于 来说，考察邻

54、接矩阵A的幂An可知，邻接矩阵A中的第i行和第j列上的元素值1，说明了图G中存在一条边，也就是说，存在一条从结点vi到vj长度为1的路径。试定义矩阵A2，使得A2中的各元素 为 2,3,4,n 2ija12nijikkjkaa a元素值 等于从vi到vj长度为2的不同路径的数目。显然，矩阵中主对角线上的元素 的值，表示了结点 上长度为2的循环的个数。矩阵A3中的元素值(i,j)依次类推。2ija2iia(1,2, )iv in107邻接矩阵的幂邻接矩阵的幂例：例：2300100010110101121110,211101311101000001001110002111AA45211101311

55、11311123321,233213634301011211102222135232AA108邻接矩阵的幂邻接矩阵的幂定理：设定理：设 是一简单有向图，并且是一简单有向图，并且A是是G的的邻接矩阵。对于邻接矩阵。对于 来说，矩阵来说，矩阵Am中的元中的元素素(i,j)的值，等于从的值，等于从vi到到vj长度为长度为m的路径数目。的路径数目。 ,GV E 1,2,3,m 证：对于证：对于m进行归纳证明。当进行归纳证明。当m=1时，由邻接矩阵时，由邻接矩阵的定义中能够得到的定义中能够得到Am=A。设矩阵。设矩阵Ak中的元素中的元素(i,j)值值 是是 ，且对于，且对于m=k来说结论为真。因来说结论

56、为真。因为为 ，所以应有，所以应有 kija1kkAA A11nijikkjkkkaaa 是从结点是从结点vi出发，经过结点出发，经过结点vk到到vj的长的长度为度为k+1的各条路径的数目。这里的各条路径的数目。这里vk是倒数第是倒数第二个结点。因此，二个结点。因此， 应是从结点应是从结点vi出发，经出发，经过任意的倒数第二个结点到过任意的倒数第二个结点到vj的长度为的长度为k+1的的路径总数。因此，对于路径总数。因此，对于m=k+1，定理成立。，定理成立。 kikkjaa1kija109邻接矩阵的幂邻接矩阵的幂根据上述定理，可得出结论：能使矩阵Am中的元素(i,j)值是非零的最小正整数m，就

57、是距离 。对于 和 来说，如果矩阵 中的(i,j)元素值和(j,i)元素值都为0，那么就不会有任何路径连通结点vi和vj。因此，结点vi和vj必定是属于图G的不同分图。 ,ijd v v1,2,1mnijmA110邻接矩阵的幂邻接矩阵的幂例：给定一个简单有向图例：给定一个简单有向图 ，如下图所示，如下图所示，其中的结点集合其中的结点集合 。试求出图。试求出图G的邻接的邻接矩阵矩阵A和和A的幂的幂A2，A3,A4。 ,GV E 12345 ,Vv v v v v0100010100010000000100010A111邻接矩阵的幂解：20101000200010100000100001A3020

58、0020200020000000100010A42020004000202000001000001A112可达性矩阵可达性矩阵 给定一个简单有向图 ，并且设结 点 。可知，由图G的邻接矩阵A能够直接确定G中是否存在一条从vi到vj的边。设 ，由矩阵 能够求得从结点vi到vj长度为r的路径数目。试构成矩阵 , ,GV E,ijv vVrIkA2kkBAAA矩阵Bk的(i,j)元素值表示了从结点vi到vj长度小于或等于r的路径数目。当图中的结点数目为n时，矩阵Bn都能够提供足够的信息，以表明从图中的任何结点到其它结点的可达性。 113可达性矩阵可达性矩阵定义：定义： 给定一个简单有向图给定一个简单

59、有向图 ，其中，其中|V|=n，并且假定并且假定G中的各结点是有序的。试定义一个中的各结点是有序的。试定义一个nn的路径矩阵的路径矩阵P，使得其元素为，使得其元素为 ,GV E 1 0 ijijijvvPvv如果从 到 至少存在一条路径如果从 到 不存在任何路径 路经矩阵P仅表明了图中的任何结点偶对之间是否至少存在一条路径，以及在任何结点上存在循环与否；它并不能指明存在的所有路径。 114可达性矩阵可达性矩阵例：试构成下列有向图的路径矩阵例：试构成下列有向图的路径矩阵P。 解：设邻接矩阵解：设邻接矩阵A=A1。在前面的。在前面的例中，已经求出过矩阵的幂例中，已经求出过矩阵的幂A2，A3和和A4

60、, A5。求出矩阵。求出矩阵B5和路径矩和路径矩阵阵P如下：如下： 5363431 1 1 1 1586531 1 1 1 1,9148951 1 1 1 1232221 1 1 1 16116641 1 1 1 1BP115可达性矩阵可达性矩阵注意：注意：对于具有对于具有n个结点的图而言，长度为个结点的图而言，长度为n的路径不可能的路径不可能是基本路径。是基本路径。 假定图中的每一个结点，从它本身出发总是可达的，假定图中的每一个结点，从它本身出发总是可达的，由矩阵由矩阵Bn-1构成路径矩阵构成路径矩阵P，或由矩阵，或由矩阵Bn构成路径构成路径矩阵矩阵P，这两种方法都可以采纳。，这两种方法都可