哥尼斯堡七桥问题

18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?

1736年,29岁的欧拉提交了《哥尼斯堡七桥》的论文,圆满解决了这一问题,同时开创了数学新一分支——图论。

欧拉把每一块陆地考虑成一个点,连接两块陆地的桥以线表示。那么上面的图就被抽象成了下图。

图中的A,B,C,D四个点表示两个岛以及河的两岸。这样抽象以后,假设你从某个顶点出发,那么出去的时候走了一座桥,那么你最后回来也必须有一座桥。这就是说,你的起点的桥的数目必须是偶数的。七桥问题中的每个顶点所连接的桥的数目都是奇数个,所以不存在上面的走法。这个问题的实质就是一笔画,欧拉给出了一笔画的条件。

1. 图形必须是连通的。

2. 图中的“奇点”个数是0或2。

后来也就把图中所有边且每边仅通过一次,最后回到起点的回路,称为欧拉回路。具有欧拉回路的图称为欧拉图。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券