柯尼斯堡七桥问题（Seven Bridges of Konigsberg）是图论中的著名问题,也是世界上第一个图论问题,这个问题是基于一个现实生活中的事例：当时东普鲁士柯尼斯堡（今日俄罗斯加里宁格勒）市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？
柯尼斯堡平面图(部分)
问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。利用普通数学知识，每座桥均走一次，那这七座桥所有的走法一共有5040种，这么多情况，要一一试验，会是很大的工作量。但怎么才能找到成功走过每座桥而不重复的路线呢？因而形成了著名的“柯尼斯堡七桥问题”。
1735年，有几名大学生写信给当时正在俄罗斯的彼得斯堡科学院任职的天才数学家欧拉,请他帮忙解决这一问题。
1736年29岁的欧拉提交了《柯尼斯堡七桥》的论文，圆满解决了这一问题，同时开创了数学新分支--->图论!
欧拉把问题的实质归于"一笔画"问题，即判断一个图是否能够遍历完所有的边而没有重复，而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。
抽象"七桥"
上图右侧部分,已进行了抽象,线代表桥,五边形代表陆地(与陆地相连"桥的数量"用数字表示);
"一笔画问题"规则抽象:
1.由于不能重复过桥,所以每经过一条线,就必须把刚刚经过的线擦掉;
2.我们每经过一次五角形,此五角形会擦去两条边;
3.五角形是我们的起点,也是终点!
综上,"一笔画问题"必须满足的条件(二选一):
1. 如果起点和终点相同:每个五角形连接的边数,都为偶数
2. 如果起点和终点不同:两个五角形边数是奇数,其它五角形边数都是偶数
对于"七桥问题",4个五角形的边数都为奇数{A结点:3条},{B结点:5条},{C结点:3条},{D结点:3条},不符合完成"一笔画"的任一条件,所以不可能一次走遍七座桥!
本文永久更新地址(欢迎来读留言,写评论):
https://www.v2fy.com/p/2020-12-27-seven-bridges-1609053736000
