哥尼斯堡七桥问题概要.ppt

* 哥尼斯堡七桥问题 哥尼斯堡七桥问题 故事发生在18 世纪欧洲东普鲁士（现为俄罗斯的加里宁格勒）有个名叫哥尼斯堡的城市近郊。这里的普雷盖尔河穿城而过，河中有两个岛，两岸与两岛之间架有七座桥（如图）。 当时城中居民热烈地讨论着这样 一个问题：一个散步者怎样走才 能不重复地走遍所有的七座桥而 回到原出发点？ 这个问题初看起来似乎不太难，所以很多人都想试一试，寻找这种走法，但谁出找不出问题的答案，均以失败告终。 当时大数学家殴拉从众多人的失败中想到，这样的走法可能就根本不存在，随后他用数学的方法证实了自己的猜想是正确的，并于1736 年发表了图论（组合数学的一个分支）的第一篇论文“哥尼斯堡的七座桥”。 主页 A B C D 连接ABCD四点，能一笔画完成（画出三张图） A B C D 连接ABCD四点，不能一笔画完成（画出三张图） 每个人各画一个图，让你的同桌完成 （1）比较你画的图，你能否总结一个规律？ （2）你能找出其中的原因吗？ 一个连通的图形，我们要根据图形中奇点的个数来判断能否一笔画成： （1）凡没有奇点，只偶点的图形，一定可以一笔画成。画时可从任意偶点起笔，最后仍回到这点。 任何图形都是由点、线组成，图形中的点可以分为偶点和奇点两大类。 凡是从一个点出发的线的数目是偶数的叫偶点 。 A A是偶点。 凡是从一个点出发的线的数目是奇数的叫奇点 。 B是奇点。 B 不连通 偶点 偶点 偶点 偶点 （2）凡只有两个奇点的图形，一定可以一笔画成。画时要从一个奇点为起点，另一个奇点为终点。 （3）奇点超过两个的图形就不能一笔画成。 偶点 奇点 偶点 奇点 偶点 奇点 偶点 奇点 偶点 偶点 偶点 偶点 偶点 偶点 偶点 奇点 奇点 下列图形能不能用一笔画出来？ 思考1：下面的图形中有4个奇数点，因此不能一笔画成功。但只要给下图加一条线，这个图形就能一笔画成功。怎么加？ 思考2：下面的图形中有6个奇数点，因此不能一笔画成功。但只要给下图加二条线，这个图形就能一笔画成功。怎么加？ 中国邮递员问题 著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线？此问题由中国数学家管梅谷于1960年首先研究并给出算法。 方法： 奇偶点图上作业法 （1）找出图G中的所有的奇顶点，把它们两两连接，使得新连通图必无奇点。 （2）如果某两个偶顶点连接边重复，可从重复边中去掉偶数条，使得全部都是偶顶点。 （3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。 判定标准1: 在最优邮递路线上，图中的每一条边至多有一条重复边。 判定标准2 : 在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。 A B C D E G H I J K N M L 1 1 1 1 2 2 2 2 1 1 3 2 2 1 2 2 图1 *