六、图与网络分析 图论的起源与发展 o欧拉在1736年发表了图论方面的第一篇论文,解决了著名的哥尼 斯堡七桥问题 七桥问题: 口哥尼斯堡城中有二条河叫普雷格尔河,该河中有两个岛,河上有七座 桥。当时那里的居民热衷于这样的问题:一个散步者能否走过七座桥, 且每座桥只走过一次,最后回到出发点。图10-1(a) o欧拉将此间题归结为如图10-1()所示图形的一笔画问题。即能否 从某一点开始,不重复地一笔画出这个图形,最后回到出发点。 欧拉证明了这是不可能的,因为图10-1(b)中的每个点都只与奇数 条线相关联,不可能将这个图不重复地一笔画成。 图10-1 清华大学出版社六、图与网络分析 v 图论的起源与发展 ¢ 欧拉在1736年发表了图论方面的第一篇论文，解决了著名的哥尼 斯堡七桥问题。 ¢ 七桥问题： o 哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座 桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥， 且每座桥只走过一次，最后回到出发点。图10-1(a) ¢ 欧拉将此问题归结为如图10-1(b)所示图形的一笔画问题。即能否 从某一点开始，不重复地一笔画出这个图形，最后回到出发点。 欧拉证明了这是不可能的，因为图10-1(b)中的每个点都只与奇数 条线相关联，不可能将这个图不重复地一笔画成。 图10-1 清华大学出版社 3