离散数学第九章图的基本概念及其矩阵表示.ppt

《离散数学第九章图的基本概念及其矩阵表示.ppt》由会员分享，可在线阅读，更多相关《离散数学第九章图的基本概念及其矩阵表示.ppt（91页珍藏版）》请在三一文库上搜索。

1、,第九章 图的基本概念及其矩阵表示,离散数学 陈志奎主编 人民邮电出版社,前言,图论（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。,前言,图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有7座桥将河中的岛及岛与河岸联结起来，如下图所示，a、

2、b、c、d表示陆地。 从4块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？1736年瑞士大数学家列昂哈德欧拉（Leonhard Euler）解决了这一问题，他用了科学研究中最一般的方法抽象。用四个字母a，b，c，d表示4块陆地，并用7条线表示7座桥，从而将七桥问题抽象为图的问题，寻找经过图中每边一次且仅一次的回路，后来人们把有这样回路的图称为欧拉图。,图论的起源,前言,图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立

3、图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。 图论部分共分为三章：图的基本概念及其矩阵表示，几种图的介绍，树。,图论的起源,图的基本概念,主要内容,子图和图的运算,路径、回路和连通性,图的矩阵表示,9.1 图的基本概念,图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的方法也可

4、以用来描述其他的问题。 当我们考察交通路线时，可以用点来代表城市，用线来表示两城市间有道路通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图的这种表示方式中可以抽象出图的数学概念来。,6,图的定义,9.1 图的基本概念,定义9.1 设一个三元组 ， ， ，其中 是一个非空的节点集合， 是有限的边集合，如果 是从边集合 E 到点集合 V 中的无序偶映射，即 ，则称 为无向图。 在无向图中，如果 ，则称 e 连接 和 ， 和 既是 e 的起点，也是 e 的终点，也称 和 为

5、点邻接。如果两条不同的边 和 与同一个结点连接，则称 和 为边邻接。,7,图的定义,9.1 图的基本概念,定义9.1 设一个三元组 ， ， ，其中 是一个非空的节点集合， 是有限的边集合，如果 是从边集合 E 到点集合 V 中的有序偶映射，即 ，则称 为无向图。 在有向图中，如果 ，则称e连接 和 ，分别称 和 是 e 的起点和终点，也称 和 邻接。,8,图的定义,9.1 图的基本概念,无论是无向图还是有向图，都统称为图，其中 V 的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为图的阶。 我们可以用几何图形表示上面定义的图。用小圆圈表示结点。在无向图中，若 ，就用连接结点 和 的

6、无向线段表示边 g。在有向图中，若 ，就用 指向 的有向线段表示边 e。,9,图的定义,9.1 图的基本概念,例9.1 无向图 和有向图 分别示于图9.1和图9.2。在图9.1中， 连接 和 ， 和 邻接， 和 邻接。在图9.2中， 和 分别是 的起点和终点， 与 邻接。,10,图9.1,图9.2,9.1 图的基本概念,定义9.3 设图 ， e1和e2是G的两条不同的边。 （1）如果与e1连接的两个结点相同，则称e1为自回路或环。 （2）如果 ，则称e1与e2平行。 （3）如果图G没有自回路，也没有平行边，则称G为简单图。 （4）如果图G没有自回路，有平行边，则称G为多重边图。 （5）如果图G

7、既有自回路，又有平行边，则称G为伪图。,11,在有向图中，如果两条边连接的结点相同，但方向相反，它们也不是平行边。,9.1 图的基本概念,12,例9.2 中国主要城市通讯图如图9.3所示：当数据量很小时，可采用单线通讯如图（a）所示；数据量很大时，两点之间往往要连接多条线路如图（b）所示。为了诊断本地故障也可采用自环连接如图（c）所示；有时数据可以不是双向传输，沈阳只接收数据不发送数据如图（d）所示（有向图允许有自环）；数据量大时也可采用多重有向图如图（e）所示。,9.1 图的基本概念,简单图是一类非常重要的图。在某些图论著作中，把我们定义的简单图称为图，而把允许有平行边的图称为多重边图，把我

8、们定义的图称为伪图。 从图的定义可以看出，图的最本质的内容是结点和边的关联关系。两个表面上看起来不同的图，可能表达了相同的结点和边的关联关系。如图9.4的两个图，不仅结点和边的数目相同，而且结点和边的关联关系也相同。为了说明这种现象，我们引进两个图同构的概念。,13,9.1 图的基本概念,定义9.4 设图 和 。如果存在双射 和双射 ，使得对于任意的 ， 都满足 则称G与 同构，记作 ，并称f和g为G和 之间的同构映射，简称同构。 两个同构的图有同样多的结点和边，并且映射 保持结点间的邻接关系，映射 保持边之间的邻接关系。,14,同构映射,9.1 图的基本概念,定义9.5 设 。 （1）如果

