第十一章图与树.ppt
《第十一章图与树.ppt》由会员分享,可在线阅读,更多相关《第十一章图与树.ppt(141页珍藏版)》请在三一文库上搜索。
1、第十一章 图与树,先来研究我们班同学名字中有相同汉字的问题。如果我们把每个同学用平面上的点来表示,谁与谁有相同汉字则在其对应的节点之间连一条边,于是这样就构成一个图。,我们再来看看代表图论的起源的哥尼斯堡七桥问题。哥尼斯堡(后来的加里宁格勒)位于立陶宛的普雷格尔河畔。河中有两个小岛,为方便交通,在河两岸及两个小岛之间建有七座小桥(如图11. l(a)所示)。城中居民经常来此游逛,随即提出了这样一个有趣的问题:游人是否可能从两岸或小岛的一处出发,经由每座桥一次且仅一次,然后回到原地。许多人久而不得其解,直到1736年瑞士数学家欧拉(Euler)解决了这一问题。但欧拉只用一个十分简明而又很有代表性
2、的方法 - 抽象为一张图(如图11.1(b)所示),并进而研究一般的图何时有这样的解。图11.1(b)中的小圆圈叫做结点,用以表示河两岸及两个小岛;结点间的线段或弧线叫做边,用以表示小桥,如果游人可以作出所要求的那种游历,那么必可从图的某一结点出发,经过每条边一次且仅经过一次后又回到原节点。这时,对每个结点而言,每进入一次,总相应地要离开一次,而每次离开不得重复同一条边,因而它应当与偶数条边相联结。由于图11.1之(b)中并非每个结点都与偶数条边相联结,因此欧拉作出结论:游人不可能作出所要求的游历。,像如上这样由结点和联结结点的边所组成的离散结构就是本章所要讨论的图。这种图与我们以前学过的平面
3、几何图形和立体几何图形不同,即它表示的往往是一个事物集中事物之间的关系,上例的图就分别描述的是我们班同学名字集合上的有相同汉字的关系,以及地点集合上有桥的关系。,因此,图可用来解决许多领域的问题。如生态环境里不同物种的竞争、在人事组织里谁影响谁、比赛结果等都可以用图来表示。而网络中两台计算机是否有通信链路连接、区别分子式相同但结构不同的两种化合物、动物群中存在的食物链、如何根据需要安排考试、分配电视台频道、如何最经济地将一些城市连接起来、能否走遍城市里的所有街道而不重复、能否在平面电路板上实现电路等等都可以用图论解决。因此,我们现在所要研究的图是建立和处理离散对象及其关系即离散结构模型的一个重
4、要工具。在各类关系表示、运筹规划作业、网络结构研究、以及计算机程序流程分析中,都会遇到由这种“结点”和“边”组成的图。它在计算机科学及其应用的许多领域,如数据结构、操作系统、编译、人工智能、形式语言、网络理论、信息的组织与检索等,均起着重要作用。它广泛应用于生物学、心理学、遗传学、地理学、物理学、化学、经济学、社会学、语言学、控制论、运筹学等几乎所有的学科,我们可以说几乎每一门学科都可以用图模型来解决,而本章所要讲的树又是一个结构非常优秀的特殊图,它也有极广泛的应用。,111图的基本概念,由上述介绍我们可以简略地说,有点有边即构成图。即给定一个结点集合和这些节点之间联边的情况,这样组成的离散结
5、构就构成一个图。,1112 图的概念,定义11.1 图(graph)G是一个有序二元组,其中: (1)非空集合V(G)称为图G的结点集,其成员称为结点或顶点(nodes or vertices)。结点用拉丁字母或希腊字母来表示。 (2)集合 E(G)称为图G的边集,其成员称为边(edges)。边用结点的序偶来表示。结点有序偶表示的边称为有向边(directed edges),节点无序偶表示的边称为无向边(indirected edges)。,当图的边均为有向边时,称该图为有向图(directed graph);当图的边均为无向边时,称该图为无向图(indirected graph)。 以下图论
6、术语是经常会用到的。 边e = 时,称边e关联端点u,v,并称u为e 的起点,v为e 的终点。边e = (u,v)时,称边e关联结点u,v,并称u,v为e 的端点,这时u,v为邻接点。当边e与e1有共同端点时,称边e,e1为邻接边。当u = v时,和u,v均称为自环。不是任何边的端点(或称不关联任何边,或称不与任何点邻接)的节点称为孤立节点,仅由孤立节点构成的图(E = )称为零图。,图11.1(b)是一个图的直观表示,称为图的图形,可表示为 ,例11.1 (1)某些城市的铁路连接问题用无向图表示: 将城市用结点表示,两城市有铁路直通时连一条边。结点集V=北京,天津,济南,南京,苏州,上海,杭
7、州,武汉,广州,边集E=(北京,天津),(天津,济南),(济南,南京),(南京,苏州),(苏州,上海),(上海,杭州),(武汉,广州),(天津,武汉),图形为: 图11.2,(2)有四个程序p1,p2,p3,p4,它们之间的调用关系为:p1调用p2, p2调用p3和p4,可用有向图表示为:程序为结点,一个程序能调用另一个程序则连成一条边,即图为: , 图11.3(a),(b)都是此图的图形:,(3)图11.3为一有向图的图示,可表示为 ,,我们看到,与几何图形不同,图与图形的结点位置、边的长短、形状无关紧要,图只与结点与边的联结有关系。因此,一个图所画出的图形可以是不惟一的。 如果我们把本章最
8、初提到的同学名字之间有一相同汉字则连一条边,当有两个汉字相同时则要连两条边,这我们所谓叫平行边。关于图还有一些很好理解的术语。,定义11. 2 设图G为。 (1)当V和E为有限集时,称G为有限图,否则称G为无限图。本书只讨论有限图。 (2)关联同一对结点的边称为重边,或平行边。含有重边的图为重图。 (3)无环和重边的图称为简单图。当G为有限简单图时,也常用(n,m)表示图G有n 个节点,m 条边 。 (4)任何两个不同结点间都有边关联的简单图,称为完全图。n个顶点的完全图常记作Kn。 (5)有时我们还需要在图中的边上或结点上标上一个数字,即所谓权,此时称G为赋权图,如例11.1的(1)边上的权
9、表示两地的距离。,例11.2 图11.1(b)为重图,b1,b2为重边。图11.3为有向图,e1为环,v6为孤立结点。图11.4(a)为简单图,(b)为完全图K5,(c)为赋权图。,11. 1. 2 结点的度,结点所邻接的边的数目,我们称之为结点的度,它是图的性质的重要判据。,定义11.3 在图中,结点v的度(degree)d(v)是v所关联的边数。在有向图中,结点v的出度(out-degree)是v作为有向边起点的数目,v的入度(in-degree)是v作为有向边终点的数目。因此,结点v的度d(v)是d+(v)与d-(v)的和。当结点v有自环时,自环使其度增加2,其中一个出度,一个入度。,例
10、11.3 图11.5(a)中,d(v1) = 5,(b)中d+( v1) = 2,d-(v1) = 3,d(v1)= d+(v1) + d-(v1) = 5。,关于结点的度有下列重要而基础的性质。 定理11.1 对任意图G,设其边数为m, 顶点集为v1,v2,vn,那么 (11-1) 证 当一边关联于两个不同结点时,它分别使两结点各增加一度;当一边为一自环时,它给该结点增加两度,因此有一边使各结点的度的总和增加2,因而各结点的度的总和是边的数目的两倍。,当G为有向图时,式(11-1)可改写为 (11-2) 证明是较容易的,试着自己完成。,定理11.2 图的奇数度顶点必为偶数个。 证 反设某图有
11、奇数个奇数度的顶点,那么它们的度的总和是奇数。由于其余顶点为偶数度的,从而这部分结点度的总和为偶数。于是,图的所有顶点的度数总和为奇数(奇数与偶数的和),与定理11.1矛盾。定理得证。,还有两个与度有关的术语。 定义11.4 一度的顶点称为悬挂点(pendant nodes)。 定义11.5 各顶点的度均相同的图称为正则图(regular graph)。各顶点度均为k的正则图称为k-正则图。 当然,完全图都是正则图,而且利用定理11.2很易证明三次正则图有奇数个结点。,11. 1. 3 子图、补图及图同构,定义11.6 设图G1,G2,如果V1V2,E1E2,称G1为G2的子图(subgrap
12、h)。如果G1是G2的子图,且V1 = V2,称G1为G2的生成子图(spanning subgraph),。 定义11.7 设无向图G1,G2,称G1与G2互为补图,如果V1=V2,E1E2 = ,且是完全图。,例11.4 图11.5中(a)和(b)都是(c)的子图。(a)和(b)关于(c)互为补图,(c)为完全图K5。 两个图可能本质结构是一样的,我们称为同构。,定义11.8 设G1,G2为两个简单图,称G1与G2同构(isomorphic),如果存在一种方式将V1中节点的名一 一对应地置换为V2中节点的名,可使置换得到的图G1 满足G1G2(即 V1V2,E1E2)。,例11.5 (1)
13、图 11.6中(a),(c)表示的两图G1,G2是同构的,因为可以如下将V1中节点的名一一对应地置换为V2中节点的名,可使得到的图G1 满足G1G2 。其对应置换为:,(2)图11.7中(a),(b)表示的两图G1,G2不是同构的,定义11.9中所说“一一对应的置换”无法找到,因为这种一一对应的置换必定满足a 置换为 (它们是两图中仅有的三度顶点),从而使b,c,d分别对应于,,(或它们的另一排列),因而总有G1中一个悬挂点对应于G2中的一个二度结点,因而不可能使得G1G2。,112 路径、回路及连通性,路与回路是图的基本概念,连通性是图的基本特性。许多问题可以用图的通路来解决,如计算机之间能
14、否传递消息的问题、网络上传递邮递、收集垃圾以及故障诊断等的路线有效计划问题。,1121 路径与回路,所谓路就是从一点沿着图中的边到另外一点,回路即为起点和终点重合。,定义11.9 图G的顶点v1到顶点vl的拟路径(pseudo path)是指如下顶点与边的序列: v1 ,e1 ,v2 ,e2 ,v3 , ,v l-1 ,el-1 ,vl (11-3) 其中v1 ,v2 ,v3 , ,v l-1 ,vl为G的顶点e1 ,e2 , ,el-1 为G的边,且ei( i= 1,2, ,l-1 )以vi及vi+1为端点,(对有向图G,ei以vi为起点,以vi+1为终点),路径所含的边数l1称为该拟路径的
15、长度。当ei( i= 1,2, , l-1 )各不相同时,该拟路径称为路径(walk),又当vi(i = 1,2, ,l)各不相同时(除v1与vl),则称此路径为通路(Path)。v1vl的路径称为闭路径(closed walk);v1= vl的通路称为回路(circuit)。 当讨论限于无平行边的图时,上述拟路径、路径、通路等可用顶点序列来表示,例如用(v1 ,v2 ,v3 , ,v l-1 ,vl)代替式(11-3)。,例11.6(1)在图11.9(a)的有向图中: (v1 ,v2 ,v3 , v1 ,v2 ,v5)为一拟路径,长度为5。 (v2 ,v3 ,v1 , v2 ,v5 ,v4)
16、为一路径,长度为5。 (v2 ,v3 , v4)为一通路,长度为2。 (v2 ,v3 ,v1 , v2 ,v5 ,v4,v2)为一闭路径,长度为6。 (v2 ,v3 ,v1 , v2)为一回路,长度为3。 (2)在11.9(b)的无向图中: (v2 ,v3 , v4 ,v5)为一路径(它在(a)中不是路径),长度为3。 (v1 , v2 ,v5 ,v4,v3,v1)为一回路,长度为5。,关于路径和回路我们有 定理11.3 在有n个顶点的图G中,如果有从顶点u到v(u v)的拟路径,那么从u到v必有路径,并且必有长度不大于n 1 的通路。 证 不设一般性,设G为一简单图。若G有从u到v的拟路径(
17、u = v1 ,v2 ,v3 ,v l-1 ,vl = v),且没有vivj(i,j = l,2,, l),那么它便是一条通路,且l n l ;若G的这一拟路径中有,vivj,则它可表示为 (u = v1 ,v2 ,vi, , vi, ,v l-1 ,vl = v) 那么从中删去从vi+1到第二个vi之间的所有边及顶点,便得到一条从u到v的更短的拟路径 (u = v1 ,v2 ,vi,v l-1 ,vl = v) 然后重复上述讨论,直至没有顶点重复出现,从而 得到从u到v的路径和长度不超过n 1的通路。,完全类似地可以证明: 定理11. 4 在具有n个顶点的图G中,如果有从v到v的闭路径,那么
18、必定有一条从v到v的长度不大于n的回路。,例11.7 (1)图11.9(a)中有v2到v4的拟路径 (v2 ,v3 ,v1 , v2 ,v5 ,v4) 因而可求得从v2到v4的长度为2 (4)的通路(v2 , v5 ,v4)。 (2)图11.9(b)中有经由v2的闭路径 (v2 ,v3 ,v1 , v2 ,v5 ,v4,v2)。 从而有经由v2的长度为3(5)的回路(v2 ,v5 ,v4,v2)。,11. 2. 2 连通性,定义11.10 对于图中顶点u,v,若有一条u到v的路径,则称u到v是可达的(accesible),特别对u = v也称为是可达的。 定义11.11 如果对无向图G的任何两
19、个顶点u,v,u到v都是可达的,称G是连通的(connected)。对于有向图,如果G的任何两个顶点都是相互可达的,称G是强连通的;如果G的任何两个顶点中,至少从一个顶点到另一个顶点是可达的,称G是单向连通的;如果G的有向边被看作无向边时是连通的,称有向图G是弱连通的。,例11.8 图11.10(a)为一连通图,(b)为强连通图,(c)为单向连通图,(d)为弱连通图,(e)为含两个连通部分即两个连通分支的不连通图。,定理11.5 如果图G恰有两个不同的奇数度的顶点u,v,那么u到v必定是可达的。 证 如果u到v不可达,那么G不是连通的,u与v必分属于两个连通分支G1,G2,而G1,G2是G的子
20、图,且都恰有一个奇数度顶点。这是不可能的(定理11.2)。因而u到v是可达的。,下面我们介绍如何对图进行删点和删边以及割点和割边的概念。 首先在图中删掉某点v时,同时要删掉关联v的所有边;而在图中删掉某边e时,只将边e 删掉,点不作任何改变。因为这样才能保证图完整。 定义 8.12 如果从G中删除点v后得到的图不连通,则称v为割点(cut-nodes)。如果从G中删除边ev后得到的图不连通,则称e为割边(cut-edges)。,例11.9 图11.11中,v1,v2 ,v4都是割点,而(v1, v4),(v1, v2),(v2, v3)都是割边。,113 图的矩阵表示,我们说图实际上是两个集合
21、:点集和边集,而边是由结点之间连接的,所以图实际上是建立在结点集上的二元关系。因此我们还可以用关系矩阵表示图,当论及图的不同关系就得到图的不同矩阵表示。,1131 邻接矩阵,定义11.13 设G =为一有向图。其中V=v1,v2,vn,那么nn矩阵A = aij, 称为图G的邻接矩阵(adjacency matrix),记为AG,我们很易得出: (1)邻接矩阵也可用于无向图,并且无向图的邻接矩阵是对称矩阵。 (2)有向图邻接矩阵第i行“1”的个数是结点vi的出度,而第i列“1”的个数是结点vi的入度;而无向图邻接矩阵第i行“1”的个数是结点vi的度。,例11.10 (1)零图的邻接矩阵为零矩阵
22、。 (2)图11.12(a)的邻接矩阵为图11.12(b)。,以下设A为图G的邻接矩阵,A = aij,A为A的转置矩阵,为矩阵乘运算符。我们知道,若AB = C,A = aij,B = bij,C = cij,那么 我们还用Al表示l个矩阵A的乘积。 (1)令Al = ,那么的意义是:G中从顶点vi到vj的长度为l的拟路径恰为 条。,如例11.10之(2),由计算得 其中= 4,因此图中v3到v1长度为3的拟路径为四条。而图11.12中v3到v1恰有四条长度为3的拟路径,它们是(v3 ,v1 ,v1 ,v1),(v3 ,v4 ,v1 ,v1),(v3 ,v2 ,v4 ,v1),(v3 ,v2
23、 ,v3 ,v1)。,11.3.2 路径矩阵与可达性矩阵,定义11.14 设G =为一有向图。其中V=v1,v2,vn,那么nn矩阵A = pij, 称为图G的路径矩阵(walk matrix),记为BG,由上可知 BAA(2)A(n) 令矩阵PIB,其中I为(nn)单位矩阵,为逻辑加,称P为图G的可达性矩阵,记为PG。,114 树,树就象自然界当中的大树,是一种极为简单而又非常重要的特殊图,因为我们将会发现它的结构和性质非常好,因此它在计算机科学的算法设计、数据结构、网络技术、人工智能、软件工程、知识工程以及其他许多领域都有广泛的应用。最典型的就是菜单树、目录树。,11.4.1 树的基本概念
24、,定义11.15 连通无回路的无向图称为无向树,简称为树(tree)。树中的悬挂点又称为树叶(leave),其它结点称为分支点(branched node)。单一孤立结点称为空树(null tree)。诸连通分支均为树的图称为森林(forest),树也是森林。,例11.12 图11.15中(a),(b)为树,而(c)不是树,但(c)为森林。 由于树无自环也无重边(否则它有回路),因此树必定是简单图。树还有一些重要的性质。,定理11.6 设图T为一树,其顶点数、边数分别是n, m, 那么 n m = 1 或 m = n 1 证 用数学归纳法,略。,定理11.7 任何树都至少有两片叶。 证 设T为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十一
链接地址:https://www.31doc.com/p-2563129.html