资源描述
,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论,Graphic Theory,阙夏制作,图论Graphic Theory阙夏制作,1,内容回顾,图论中著名的问题：,环球旅行问题到货郎问题；,四色猜想问题；,Ramsey,问题：,Ramsey,问题的描述；,Ramsey,问题的证明；,妖怪图,(snark graph),内容回顾图论中著名的问题：,2,内容回顾1,图的基本概念,有向图,/,无向图,子图；,邻接,度；,路径,/,简单路径,/,回路,/,简单回路；,连通,/,连通图,/,连通分量,/,连通有向图,/,强连通图；,两个结论：,握手定理；,握手定理的推论。,内容回顾1图的基本概念,3,第一章 图的基本概念,1,引论,2,图的概念,3,道路和回路,4,图的矩阵表示法,5,中国邮路问题,6,平面图,第一章 图的基本概念1 引论,4,思考：,(1),若有,n,个顶点的有向图,G,是强连通图，,G,中最少有几条弧才能保证其强连通性？,(2),若有,n,个顶点的无向图,G,是连通图，,G,中最少有几条边才能保证其极大连通性？,3),，若,G,中任意一对顶点,v,i,、,v,j,，恒有,d(v,i,)+d(v,j,)n-1,，则图,G,中至少有一条,Hamilton,道路。,推论,(,充分条件,),：若任意一对顶点,v,i,、,v,j,，恒有,d(v,i,)+d(v,j,)n,，则图,G,中至少有一条,Hamilton,回路。,Hamilton定理定理(充分条件)：设简单图G的顶点数为,23,Hamilton定理证明,下面证明,Hamilton,道路的存在。,证明：,(1),先证明,G,是连通的。,假设,G,不连通，则,G,至少有两个连通分量。设其中一部分有,n,1,个顶点，另一部分有,n,2,个顶点。分别在两部分各选一个顶点,v,1,、,v,2,，,G,是简单图，所以：,d(v,1,)n,1,1,，,d(v,2,)n,2,1,，,d(v,1,)+d(v,2,)n,1,n,2,2,n,1,。,与假设,d(v,i,)+d(v,j,)n-1,矛盾，所以,G,连通。,Hamilton定理证明下面证明Hamilton道路的存在。,24,Hamilton定理证明1,(2),再证明存在,Hamilton,道路：,假设,G,中有一条从,v,1,到,v,L,道路,T=(v,1,v,2,v,L,),是图中的最长道路，即起点,v,1,和终点,v,L,不和,T,之外的顶点相邻。,(a),如果,L,n,，即,T,是包含所有顶点的道路，即,T,是,Hamilton,道路，得证。,(b),若,L,n,且,v,1,和,v,L,相邻，则存在包含,T,的回路；,v,1,v,2,v,p,v,L,v,L-1,Hamilton定理证明1(2)再证明存在Hamilton,25,Hamilton定理证明2,若,L,n,且,v,1,和,v,L,不相邻，则根据条件,d(v,i,)+d(v,j,)n-1,，有如下图示：,v,1,v,2,v,p-1,v,L,v,p,所以存在包含,T,的回路。,Hamilton定理证明2 若Ln且v1和vL不相邻，则,26,Hamilton定理证明3,(c),证明存在比,T,更长的道路：,与假设矛盾，所以存在包含所有顶点的,Hamilon,道路。,v,1,v,2,v,p-1,v,L,v,p,v,k,则根据条件,d(v,i,)+d(v,j,)n-1,，有如下图示：,Hamilton定理证明3(c)证明存在比T更长的道路：,27,课后作业,1.,试证明,10,人中必有,3,个人相互认识或,4,个人相互不认识，两者必居其一。,课后作业1.试证明10人中必有3个人相互认识或4个人相互不认,28,思考题1答案,(1),若有,n,个顶点的有向图,G,是强连通图，,G,中最少有几条边才能保证其强连通性？,答：,n,条边，一个环。,(2),若有,n,个顶点的无向图,G,是连通图，,G,中最少有几条边才能保证其极大连通性？,答：,n-1,条边，即为一棵树的时候边数最少。,思考题1答案(1)若有n个顶点的有向图G是强连通图，G中最少,29,
展开阅读全文