9、G 是无向图，G 中与 v关联的边和与 v 关联的自回路的数目之和称为 v 的度（Degree），记为 。 （2）如果 G 是有向图，G 中以 v为起点的边的数目称为 v 的出度（Out Degree），记为 ；G 中以 v 为终点的边的数目称为 v 的入度（In Degree），记为 ；v 的出度与入度之和称为 v的度（Degree），记为 ，显然 =,15,节点的度,在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。,9.1 图的基本概念,例9.3 在图9.5所示的无向图中， ， ， ， 。在图9.6所示的有向图D中 ， 1， 图9.5 图9.6 显然，每增加一条边，都使图中所

10、有结点的度数之和增加2。,16,9.1 图的基本概念,定理9.1 在无向图中，所有节点的度数之和等于边数的2倍。 证明：因为每条边（包括环）给图带来两度，图有m条边，所以图共有2m度，等于图的所有结点的度数之和。 定理9.2 在有向图中，所有顶点的度数之和等于边的2倍；所有顶点的入度之和等于所有节点的出度之和，都等于边数。 证明：因为每条边（包括环）给图带来两度（一个出度和一个入度），图有 m 条边，所以图共有 2m 度（m个入度和 m 个出度），等于图的所有结点的度数之和。,17,9.1 图的基本概念,18,9.1 图的基本概念,定义9.6 度数为奇数的结点称为奇结点，度数为偶数的结点称为偶

11、结点。 推论9.1 任何图都有偶数个奇结点。 证明：设 ， ，则 因为 是偶数，所以 也是偶数， 而 中每个点 v 的度 均为奇数，因此 为偶数。,19,9.1 图的基本概念,定义9.7 设 是图 的结点集，称 为 G 的度序列。如图9. 5的度序列为 3,4,4,1,0，图9.6的度序列是 3,4,3,2。 定义9.8 度为0的结点称为孤立结点，度为1的结点称为端点。,20,9.1 图的基本概念,定义9.9 定义以下图： （1）结点都是孤立结点的图称为零图。 （2）一阶零图称为平凡图。 （3）由n个顶点v1,v2,vn(n3)以及边v1,v2,v2,v3,vn-1,vn,vn,v1组成的图（

12、Cn）称为圈图，如图9.7。,21,图的定义,图9.7 圈图,9.1 图的基本概念,定义9.9 定义以下图： （4）对n来说，当给圈图Cn添加一个顶点，并且把这个新顶点与Cn里的n个顶点逐个连接，可以得到轮图（Wn），如图9.8。 图9.8 轮图,22,图的定义,9.1 图的基本概念,定义9.9 定义以下图： （5）所有结点的度均为自然数 的无向图称为 度正则图，如图9.9。 3度、4度正则图,23,图的定义,9.1 图的基本概念,定义9.9 定义以下图： （6）设 ，如果 n 阶简单无向图 G是 n-1 度正则图，则称 G 为完全无向图，记为 。如图9.10。 图9.10 1至5阶完全无向图

13、,24,图的定义,9.1 图的基本概念,定义9.9 定义以下图： （7）设 ，每个结点的出度和入度均为 n-1的 n 阶简单有向图称为完全有向图，如图9.11。 图9.11 1至3阶完全有向图,25,图的定义,显然，完全无向图的任意两个不同结点都邻接，完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接。,9.1 图的基本概念,定理9.3 n个节点的无向完全图 的边数为 。 证明：因为在无向完全图 中，任意两个节点之间都有边相连，所以 n个节点中任取两个点的组合数为 ，故无向完全图 的边数为 。 如果在 中，对每条边任意确定一个方向，就称该图为 n 个节点的有向完全图。显然，有向完全

14、图的边数也是 。,26,图的基本概念,主要内容,子图和图的运算,路径、回路和连通性,图的矩阵表示,9.2 子图和图的运算,定义9.10 设 和 为图。 （1）如果 ，则称 是 G 的子图，记作 ，并称 G 是 的母图。 （2）如果 ，则称 是 G 的真子图，记作 （3）如果 ，则称 是 G 的生成子图。,28,子图和补图,9.2 子图和图的运算,定义9.11 设图 ， 且 。以 为结点集合，以起点和终点均在 中的边的全体为边集合的 G 的子图，称为由 导出的 G 的子图，记为 。若 ，导出子图 ，记为 。 是从 G 中去掉 中的结点以及与这些结点关联的边而得到的图 G的子图。,29,子图和补图

