七桥问题

问题描述:

18世纪,东普鲁士(今日的德国)的哥尼斯堡(现今叫加里宁格勒,在波罗的海南岸)是一座景致迷人的城市,也是一个在战争中双方必争的战略要地。普勒格尔河横贯其境,并在这儿形成两条支流,把整座城市分割成4个区域(见投影):河的两岸(A和B),河中的岛(克那伊波夫岛)(C)和两条支流之间的半岛(D)。当时有七座桥横跨普勒格尔河及其支流,把河岸、半岛和河心岛连接起来。有趣的桥群和哥城4区的迷人景色吸引了众多的游客,有人在游览时提出这样的问题:能否从某个地方出发,穿过所有的桥各一次后再回到出发点。这个问题在街头流传着,但没有人能回答它。这就是七桥问题,一个著名的图论问题。

解答:

一个图形可以一笔画,必须满足如下两个条件:
1. 图形必须是连通的。
2. 途中的“奇点”个数是0或2。

备注:

奇点:和某个点连接的线的条数是奇数

偶点:和某个点连接的线的条数是偶数

计划、执行、每天高效的活着学着
原文地址:https://www.cnblogs.com/huxiaoyun90/p/3335907.html