七桥问题(七桥问题的起源及解法)

七桥问题是欧拉在18世纪提出的一个著名的问题,该问题描述的是一个城市地图上有七座桥,如何从不重复地走过这七座桥且不重复经过同一桥的两端。欧拉想要找到一个概括性的证明。他将这个问题抽象为一个图论问题,这是图论中的一个经典问题。

下面是解决的过程,第一步要把图简化,即只记录各部分之间的桥的数量,可以发现,在上图中,五个部分的桥的数目都是奇数。我们不妨把起点和终点算在一个部分中,并令它们没有任何一座桥与之相连,这样每个部分就都成了偶数根桥。 其次,在欧拉的解答中,他证明了这个问题的答案要么是0,要么是2,后来人们又发现了一种更为简单的证明,这个问题的答案必然是偶数。最后,我们可以通过参考欧拉拟出的这张图,既不走重走,又不走漏走,解决七桥问题。

相关信息