15、,9.2 子图和图的运算,定义9.11 设图 ， 且 ，以 为结点集合，以 为边集合的 G 的子图称为由 导出的子图。 显然，从图示看，图 G 的子图是图 G的一部分，G 的真子图的边数比 G 的边数少，G 的生成子图与 G有相同的结点，G 的导出子图 是 G 的以 为结点集合的最大子图。,30,子图和补图,9.2 子图和图的运算,例9.5 在图9.12中，图(b)是图(a) 的子图、真子图和生成子图，图(c)是图(a) 的由 1,2,3,4 导出的子图。 图9.12 图和子图,31,子图和补图,9.2 子图和图的运算,定义9.13 设 n阶无向图 是 n阶完全无向图 的生成子图，则称 为 G

16、 的补图，记为 。 显然，简单无向图都有补图，并且一个简单无向图的每个补图都是同构的。对于任意两个简单无向图 和 ，如果 是 的补图，那么 也是 的补图。例如，在图9.13中(a)和(b)互为补图。,32,子图和补图,图9.13 互补的图,9.2 子图和图的运算,定义9.14 设图 和 同为无向图或同为有向图。 （1）如果对于任意 具有 ，则称 G 和 是可运算的。 （2）如果 ，则称 G 和 是不相交的。 （3）如果 ，则称 G 和 是边不相交的。,33,子图和补图,9.2 子图和图的运算,定义9.15 设图 和 为可运算的。 （1）称以 为结点集合，以 为边集合的 和 的公共子图为 和 的

17、交，记为 （2）称以 为结点集合，以 为边集合的 和 的公共母图为 和 的并，记为 。 （3）称以 为结点集合，以 为边集合的 的子图为 和 的环和，记为,34,子图和补图,9.2 子图和图的运算,例9.6 在图9.14中，(a)和(b)分别为 和 ，则图c、d、e分别是 、 和,35,子图和补图,9.2 子图和图的运算,定理9.4 设图 和 为可运算的。 （1）如果 ，则存在唯一的 （2）存在唯一的 和 图9.15 不可运算的图,36,子图和补图,9.2 子图和图的运算,定义9.16 设图 ，记 为 ，对任意 ，记 为 是从 G 中去掉 中的边所得到的 G 的子图。 定义9.17 设图 和

18、同为无向图或同为有向图，并且边不相交，记 为 是由G增加 中的边所得到的图，其中 指出 中的边与结点的关联关系。,37,子图和补图,9.2 子图和图的运算,例9.7 设图9.16中的(a)和(b)分别为 和 ，则(c)，(d)，(e)分别是 ，其中 ，,38,子图和补图,9.2 子图和图的运算,例9.7 设图9.16中的(a)和(b)分别为 和 ，则(c)，(d)，(e)分别是 ，其中 ，,39,子图和补图,图的基本概念,主要内容,子图和图的运算,路径、回路和连通性,图的矩阵表示,9.3 路径、回路和连通性,计算机网络中常见的一个问题是网络中任何两台计算机是否可以通过计算机间的信息传递而使其资

19、源共享？我们可以用图论的方法对这个问题进行研究，其中用结点表示计算机，用边表示通讯连线，因此，计算机的信息资源共享问题就变为图中任何两个结点之间是否都有连接路径存在？,41,9.3 路径、回路和连通性,定义9.18 设 是图，从图中结点 到 的一条路径或通路是图的一个点、边的交错序列 ，其中 (或者 ) , , 分别称为通路的起点和终点，路径中包含的边数n称为路径的长度,当起点和终点重合时则称其为闭路径。 在上述定义路径与回路中，节点和边不受限制，即节点和边都可以重复出现。下面我们讨论路径与回路中节点和边受限的情况。,42,9.3 路径、回路和连通性,定义9.19 如果 中出现的边 互不相同，

20、则称该路径为简单路径。闭的简单路径称为回路。如果出现的点 互不相同，则称该路径是基本路径。基本路径中除了起点和终点相同外，别无相同的结点，则称为圈。 例9.8 在图9.17所示的无向图中， 是路径，但不是简单路径； 是简单路径，但不是基本路径； 是闭路径，但不是简单闭路径。,43,9.3 路径、回路和连通性,例9.9 在图9.18所示的有向图中， 是路径，但不是简单路径； 是简单路径，但不是基本路径。从 中去掉闭路径 就得到基本路径 。可以看出，从3至1存在多条路径，从1至3也存在多条路径。 由路径的定义知道，单独一个结点v也是路径，它是长度为0的基本路径。因此，任何结点到其自身总存在路径。

21、在无向图中，若从结点v至结点v 存在路径，则从v 至v必存在路径。而在有向图中，从结点v至结点v 存在路径，而从v 至v却不一定存在路径。,44,9.3 路径、回路和连通性,例9.10 “摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？ 解：河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）

