七桥问题与一笔画

七桥问题与一笔画赤城四小叶考良一、七桥问题的来历18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。河中有两个小岛,一个岛与河的左岸、右岸各有两座桥相连结，另一个岛与河的左岸、右岸各有一座桥相连结，两个岛屿之间也有一座桥相连结。人们经常在桥上走过，一天又一天，７座桥上走过了无数的行人。不知从什么时候起，脚下的桥梁触发了人们的灵感，一个有趣的问题在居民中传开了：谁能够一次走遍所有的７座桥，而且每座桥都只通过一次呢？大家都想找出问题的答案，但是谁也解决不了这个七桥问题。能不能既不重复又不遗漏地一次相继走遍这七座桥？哥尼斯堡七桥问题②①③④⑤⑥⑦能不能既不重复又不遗漏地一次相继走遍这七座桥？把河的两岸、两个小岛看成四个点把七座桥看成是七条线ACDB直到1736年，瑞士著名数学家欧拉才解决了这个问题。数学模型建立好之后，那么“七桥问题”也就转化成了“一笔画问题”一笔画指：1、下笔后笔尖不能离开纸。2、每一条线都只能画一次而不能重复。A→B→C→AA→头部→翅膀→尾部→翅膀→嘴BACBBA（1）凡是从一点出发的线条数目为2、4、6、8……偶数条的，我们称这个点为偶点。（2）凡是从一点出发的线条数目为1、3、5、7……奇数条的，我们称这个点为奇点。FEDCBAACBA→B→C→A这是一些平面图形，同桌请找出下列图形奇点个数，偶点个数。试一试能不能用一笔画出来？请填表，你能发现什么规律？①②③④⑤⑥⑦⑧⑨⑩图号奇点个数偶点个数能否一笔画①41不能②23能③08能④26能⑤05能⑥61不能⑦010能⑧01能⑨80不能⑩21能图号奇点个数偶点个数能否一笔画②23能③08能④26能⑤05能⑦010能⑧01能⑩21能奇点的个数是0或2的连通图。1.当奇点个数是0的时候，任何一个点都可作起点，终点也是这个点；2.当奇点个数是2的时候，起点一定是其中的一个奇点，终点一定是另一个奇点。小组讨论：能够用一笔画的图形有何特征？起点→过路点→…→过路点→终点1、起点和终点重合时，这一点也为偶点，所以奇点个数为0；过路点都是偶点2、起点和终点不重合时，这两点都为奇点，所以奇点个数为2。ADBCA→B→C→D→AA→C1.“七桥问题”如图所示，此图能一笔画出来吗？为什么？答：因为此图奇点的个数是4，所以不能一笔画出来。ACDB2.下列图形能不能用一笔画出来？为什么？FEDCBAACBDFEACDB奇点的个数是8不能一笔画出奇点的个数是0能一笔画出奇点的个数是0能一笔画出奇点的个数是2能一笔画出在七桥问题中，如果允许你再架一座桥，能否不重复地一次走遍这八座桥？这座桥应该架在哪里？请你试一试！ACDBACDBACDBACDBACDBACDBACDB1、甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？生活中的一笔画2、下图是一个公园的平面图，要使游人走遍每一条路不重复，出口和入口应设在哪儿？探究：赛纳河流经巴黎的这一段河中有两个岛，河岸与岛间共架设了15座桥。（l）能否从某地出发，经过这15座桥各一次后再回到出发点？（2）如果不要求回到出发点，能否在一次散步中，穿过所有的桥各一次？：