图论在中学数学中的渗透

“一笔画问题”；“环球旅行问题”；“着色问题”;“大学招生问题”。第一页第二页，共42页。图论的起源“图论诞生和孕育于民间游戏”第二页第三页，共42页。

哥尼斯堡七桥问题：

哥尼斯堡位于前苏联的加里宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格尔河横穿城堡，河中有两个小岛，共有七座桥连接两岸和小岛。第三页第四页，共42页。ABCD第四页第五页，共42页。

当时，城中的居民热衷于这样一个游戏，从四块陆地的任一块出发，怎样才能做到经过每座桥一次且仅一次，然后回到出发点。问题看来并不复杂，但当地的居民和游人做了不少的尝试，却都没有取得成功。第五页第六页，共42页。第六页第七页，共42页。欧拉将其概括为数学模型，把“七桥”问题变为“一笔画”问题。桥所连接的地区视为点每一座桥视为一条线第七页第八页，共42页。莱昂哈德·欧拉(LeonhardEuler，1707.4.5~1783.9.18)

瑞士的数学家和物理学家。他被称为历史上最伟大的两位数学家之一（另一位是卡尔·弗里德里克·高斯）。欧拉出生于瑞士，在那里受教育。他是一位数学神童。作为数学教授，他先后任教于圣彼得堡(1727-1741)和柏林，尔后再返圣彼得堡(1766)。

欧拉的一生很虔诚，他的离世也很特别：据说当时正是下午茶时间，正在逗孙儿玩的时候，被一块蛋糕卡在喉头窒息而死。

欧拉是第一个使用“函数”来描述包含各种参数的表达式的人，也是把微积分应用于物理学的先驱者之一。

欧拉是有史以来最多产的数学家，他的全集共计75卷。欧拉实际上支配了18世纪的数学，对于当时新发明的微积分，他推导出了很多结果。在他生命的最后7年中，欧拉的双目完全失明，尽管如此，他还是以惊人的速度产出了生平一半的著作。

小行星欧拉2002是为了纪念欧拉而命名的。

第八页第九页，共42页。

下列中的各图是否可以一笔画出?第九页第十页，共42页。Euler迹：经过连通图G的每条边的迹。

第十页第十一页，共42页。欧拉环游：

第十一页第十二页，共42页。一个图若包含Euler环游，则称这个图为Euler图。判断一个图是否可以一笔画问题等价于判断一个图是否是Euler图。定理：一个非空连通图G是Euler图当且仅当它没有“奇度点”。

点的度？第十二页第十三页，共42页。

第十三页第十四页，共42页。第十四页第十五页，共42页。“中国邮递员问题”邮递员的工作是：在邮局里选出邮件，递送邮件，然后再返回邮局。自然，他必须走过他投递范围内的每一条街道至少一次。在这个前提下，希望选择一条尽可能短的路线。

这个问题首先是由中国数学家管梅谷（1962年）研究的，所以又被称为“管梅谷问题”第十五页第十六页，共42页。哈密顿环球旅行问题

十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？

第十六页第十七页，共42页。柏拉图多面体第十七页第十八页，共42页。

“上述问题”“图论中：寻找图G中的Hamilton圈问题”。第十八页第十九页，共42页。Hamilton圈（路）：包含图G的每个顶点的圈（路）Petersen图Hamilton图：一个图若包含Hamilton圈。第十九页第二十页，共42页。

这种路和圈用Hamilton（1856年）的名字命名，是因为他在给他的朋友Graves的一封信中描述了关于十二面体的一个数学游戏：一个人在十二面体的任意五个相继的顶点上插上五根大头针，形成一条路，要求另一个人扩展这条路以形成一个生成圈。“在十二面体中找Hamilton圈”第二十页第二十一页，共42页。第二十一页第二十二页，共42页。第二十二页第二十三页，共42页。公开问题（OpenProblems)

到目前为止，Hamilton图的非平凡的充要条件上不知道；事实上，这是图论中尚未解决的主要经典问题之一第二十三页第二十四页，共42页。Hamilton图的必要或者充分条件：

第二十四页第二十五页，共42页。第二十五页第二十六页，共42页。

第二十六页第二十七页，共42页。G的闭包

第二十七页第二十八页，共42页。

在日常生活中我们常常可以遇到组合数学的问题。比如一个著名的世界难题“四色猜想”：一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。

“四色定理”第二十八页第二十九页，共42页。四色定理的背景：FrancisGuthrie（伦敦大学刚毕业）在1982年提出了四色猜想；Heawood花费毕生精力致力于四色研究，于1980年证明了五色定理；1976年6月，美国数学家K.Appel与W.Haken，在3台不同的电子计算机上，用了1200小时，完成“四色猜想”的证明，从而使“四色猜想”称为了四色定理。第二十九页第三十页，共42页。

用数学语言表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。第三十页第三十一页，共42页。四色定理(Fourcolortheorem)第三十一页第三十二页，共42页。“染色问题”

数学竞赛中的染色问题主要有两类：一类是问题本身就是用染色的方式给出的；另一类是借助于染色方式来解决问题。

这些问题通常涉及到组合数学中的存在性问题、最值问题、构造问题等。常用的方法有抽屉原理、极值原理、反证法、整体处理、分类处理等。第三十二页第三十三页，共42页。例题1：美国数学奥林匹克试题

九名数学家在一次国际数学会议上相遇，发现他们中的任意三个人中，至少有两个人可以用同一种语言对话。如果每个数学家至多可以说三种语言，证明：至少有三名数学家可以用同一种语言对话。第三十三页第三十四页，共42页。问题分析

第三十四页第三十五页，共42页。

第三十五页第三十六页，共42页。

第三十六页第三十七页，共42页。化学药品的存放问题例2：一家公司生产若干种化学制品，其中某些制品是互不相容的，如果存放在一起，则可能发生化学反应，引起爆炸的危险，因此，公司必须用不同的仓库才能保障化学药品的存放安全。问至少用多少仓库才能保证化学药品的存放安全？假设有7中化学制品，用a,b,c,d,e,f,g表示，其中不能存放在一起的是{a,b},{a,d},{b,c},{b,e},{b,g},{c,d}