《图论GraphicTheoryppt课件.ppt》由会员分享，可在线阅读，更多相关《图论GraphicTheoryppt课件.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论GraphicTheoryppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望内容回顾内容回顾n n图论中著名的问题：环球旅行问题到货郎问题；四色猜想问题；Ramsey问题：Ramsey问题的描述；Ramsey问题的证明；妖怪图(snark graph)内容回顾内容回顾1n n图的基本概念有向图/无向图子图；邻接度；路径/简单路径/回路/简单回路；连通/连通图/连通分量/连通有向图/强连通图；n n两个结论：握手定理；握手定理的推论。第一章第一章 图的基
2、本概念图的基本概念1 引论2 图的概念3 道路和回路4 图的矩阵表示法5 中国邮路问题6 平面图思考：思考：(1)若有n个顶点的有向图G是强连通图，G中最少有几条弧才能保证其强连通性？(2)若有n个顶点的无向图G是连通图，G中最少有几条边才能保证其极大连通性？3)，若G中任意一对顶点vi、vj，恒有d(vi)+d(vj)n-1，则图G中至少有一条Hamilton道路。n n推论(充分条件)：若任意一对顶点vi、vj，恒有d(vi)+d(vj)n，则图G中至少有一条Hamilton回路。Hamilton定理证明定理证明下面证明Hamilton道路的存在。证明：(1)先证明G是连通的。假设G不连通
3、，则G至少有两个连通分量。设其中一部分有n1个顶点，另一部分有n2个顶点。分别在两部分各选一个顶点v1、v2，G是简单图，所以：d(v1)n11，d(v2)n21，d(v1)+d(v2)n1 n2 2n1。与假设d(vi)+d(vj)n-1矛盾，所以G连通。Hamilton定理证明定理证明1(2)再证明存在Hamilton道路：假设G中有一条从v1到vL道路 T=(v1,v2,vL)是图中的最长道路，即起点v1和终点vL不和T之外的顶点相邻。(a)如果Ln，即T是包含所有顶点的道路，即T是Hamilton道路，得证。(b)若Ln且v1和vL相邻，则存在包含T的回路；v1v2vpvLvL-1Ha
4、milton定理证明定理证明2 若Ln且v1和vL不相邻，则根据条件d(vi)+d(vj)n-1，有如下图示：v1v2vp-1vLvp所以存在包含T的回路。Hamilton定理证明定理证明3(c)证明存在比T更长的道路：与假设矛盾，所以存在包含所有顶点的Hamilon道路。v1v2vp-1vLvpvk 则根据条件d(vi)+d(vj)n-1，有如下图示：课后作业课后作业1.试证明10人中必有3个人相互认识或4个人相互不认识，两者必居其一。思考题思考题1答案答案(1)若有n个顶点的有向图G是强连通图，G中最少有几条边才能保证其强连通性？答：n条边，一个环。(2)若有n个顶点的无向图G是连通图，G中最少有几条边才能保证其极大连通性？答：n-1条边，即为一棵树的时候边数最少。