离散数学-教案 -第6章 6.1欧拉图 6.2哈密顿图

课堂教学设计20章节（专题）第6章特殊的图计划学时2课题（内容）6.1欧拉图6.2哈密顿图教育教学目的1.理解哈密顿通路与哈密顿回路的定义2.掌握哈密顿通路和哈密顿回路的充分条件和必要条件3.掌握哈密顿图的应用4.掌握欧拉通路与欧拉回路5.理解存在欧拉通路和欧拉回路的充分必要条件6.思政目标：介绍欧拉图时，融入中国古代数学成就与现代数学发展，以及我国当代数学家在图论领域的重要贡献，让学生了解我国数学发展的悠久历史和卓越成就，增强学生的民族自豪感和文化自信。教学重点及难点1.重点：哈密顿图、哈密顿通路与哈密顿回路及其判定、欧拉图2.难点：哈密顿通路与哈密顿回路的充分条件和必要条件、哈密顿图的判定定理最短路径，欧拉图的判定定理教学方法及手段1.讲授法2.互动式教学3.多媒体辅助教学教学互动环节设计1.课程回顾导入新课（回路、通路）2.启发式提问引发课堂讨论（哈密顿图的判定，给出几幅图，请同学们判定是不是哈密顿图。）3.哥尼斯堡七桥问题引发思考4.启发式提问引发课堂讨论（欧拉通路与欧拉回路的判定）课后总结与反思第6章特殊的图6.1哈密顿图问题引入：哈密顿周游世界问题下图中每个顶点是一个城市,有20个城市,要求从一个城市出发,恰好经过每一个城市一次,回到出发点。存不存在这样一条路径？上图中，左图和右图是同构的，即如果右图中存在这样一条路径满足上述条件，则在左图中也会存在这样一条路径。如何判定有没有这样一条路就是我们今天要学习的内容。哈密顿图的定义哈密顿通路:经过图中所有顶点一次且仅一次的通路。哈密顿回路:经过图中所有顶点一次且仅一次的回路。哈密顿图:具有哈密顿回路的图。半哈密顿图:具有哈密顿通路而无哈密顿回路的图。几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路。环与平行边不影响图的哈密顿性。实例：判断下面几幅图是否为哈密顿图，是否为半哈密顿图。上图中，第一幅图和第二幅图符合哈密顿回路的定义，是哈密顿图，第三幅图符合哈密顿通路的定义，是半哈密顿图，而最后一幅图不满足二者的定义，因此既不是哈密顿图也不是半哈密顿图。无向哈密顿图的一个必要条件定理：设无向图G=<V,E>是哈密顿图,则对于任意V1V且V1,均有p(G-V1)|V1|。证设C为G中一条哈密顿回路,有p(C-V1)|V1|。又因为CG,故p(G-V1)p(C-V1)|V1|。几点说明：1.定理中的条件是哈密顿图的必要条件,但不是充分条件。2.可利用该定理判断某些图不是哈密顿图。3.由定理可知,Kr,s当sr+1时不是哈密顿图。4.当r2时,Kr,r是哈密顿图,而Kr,r+1是半哈密顿图。实例：设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证(1)证(1)设v为割点,则p(Gv)2>|{v}|=1.根据定理,G不是哈密顿图。(2)若G是K2(K2有桥),它显然不是哈密顿图.除K2外,其他的有桥连通图均有割点.由(1),得证G不是哈密顿图.无向哈密顿图的充分条件定理：设G是n阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n-1,则G中存在哈密顿通路.当n3时,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路。由定理,当n3时,Kn均为哈密顿图。定理中的条件是充分条件,但不是必要条件。例如,n(6)个顶点的路径存在哈密顿通路,但不满足条件。n(5)个顶点的圈是哈密顿图,不满足条件。判断是否是哈密顿图的可行方法1.观察出一条哈密顿回路例如下图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图。2.满足充分条件例如当n3时,Kn中任何两个不同的顶点u,v,均有d(u)+d(v)=2(n-1)n,所以Kn为哈密顿图。3.不满足必要条件例例44国际象棋盘上的跳马问题:马是否能恰好经过每一个方格一次后回到原处?解：每个方格看作一个顶点,2个顶点之间有边当且仅当马可以从一个方格跳到另一个方格,得到16阶图G,如左图红边所示.取V1={a,b,c,d},则p(GV1)=6>|V1|。由定理,图中无哈密顿回路,故问题无解。应用实例例1某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？解解作无向图G=<V,E>,其中V={v|v为与会者}，E={(u,v)|u,vV,u与v有共同语言,且uv}。G为简单图。根据条件,vV,d(v)4。于是，u,vV,有d(u)+d(v)8。由定理可知G为哈密顿图。服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可。ABCDABCD根据定理,竞赛图中一定有哈密顿通路,当然也可能有哈密顿回路。当没有哈密顿回路时,通常只有一条哈密顿通路,这条通路给出参赛队的惟一名次。例如,CABD是一条哈密顿通路,它没有哈密顿回路,比赛结果是C第一,A第二B,C第三,D第四。6.2欧拉图哥尼斯堡七桥问题是否存在一条路线：从某一地点出发，通过每座桥恰好一次，再回到出发点？要求边不重复地一笔画出整个图。①欧拉图欧拉通路:图中行遍所有顶点且恰好经过每条边一次的通路.(能一笔画)欧拉回路:图中行遍所有顶点且恰好经过每条边一次的回路.欧拉图:有欧拉回路的图.半欧拉图:有欧拉通路回路,但无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.课程思政：介绍欧拉图相关理论时，融入中国古代数学成就与现代数学发展，如中国古代在图论思想方面的早期探索，以及我国当代数学家在图论领域的重要贡献，让学生了解我国数学发展的悠久历史和卓越成就，增强学生的民族自豪感和文化自信。同时，通过欧拉图解决实际问题带来的社会价值，培养学生对数学学科的热爱，激发学生投身科学研究、用数学知识服务社会的热情，树立正确的价值观和科学情怀。例是否是欧拉图或半欧拉图?②欧拉图的判别法请归纳：‘结点的度数’与‘是否存在通路或回路的关系’？欧拉图不是欧拉图但存在欧拉通路欧拉图不是欧拉图但存在欧拉通路不存在欧拉通路当连通图的各个顶点都是偶数度时，该图可以一笔画，且始点与终点重合。——形成回路——当一个图仅有两个奇数度点时，该图也可以一笔画，但必须把其中一个奇数度点作为起点，另一个奇数度点作为终点。——形成通路——定理无向图G为欧拉图当且仅当G连通且无奇度顶点.G是半欧拉图当且仅当G连通且恰有两个奇度顶点.定理有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.D是半欧拉图当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.欧拉图的判定：连通图的无向图（1）计算所有结点的度数。（2）存在0个奇度数结点则有欧拉回路，是欧拉图；存在2个奇度数结点则有欧拉通路。连通图的有向图（1）计算所有结点的出度和入度。（2）所有结点的入度等于出度则有欧拉回路，是欧拉图；两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1，则有欧拉通路。练习：通过定理来判断以下哪些图有欧拉通路和欧拉回路?例1哥尼斯堡七桥问题4个奇度顶点,不存在欧拉通路,更不存在欧拉回路,例2下面两个图都是欧拉图.（一笔画问题）从A点出发,如何一次成功地走出一条欧拉回路来？例3如图所示，四个村庄下面各有一个防空洞甲、乙、丙、丁，相邻的两个防空洞之间有地道相通，并且每个防空洞各有一条地道与地面相通，能否每条地道恰好走过一次，既无重复也无遗漏？定义11.2.2设G=<V,E>，e∈E，如果p(G-e)＞p(G)称e为G的桥(Bridge)或割边(Cutedge)。显然，所有的悬挂边都是桥。（v3-v4）求欧拉图G=<V,E>的欧拉回路的Fleury算法：（1）任取v0∈V，令P0=v0，i=0；（2）按下面的方法从E-{e1,e2,…,e