22、之间画一直线，得到图9.19。,45,摆渡问题,9.3 路径、回路和连通性,定理9.5 设v和v是图G中的结点。如果存在从v至v的路径，则存在从v至v的基本路径。,46,9.3 路径、回路和连通性,定理9.6 n阶图中的基本路径的长度小于或等于 。,47,9.3 路径、回路和连通性,定理9.7 设v是图G的任意结点，G是回路或有向回路，当且仅当G的阶与边数相等，并且在G中存在这样一条从v到v的闭路径，使得除了v在该闭路径中出现两次外，其余结点和每条边都在该闭路径上恰出现一次。,48,9.3 路径、回路和连通性,定义9.20 如果回路（有向回路，无向回路）C是图G的子图，则称G有回路（有向回路，

23、无向回路）C。 定理9.8 如果有向图G有子图G满足：对于G的任意结点v， 则G有有向回路。,49,9.3 路径、回路和连通性,定理9.9 如果有向图G有子图G满足：对于G中的任意结点v， 则G有有向回路。 例9.11 为判断图9.20的(a)有没有有向回路，我们依次得到图9.20的 。由(g)是平凡图知(a)没有有向回路。(a)不是非循环图，因为它的所有结点的度均大于1。,50,9.3 路径、回路和连通性,定义9.21 设v1和v2是图G的结点。如果在G中存在从v1至v2的路径，则称在G中从v1可达v2或v1和v2是连通的，否则称在G中从v1不可达v2。对于图G的结点v，我们用R(v)表示从

24、v可达的全体结点的集合。 在无向图中，若从v1可达v2，则从v2必可达v1；而在有向图中，从v1可达v2不能保证从v2必可达v1。无论无向图还是有向图，任何节点到自身都是可达的。,51,9.3 路径、回路和连通性,例9.12 在图9.20所示的无向图中，存在路径v1av2bv3所以v1可达 v3， v3也可达 v1 ，从v1 可达的全体节点的集合 =,52,9.3 路径、回路和连通性,例9.13 在图9.22所示的有向图中，存在路径 所以1可达4。从2可达的全体节点的集合 =,53,9.3 路径、回路和连通性,定义9.22 设v1和v2是图G的结点。如果从v1至v2是可达的，则在从v1至v2的

25、路径中，长度最短的称为从v1至v2的测地线，并称该测地线的长度为从v1至v2的距离，记作 。如果从v1不可达v2，则称从v1至v2的距离 为 应该说明，对于任何结点 来说，总是假定 ，另外，从结点vi 至vj 的距离 具有下列性质。 对于任何结点来 来说，都应有 （1） （2） （3） 不等式（3），通常称为三角不等式，如果结点vi到vj 是可达的，并且从vj 到vi也是可达的，但是 却不一定等于 ，这一点读者应予注意。,54,9.3 路径、回路和连通性,定义9.23 图 的直径定义为 例9.14 在图9.23所示的有向图中， =1， =1， =1， =2。 + ，且,55,9.3 路径、回路

26、和连通性,定义9.24 设图 ， ，其中R+是正实数集合，则称 为加权图。对任意 称为边e 的加权长度。路径中所有边的加权长度之和称为该路径的加权长度。从结点 至 的路径中，加权长度最小的称为从 至 的最短路径。若从 可达 ,则称从 至 最短路径的加权长度为从 至 加权距离；若从 不可达 ，则称从 至 的加权距离为 在图论的实际应用中，常常需要从一结点至另一结点的加权距离。 图的连通性分为无向图的连通性和有向图的连通性。而且有向图的连通性要比无向图的连通性复杂些。下面讨论图的重要性质连通性。,56,9.3 路径、回路和连通性,定义9.25 若无向图G中任意两个结点都可达的，则称G是连通的。规定

27、平凡图是连通的。 显然，无向图 是连通的，当且仅当对于任意 ， 易知，无向图G中，结点之间的连通关系是等价关系。设G为一无向图，R是 中结点之间的连通关系，由 R 可将 划分成 个等价类，记作 ，由它们导出的导出子图 称为 G 的连通分支(Connected Component)，其个数应为,57,9.3 路径、回路和连通性,例9.16 图9.25所示的（a）为无向连通图， =1。（b）为无向非连通图， =3。 图9.25 无向图 由于可达性的非对称性，有向图的连通概念要复杂得多，这里需要用到基础图的概念。,58,9.3 路径、回路和连通性,定义9.26 设有向图 ，若略去G中各有向边的方向后得到无向图D，则称D为有向图G的基础图。 例9.17 图9.26所示，有向图（a）的基础图为无向图（b）。 图9.26 基础图,59,