ch图的基本概念.pptx
《ch图的基本概念.pptx》由会员分享,可在线阅读,更多相关《ch图的基本概念.pptx(117页珍藏版)》请在咨信网上搜索。
1、n如何找到物流运输的最优路径?n如何找到最优的网络通信线路?n如果你想周游全国所有城市,如何设计旅游线路?n化学化合物分析:结构是否相同?n程序结构度量:程序是否结构相似?n如何为考试分配教室,使得资源利用率最优?n如何安排工作流程而达到最高效率?n如何设计为众多的电视台频道分配最优方案?n如何设计通信编码以提高信息传输效率?n操作系统中,如何调度进程而使得系统效率最优?n如何设计集成电路线路布局而达到最优效率?n如何设计计算机鼓轮?n七枚同重量硬币与一枚较轻的伪币,使用天平秤多少次就能找出伪币?n如何设计下棋程序?nn-皇后问题n最少用几种颜色就能将世界地图都着色?n如何使箱子尽可能装满物体
2、?n一个船夫要把一只狼,一只羊和一棵白菜运过河。问题是当人不在场时,狼要吃羊,羊要吃白菜,而他的船每趟只能运其中的一个。那么他怎样才能把三者都运过河呢?研究主题研究主题n旅行商问题:TSP问题n中国邮路问题n地图着色问题:四色定理n最短路径问题n网络流n匹配n组合计数主要内容主要内容 1)1)图的基本术语;图的基本术语;2)2)结点的度,子图,完全图;结点的度,子图,完全图;3)3)图的连通性;图的连通性;4)4)图的运算,图的矩阵表示及其性质;图的运算,图的矩阵表示及其性质;5)5)图的同构;图的同构;6)6)欧拉图与哈密尔顿图的性质及其应用。欧拉图与哈密尔顿图的性质及其应用。10.1 10
3、.1 图论概述图论概述 图是人们日常生活中常见的一种信息载图是人们日常生活中常见的一种信息载体,其突出的特点是直观、形象。图论,顾体,其突出的特点是直观、形象。图论,顾名思义是运用数学手段研究图的性质的理论,名思义是运用数学手段研究图的性质的理论,但这里的图不是平面坐标系中的函数,而是但这里的图不是平面坐标系中的函数,而是由一些点和连接这些点的线组成的结构。图由一些点和连接这些点的线组成的结构。图论是有许多应用的古老学科,也一直以来都论是有许多应用的古老学科,也一直以来都是一个热门学科,它已经被广泛应用于计算是一个热门学科,它已经被广泛应用于计算机科学、化学、运筹学、心理学等很多领域。机科学、
4、化学、运筹学、心理学等很多领域。10.2 10.2 图与图模型图与图模型 例例10.210.2 时时间间安安排排问问题题。某某大大学学计计算算机机学学院院的的某某教教研研组组共共有有1010名名教教师师,他他们们分分别别参参加加7 7个个班班级级的的讨讨论论课课,每每个个班班级级可可能能同同时时需需要要多多位位教教师师参参加加,有有的的教教师师可可能能需需要要参参加加多多个个班班级级的的讨讨论论,每每个个班班级级必必须须单单独独开开展展讨讨论论课课,则则如如何何安安排排才才使使得得所所有有班班级级在在最最短短时时间间段段内内完完成成讨讨论论课课?参参加加各各个个班班级级讨讨论论课课的的教教师师
5、情情况况如下(如下(c ci i为班级编号,数字为班级编号,数字1-101-10为教师编号):为教师编号):c c1=1=1,2 2,33,c c2=1=1,3 3,4 4,55,c c3=2=2,5 5,6 6,77,c c4=2=2,6 6,77,c c5=4=4,7 7,8 8,99,c c6=8=8,9 9,1010,c c7=1=1,3 3,9 9,1010。10.2 10.2 图与图模型图与图模型 这样,一位教师如果给多个班级都授课,则在这样,一位教师如果给多个班级都授课,则在讨论课时间安排方面则不能冲突,如教师讨论课时间安排方面则不能冲突,如教师1 1不能同不能同时参加班级时参加
6、班级c c1 1与班级与班级c c2 2的讨论课。这种情况可以用的讨论课。这种情况可以用下下图直观地表示。图直观地表示。在在上上图中,共用了图中,共用了7 7个小圆圈来表示班级,圆圈个小圆圈来表示班级,圆圈之间的线段表示存在同一个教师参加该二班级的讨之间的线段表示存在同一个教师参加该二班级的讨论课,这样就不能安排该二班级同时开展讨论课。论课,这样就不能安排该二班级同时开展讨论课。显然,这就给上述问题构建了一个直观的图的模型。显然,这就给上述问题构建了一个直观的图的模型。c c6c c5c c4c c2c c3c c7c c110.2 10.2 图与图模型图与图模型 定义定义10.110.1 图
7、图G G包括一个非空的对象的集合包括一个非空的对象的集合V V与与有限的两个对象构成的有限的两个对象构成的V V的无序对构成的集合的无序对构成的集合E E,前者称为的,前者称为的结点集结点集,后者称为,后者称为边集边集。令令V=vV=v1 1,v,v2 2,v,vn n 是包含是包含n n个结点的集合,个结点的集合,其其m m条边的集合条边的集合E=eE=e1 1,e,e2 2,e,em m,其中,每一,其中,每一条边都是集合条边都是集合V V的二元子集,如边的二元子集,如边e ei i=u=u,vv,常常简记为,常常简记为uvuv或或vuvu,其中,其中u u、v v称为边称为边uvuv的的
8、端点端点。这样,一个图事实上就是。这样,一个图事实上就是V V与与E E构成的构成的序偶,常常被记作序偶,常常被记作G=(V,E)G=(V,E)。于是,也常常用。于是,也常常用V(G)V(G)和和E(G)E(G)来表示某一个图来表示某一个图G G的结点集与边集。的结点集与边集。当然,也可以使用其它符号来表示图,如用当然,也可以使用其它符号来表示图,如用F F或或H H,甚至,甚至G G1 1等等。等等。10.2 10.2 图与图模型图与图模型 集合集合V(G)V(G)的基数的基数n n表示表示图图G G的阶的阶(OrderOrder),集合),集合E(G)E(G)的基数的基数m m表示表示图图
9、G G的规模的规模(SizeSize),有时也将图),有时也将图G G记作记作(n,m)(n,m)。在图。在图G G中,若边集中,若边集E(G)=,E(G)=,则称则称G G为为零图零图(Null GraphNull Graph),此时,又若),此时,又若G G为为n n阶图,则称阶图,则称G G为为n n阶零图阶零图,记作,记作N Nn n,特别地,称,特别地,称N N1 1为为平凡图平凡图(Trivial Trivial graphgraph)。在图的定义中规定结点集)。在图的定义中规定结点集V V为非空集,但为非空集,但在图的运算中可能产生结点集为空集的运算结果,在图的运算中可能产生结点
10、集为空集的运算结果,为此规定结点集为空集的图为为此规定结点集为空集的图为空图空图(Empty GraphEmpty Graph),),并将空图记为并将空图记为。阶为有限的图称为。阶为有限的图称为有限图有限图(Finite(Finite Graph)Graph),否则称为,否则称为无限图无限图(Infinite Graph)(Infinite Graph)。结点结点没有标号的图称为没有标号的图称为非标号图非标号图(Unlabeled GraphUnlabeled Graph),),否则为否则为标号图标号图(Labeled GraphLabeled Graph)。)。10.2 10.2 图与图模型
11、图与图模型 如果图中存在某两条边的端点都相如果图中存在某两条边的端点都相同,则称该图为同,则称该图为多重图多重图(Multigraph)(Multigraph),该两条边称为该两条边称为平行边平行边。如果一条边关联。如果一条边关联的两个结点是相同的结点,则称该边为的两个结点是相同的结点,则称该边为圈圈或或自环自环(Loop)(Loop)。不存在平行边与圈的。不存在平行边与圈的图即称为图即称为简单图简单图(Simple Graph)(Simple Graph)。10.2 10.2 图与图模型图与图模型 定义定义10.210.2 如果如果uvuv是图是图G G的边,记为的边,记为e e,即,即uv
12、uv E(G),E(G),则则称结点称结点u u和和v v邻接邻接(Adjacent),(Adjacent),否则称结点否则称结点u u与与v v非邻接非邻接。这里,也称结点这里,也称结点u u或或v v与边与边e e是是关联关联(IncidentIncident)关系。)关系。与同一个结点关联的两条边称为与同一个结点关联的两条边称为邻接边邻接边。与结点。与结点v v关关联的边数称为联的边数称为结点结点v v的度的度,记作,记作deg(v)deg(v)。与结点。与结点v v关联关联的环对的环对v v的度数的贡献要计算两次。如果结点的度数的贡献要计算两次。如果结点v v的度为的度为0 0,则称之
13、为,则称之为孤立点孤立点(Isolated Vertex)(Isolated Vertex)。一度的结点。一度的结点称为称为悬挂点悬挂点(Pendant VertexPendant Vertex)。图)。图G G的所有结点度的所有结点度数的最小度数称为数的最小度数称为G G的最小度的最小度,记作,记作(G)(G),而所有结,而所有结点度数的最大者称为点度数的最大者称为G G的最大度的最大度,记作,记作(G)(G)。各结点。各结点的度均相同的图称为的度均相同的图称为正则图正则图(Regular GraphRegular Graph)。各)。各结点度均为结点度均为k k的正则图称为的正则图称为k-
14、k-正则图正则图。10.2 10.2 图与图模型图与图模型 定义定义10.310.3 如果图的每条边是二结点构成的有序对,如果图的每条边是二结点构成的有序对,则该图称为则该图称为有向图有向图(Directed Graph)(Directed Graph),上文所定义,上文所定义的图都是的图都是无向图无向图(Undirected Graph)(Undirected Graph)。有向图中边。有向图中边uvuv与与vuvu是两条不同的边,对于边是两条不同的边,对于边uvuv,称,称u u为为始点始点,v v为为终点终点。有向图中,结点有向图中,结点v v的度分为的度分为入度入度,即与该结点相,即与
15、该结点相关联并以该结点为终点的边的数目,以及关联并以该结点为终点的边的数目,以及出度出度,即与即与该结点相关联并以该结点为始点的边的数目该结点相关联并以该结点为始点的边的数目,分别记分别记作作degdeg+(v)(v),degdeg-(v)(v)。10.2 10.2 图与图模型图与图模型v v1 1v v2 2e e1 1e e2 2v v1 1v v2 2e e1 1e e2 2无向图无向图有向图有向图10.2 10.2 图与图模型图与图模型环环looploop-(-(伪图伪图:非简单图非简单图simple graph)simple graph)边边e e2 2(有向边有向边directed
16、 edgedirected edge有向图有向图)关联关联incidentincident结点结点v v1 1、v v2 2结点结点vertex/vertices(vertex/vertices(顶点顶点)平行边平行边/重边重边multiedgemultiedge多多重图重图multigraphmultigraph多重图多重图且伪图且伪图拟图拟图(pseudograph)(pseudograph)孤立点孤立点(isolated vertex)(isolated vertex)悬挂边悬挂边(pendant edge)(pendant edge)悬挂点悬挂点(pendant vertex)(pen
17、dant vertex)分离边分离边v v3 3结点度结点度degreedegree为为3,3,与与3 3结点结点邻接邻接adjacent,2adjacent,2出度出度1 1入度入度v v3 3v v1 1v v2 2e e1 1e e2 210.2 10.2 图与图模型图与图模型 练习练习1 1 设设G=(V,E)G=(V,E)是一无向图,是一无向图,V=vV=v1 1,v,v2 2,v,v8 8,E=E=(v(v1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),(v3 3,v,v1 1),(v),(v1 1,v,v5 5),(v),(v5 5,v,v4 4),(v),(
18、v4 4,v,v3 3),),(v(v7 7,v,v8 8)(1 1)画出)画出G G的图解;的图解;(2 2)指出与)指出与V V3 3邻接的结点,以及和邻接的结点,以及和V V3 3关联的边;关联的边;(3 3)指出与)指出与(v(v2 2,v,v3 3)邻接的边和与邻接的边和与(v(v2 2,v,v3 3)关联的结点;关联的结点;(4 4)该图是否有孤立结点和孤立边?)该图是否有孤立结点和孤立边?(5 5)求求出出各各结结点点的的度度数数,并并判判断断是是否否是是完完全全图图和和正正则图?则图?(6 6)该)该(n,m)(n,m)图中,图中,n=n=?,?,m=m=?10.2 10.2
19、图与图模型图与图模型 图图的的边边数数与与结结点点数数的的关关系系是是图图最最为为重重要要的的属属性性,结结点点的的度度数数满满足足一一个个非非常常简简单单的的关关系系,即即图图的的每每条条边边都都关关联联于于两两个个结结点点,则则每每条条边边对对图图结结点点度度数数之之和和的贡献为的贡献为2 2,从而有下面的定理:,从而有下面的定理:定定理理10.110.1(欧欧拉拉定定理理)在在任任何何图图中中,结结点点度度的的总总和和等于边数的两倍。等于边数的两倍。该该定定理理也也被被称称为为握握手手定定理理,被被认认为为图图论论第第一一定定理,可以用于证明图的相关性质。理,可以用于证明图的相关性质。推
20、论推论10.110.1 在任意图中,奇数度的结点个数为偶数。在任意图中,奇数度的结点个数为偶数。10.2 10.2 图与图模型图与图模型 例例10.310.3 设设G=G=,|V|=n,|E|=m|V|=n,|E|=m,证明:,证明:(G)2m/n(G)2m/n(G)(G)。证明证明 由欧拉定理,由欧拉定理,deg(v)deg(v)=2m=2m。对对任任意意的的v v V V,有有(G)deg(v)(G)deg(v)(G)(G),于于是是 n n(G)(G)deg(v)deg(v)nn(G)(G)n n(G)2mn(G)2mn(G)(G)即即 (G)2m/n(G)2m/n(G)(G)。10.2
21、 10.2 图与图模型图与图模型 例例10.410.4 请证明:有向图中,所有结点出度之请证明:有向图中,所有结点出度之和等于所有结点入度之和。和等于所有结点入度之和。证明证明 在有向图中,任意一条边都有一个始点在有向图中,任意一条边都有一个始点和一个终点,因而结论成立。和一个终点,因而结论成立。10.2 10.2 图与图模型图与图模型 练习练习2 2 设设G=(V,E)G=(V,E)有有1212条边,有条边,有6 6个度为个度为3 3的结的结点,其余结点的度数均小于点,其余结点的度数均小于3 3,问,问G G中至少有中至少有多少个结点?多少个结点?10.2 10.2 图与图模型图与图模型 例
22、例10.510.5 十字路口交通管理问题。下图十字路口交通管理问题。下图(a)(a)是某繁忙的城市十字是某繁忙的城市十字路口交通管理示意图,其中路口交通管理示意图,其中c c1 1 c c9 9表示可能的行车路线,为安全表示可能的行车路线,为安全考虑,显然考虑,显然c c1 1、c c5 5可以同时进入十字路口,但可以同时进入十字路口,但c c1 1与与c c8 8却不能同时却不能同时进入十字路口,等等。本问题可以用图来建模,如下图(进入十字路口,等等。本问题可以用图来建模,如下图(b b)所示。其中,结点集为所有行车路线的构成的集合,结点之间所示。其中,结点集为所有行车路线的构成的集合,结点
23、之间的边表示相应的二行车道不能同时开通。显然此图可以用于十的边表示相应的二行车道不能同时开通。显然此图可以用于十字路口交通信号灯的设计。字路口交通信号灯的设计。c4 c5c1 c2c3c8c7c6c3c4c9c1c5c2c7 c6c9 c8(a)(b)10.2 10.2 图与图模型图与图模型 例例10.610.6 旅行售货员问题。现有旅行售货员问题。现有一个笔记本计算机代理商要从一个笔记本计算机代理商要从其所在的城市北京出发,乘飞其所在的城市北京出发,乘飞机去机去5 5个城市,然后回到出发点。个城市,然后回到出发点。如右图所示。图中结点代表城如右图所示。图中结点代表城市,边代表城市间的直达航线
24、。市,边代表城市间的直达航线。他怎样才能出差到每个城市恰他怎样才能出差到每个城市恰巧一次,最后回到北京呢?巧一次,最后回到北京呢?海口海口成都成都北京北京武汉武汉广州广州上海上海这个问题的解答本身比较简单,如可以选择线路为北京这个问题的解答本身比较简单,如可以选择线路为北京-成都成都-武汉武汉-海口海口-广州广州-上海上海-北京。但对于更为复杂的北京。但对于更为复杂的情况就很难直接找到好的解答。本问题与后文将研究的情况就很难直接找到好的解答。本问题与后文将研究的HamiltonHamilton图有关,将在那里做详细讨论。图有关,将在那里做详细讨论。10.2 10.2 图与图模型图与图模型 例例
25、10.710.7 优先图。通过并发地执行某些语句,计算机程序可以执优先图。通过并发地执行某些语句,计算机程序可以执行得更快。如何确定哪些语句可以并发执行是非常重要的,这需行得更快。如何确定哪些语句可以并发执行是非常重要的,这需要分析清楚程序中语句之间的优先关系。这种优先关系可以用有要分析清楚程序中语句之间的优先关系。这种优先关系可以用有向图来表示。如用结点表示语句,若在执行完第一个结点表示的向图来表示。如用结点表示语句,若在执行完第一个结点表示的语句之前不能执行第二个结点表示的语句所表示的语句,则在第语句之前不能执行第二个结点表示的语句所表示的语句,则在第一个结点到第二个结点之间添加一条边。最
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ch 基本概念
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。