ch10图的基本概念.ppt
《ch10图的基本概念.ppt》由会员分享,可在线阅读,更多相关《ch10图的基本概念.ppt(118页珍藏版)》请在三一办公上搜索。
1、第10章 图的基本概念,如何找到物流运输的最优路径?如何找到最优的网络通信线路?如果你想周游全国所有城市,如何设计旅游线路?化学化合物分析:结构是否相同?程序结构度量:程序是否结构相似?如何为考试分配教室,使得资源利用率最优?如何安排工作流程而达到最高效率?如何设计为众多的电视台频道分配最优方案?如何设计通信编码以提高信息传输效率?操作系统中,如何调度进程而使得系统效率最优?,如何设计集成电路线路布局而达到最优效率?如何设计计算机鼓轮?七枚同重量硬币与一枚较轻的伪币,使用天平秤多少次就能找出伪币?如何设计下棋程序?n-皇后问题最少用几种颜色就能将世界地图都着色?如何使箱子尽可能装满物体?一个船
2、夫要把一只狼,一只羊和一棵白菜运过河。问题是当人不在场时,狼要吃羊,羊要吃白菜,而他的船每趟只能运其中的一个。那么他怎样才能把三者都运过河呢?,研究主题旅行商问题:TSP问题中国邮路问题地图着色问题:四色定理最短路径问题网络流匹配组合计数,主要内容,1)图的基本术语;2)结点的度,子图,完全图;3)图的连通性;4)图的运算,图的矩阵表示及其性质;5)图的同构;6)欧拉图与哈密尔顿图的性质及其应用。,10.1 图论概述 图是人们日常生活中常见的一种信息载体,其突出的特点是直观、形象。图论,顾名思义是运用数学手段研究图的性质的理论,但这里的图不是平面坐标系中的函数,而是由一些点和连接这些点的线组成
3、的结构。图论是有许多应用的古老学科,也一直以来都是一个热门学科,它已经被广泛应用于计算机科学、化学、运筹学、心理学等很多领域。,10.2 图与图模型 例10.2 时间安排问题。某大学计算机学院的某教研组共有10名教师,他们分别参加7个班级的讨论课,每个班级可能同时需要多位教师参加,有的教师可能需要参加多个班级的讨论,每个班级必须单独开展讨论课,则如何安排才使得所有班级在最短时间段内完成讨论课?参加各个班级讨论课的教师情况如下(ci为班级编号,数字1-10为教师编号):c1=1,2,3,c2=1,3,4,5,c3=2,5,6,7,c4=2,6,7,c5=4,7,8,9,c6=8,9,10,c7=
4、1,3,9,10。,10.2 图与图模型,这样,一位教师如果给多个班级都授课,则在讨论课时间安排方面则不能冲突,如教师1不能同时参加班级c1与班级c2的讨论课。这种情况可以用下图直观地表示。在上图中,共用了7个小圆圈来表示班级,圆圈之间的线段表示存在同一个教师参加该二班级的讨论课,这样就不能安排该二班级同时开展讨论课。显然,这就给上述问题构建了一个直观的图的模型。,10.2 图与图模型 定义10.1 图G包括一个非空的对象的集合V与有限的两个对象构成的V的无序对构成的集合E,前者称为的结点集,后者称为边集。令V=v1,v2,vn是包含n个结点的集合,其m条边的集合E=e1,e2,em,其中,每
5、一条边都是集合V的二元子集,如边ei=u,v,常常简记为uv或vu,其中u、v称为边uv的端点。这样,一个图事实上就是V与E构成的序偶,常常被记作G=(V,E)。于是,也常常用V(G)和E(G)来表示某一个图G的结点集与边集。当然,也可以使用其它符号来表示图,如用F或H,甚至G1等等。,10.2 图与图模型 集合V(G)的基数n表示图G的阶(Order),集合E(G)的基数m表示图G的规模(Size),有时也将图G记作(n,m)。在图G中,若边集E(G)=,则称G为零图(Null Graph),此时,又若G为n阶图,则称G为n阶零图,记作Nn,特别地,称N1为平凡图(Trivial graph
6、)。在图的定义中规定结点集V为非空集,但在图的运算中可能产生结点集为空集的运算结果,为此规定结点集为空集的图为空图(Empty Graph),并将空图记为。阶为有限的图称为有限图(Finite Graph),否则称为无限图(Infinite Graph)。结点没有标号的图称为非标号图(Unlabeled Graph),否则为标号图(Labeled Graph)。,10.2 图与图模型 如果图中存在某两条边的端点都相同,则称该图为多重图(Multigraph),该两条边称为平行边。如果一条边关联的两个结点是相同的结点,则称该边为圈或自环(Loop)。不存在平行边与圈的图即称为简单图(Simple
7、 Graph)。,10.2 图与图模型 定义10.2 如果uv是图G的边,记为e,即uvE(G),则称结点u和v邻接(Adjacent),否则称结点u与v非邻接。这里,也称结点u或v与边e是关联(Incident)关系。与同一个结点关联的两条边称为邻接边。与结点v关联的边数称为结点v的度,记作deg(v)。与结点v关联的环对v的度数的贡献要计算两次。如果结点v的度为0,则称之为孤立点(Isolated Vertex)。一度的结点称为悬挂点(Pendant Vertex)。图G的所有结点度数的最小度数称为G的最小度,记作(G),而所有结点度数的最大者称为G的最大度,记作(G)。各结点的度均相同的
8、图称为正则图(Regular Graph)。各结点度均为k的正则图称为k-正则图。,10.2 图与图模型 定义10.3 如果图的每条边是二结点构成的有序对,则该图称为有向图(Directed Graph),上文所定义的图都是无向图(Undirected Graph)。有向图中边uv与vu是两条不同的边,对于边uv,称u为始点,v为终点。有向图中,结点v的度分为入度,即与该结点相关联并以该结点为终点的边的数目,以及出度,即与该结点相关联并以该结点为始点的边的数目,分别记作deg+(v),deg-(v)。,10.2 图与图模型,无向图,有向图,10.2 图与图模型,环loop-(伪图:非简单图si
9、mple graph),边e2(有向边directed edge有向图)关联incident结点v1、v2,结点vertex/vertices(顶点),平行边/重边multiedge多重图multigraph,多重图且伪图拟图(pseudograph),孤立点(isolated vertex),悬挂边(pendant edge),悬挂点(pendant vertex),分离边,v3结点度degree为3,与3结点邻接adjacent,2出度1入度,v3,10.2 图与图模型 练习1 设G=(V,E)是一无向图,V=v1,v2,v8,E=(v1,v2),(v2,v3),(v3,v1),(v1,v
10、5),(v5,v4),(v4,v3),(v7,v8)(1)画出G的图解;(2)指出与V3邻接的结点,以及和V3关联的边;(3)指出与(v2,v3)邻接的边和与(v2,v3)关联的结点;(4)该图是否有孤立结点和孤立边?(5)求出各结点的度数,并判断是否是完全图和正则图?(6)该(n,m)图中,n=?,m=?,10.2 图与图模型 图的边数与结点数的关系是图最为重要的属性,结点的度数满足一个非常简单的关系,即图的每条边都关联于两个结点,则每条边对图结点度数之和的贡献为2,从而有下面的定理:定理10.1(欧拉定理)在任何图中,结点度的总和等于边数的两倍。该定理也被称为握手定理,被认为图论第一定理,
11、可以用于证明图的相关性质。推论10.1 在任意图中,奇数度的结点个数为偶数。,10.2 图与图模型 例10.3 设G=,|V|=n,|E|=m,证明:(G)2m/n(G)。证明 由欧拉定理,deg(v)=2m。对任意的vV,有(G)deg(v)(G),于是 n(G)deg(v)n(G)n(G)2mn(G)即(G)2m/n(G)。,10.2 图与图模型 例10.4 请证明:有向图中,所有结点出度之和等于所有结点入度之和。证明 在有向图中,任意一条边都有一个始点和一个终点,因而结论成立。,10.2 图与图模型 练习2 设G=(V,E)有12条边,有6个度为3的结点,其余结点的度数均小于3,问G中至
12、少有多少个结点?,10.2 图与图模型 例10.5 十字路口交通管理问题。下图(a)是某繁忙的城市十字路口交通管理示意图,其中c1c9表示可能的行车路线,为安全考虑,显然c1、c5可以同时进入十字路口,但c1与c8却不能同时进入十字路口,等等。本问题可以用图来建模,如下图(b)所示。其中,结点集为所有行车路线的构成的集合,结点之间的边表示相应的二行车道不能同时开通。显然此图可以用于十字路口交通信号灯的设计。,(a),(b),10.2 图与图模型,例10.6 旅行售货员问题。现有一个笔记本计算机代理商要从其所在的城市北京出发,乘飞机去5个城市,然后回到出发点。如右图所示。图中结点代表城市,边代表
13、城市间的直达航线。他怎样才能出差到每个城市恰巧一次,最后回到北京呢?,这个问题的解答本身比较简单,如可以选择线路为北京-成都-武汉-海口-广州-上海-北京。但对于更为复杂的情况就很难直接找到好的解答。本问题与后文将研究的Hamilton图有关,将在那里做详细讨论。,10.2 图与图模型,例10.7 优先图。通过并发地执行某些语句,计算机程序可以执行得更快。如何确定哪些语句可以并发执行是非常重要的,这需要分析清楚程序中语句之间的优先关系。这种优先关系可以用有向图来表示。如用结点表示语句,若在执行完第一个结点表示的语句之前不能执行第二个结点表示的语句所表示的语句,则在第一个结点到第二个结点之间添加
14、一条边。最后得到的图称为优先图。下图就是一个优先图的例子。该图表明在执行语句S1、S2与S4之前不能执行语句S5。,10.2 图与图模型 练习3 在晚会上有n个人,他们各自与自己相识的人握一次手。已知每人与别人握手的次数都是奇数,问n是奇数还是偶数。为什么?解 n是偶数。用n个顶点表示n个人,顶点间的一条边表示一次握手,可构成 一个无向图。若n是奇数,那么该图的顶点度数之和为奇数个奇数的和,即为奇数,与图性质矛盾,因此,n是偶数。,10.2 图与图模型 与集合论中研究子集,抽象代数中研究子代数类似,图论中也研究一个图的子图。一个图G的子图G可以通过选取G中的部分结点与边构成,但要求如果选择了G
15、中的边,则必须选择与该边向关联的结点。这样就保证了G能够构成一个图。,10.2 图与图模型 定义10.4 令图G=(V,E),称(V,E)为G的子图(Subgraph),当(1)VV且EE;(2)对任意eE,则与e相关联的结点u,vV。若G是 G的子图,则称G是G的超图,记作GG。若GG且GG(即VV或EE),则称G是G的真子图。若GG且VV,则称G是G的生成子图(Spanning Subgraph)。设V1V,且V1,以V1为结点集,以两端点均在V1中的全体边为边集的G的子图,称为结点集V1导出的导出子图(Derived Subgraph)。设E1E,且E1,以E1为边集,以E1中边关联的结
16、点的全体为结点集G的子图,称为边集E1导出的导出子图。,10.2 图与图模型 显然,子图或导出子图可以通过删除一些结点或一些边得到。例10.9 下图所示的图中,G1是G的由结点导出的导出子图,G2为G的由边集导出的导出子图。,10.2 图与图模型 定义10.5 设G=是n阶图,若G中任何结点都与其余的n1个结点相邻,则称G为n阶完全图(Complete Graph)。记作Kn。设D=为n阶有向图,若对于任意的结点,u,vV(uv),既有有向边,又有,则称D为有向完全图。容易得到如下重要结论:Kn的边数|E(Kn)|=n(n-1)/2,且对于一般的n个结点的图G其边数|E(G)|n(n-1)/2
17、。,10.2 图与图模型 下图中图(a)为四个结点的完全图,(b)不是完全图,(c)是有向完全图。,(a),(b),(c),10.2 图与图模型 定义10.6 若图G的结点可以分为两个非空集合V1,V2,G中的边的端点分别属于V1,V2,则称G为二分图(Bipartite Graph),可简记为G(V1,V2)。若V1中结点与V2中结点均邻接且V2中结点与V1中结点也均邻接,则称G为完全二分图(Complete Bipartite Graph),记为Km,n,m,n分别是V1,V2的基数。二分图常常被应用于工作分配问题中,通过对二分图的分析,找出满足最多条件的工作分配方案。完全二分图K1,n常
18、常被用来对计算机网络建模,度为n的结点代表网络服务器,其余结点代表网络中的n个计算机。,10.2 图与图模型 例10.10 下图所示的图(a)是二分图,图(b)是其的另一种表示。,10.3 路径与图连通性 图论中的许多概念和应用都与对图的遍历有关,即是从一个结点u出发,到达与之相邻接的结点,在从该邻接结点出发到达其邻接的结点,依次类推,最后可以到达图中的某结点v,从而就得到一条从u到v的通路。从u到v的通路W可用如下的结点的序列来表示:W:u=v0,v1,v2,vk=v,k0。通路W常表示为u-v通路。这些结点序列中任意相邻的结点在图中是邻接的关系,称结点vi(i=0,1,k)以及边(vi,v
19、i+1)(i=0,1,k-1)为通路W上的结点与边。,10.3 路径与图连通性 如果通路上首尾结点相同,则称该通路是闭的(Closed),否则称该通路是开的(Opened)。如果通路上没有相同的边,则称该通路为迹(Trail),如果迹上的开始结点与结束结点相同,则称之为回路(Circuit),如果回路上除了开始结点与结束结点没有相同的结点,则称之为环(Cycle)。如果通路上没有相同的结点,则称该通路为路或路径(Path),有n个结点的路常记作Pn。,10.3 路径与图连通性 通路遍历过的边的数目为通路的长度,如果通路长度为0,则称之为平凡通路(Trivial Walk)。两结点u,v间的路可
20、能不只一条,将其中的最短的路称为u,v间的距离。如果一条通路W上有k+1个结点,即W:u=v0,v1,v2,vk=v,k0。则由于W上的边是由W上相邻结点(vi,vi+1)(i=0,1,k-1)构成,因此W上有k条边,即W的长度为k。如果一条环C上有k+1个结点,即C:v0,v1,v2,vkv0,k0.则由于C上的边是由C上相邻结点(vi,vi+1)(i=0,1,k-1)以及(vk,v0)构成,因此C上有k+1条边,即C的长度为k+1。,10.3 路径与图连通性 定理10.2 如果图G上存在一条u-v通路,则必然存在一条u-v路;如果G上存在一条闭通路,则必然存在一条回路(环)。这是因为,如果
21、通路上存在相同的结点vi,vj,则可将vi,vj之间的一段通路删除,并合并vi,vj为一个结点,从而得到一条更短的u-v通路。如果所得到的u-v通路上还存在相同的结点,则可以依此继续执行删除操作,最终一定可以得到一条没有相同结点的u-v通路,也就是一条u-v路。类似地,如果G上存在一条闭通路,则必然存在一条回路(环)。,10.3 路径与图连通性例10.11 在右图中,1)找出一条包含图所有结点的通道;2)找出一条包含图所有结点的迹;3)找出所有a-d路,并求出其长度;4)找出图中所有的环。解 1)包含图所有结点的不是迹的通道:aebcaebd。2)包含所有结点的迹:beacbd。3)a-d路:
22、aebd,acbd,长度均为3。4)环:acbea,长度为4。,10.3 路径与图连通性 例10.12 每个结点的度数至少为2的图必包含一个回路。证明 设P是图G中最长路经中的一条,并设其长度为m,P的一个端点为u。考察G中与u关联的边,由于G中每个结点的度至少为2,故u必关联一条不在P上的边e,从而e的另一个端点v必然在P上,否则,将这个结点加入P上,则可以得到更长的路。于是,P上u到v的的路与边e构成回路。,10.3 路径与图连通性Dijkstra最短路径算法输入:一个带权图G,G的任意两个结点间有路径存在,G中任意边(v,x)的权值w(v,x)0;结点a与z输出:L(z),从结点a到z的
23、最短路径长度1 Procedure Dijkstra(G)2 For 所有结点xa 3 L(x)=;L(x)表示a到x的最短路径长度4End for;5 L(a)=0;6 T=V(G);7S=;,10.3 路径与图连通性8 While(zT)9 从T中找出具有最小L(v)的结点v;10 For 所有与v相邻的结点xT11 L(x)=minL(x),L(v)+w(v,x)12End For13 T=T-v;14S=Sv;15 End While16 End Procedure,10.3 路径与图连通性 例10.13 下图所示的带权图中,根据上述算法可以得到结点a到z的最短路径为图中加粗的边所示,
24、长度为13。,10.3 路径与图连通性 定义10.5 如果图G中结点u到v有一条路径,则称结点u到v是可达的(Accesible)或连通的(Connected)。结点u到其自身也定义为连通的。定义10.6 如果图G的任何两个结点都是相互可达的,称G是连通的(Connected),并称G为连通图(Connected Graph)。对于有向图G,如果G的任何两个结点都是相互可达的,则称有向图G是强连通的;如果G的任何两个结点中,至少从一个结点到另一个结点是可达的,称有向图G是单向连通的;如果G的有向边被看作无向边时是连通的,称有向图G是弱连通的。,10.3 路径与图连通性 容易判断,强连通图必定是
25、单向连通图,单向连通图必定是弱连通图。例10.14 下图中,(a)为连通图,(b)为由两个连通分支的非连通图,c为强连通图,d为单向连通图,e为弱连通图。a b c d e,10.3 路径与图连通性 练习4 已知关于a,b,c,d,e,f,g的下述事实:a说英语;b说英语和西班牙语;c说英语、意大利语和俄语;d说日语和西班牙语;e说德语和意大利语;f说法语、日语和俄语;g说法语和德语;试问:上述7人中是否任意两人都能交谈(如果必要,可由其余5人中所组成的译员链帮忙?),10.3 路径与图连通性 若将图中两个结点间的连通性看作图的结点间的一种关系,容易判定图中两个结点间的连通性是一个等价关系,因
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ch10 基本概念
链接地址:https://www.31ppt.com/p-5376693.html