图与网络模型 瑞士数学家欧拉在1736 年发表了一篇题 为“依据几何位置的解决方法”的论文，有 效地解决了哥尼哥尼斯堡“七桥问题”，这 是有史以来的第一篇图论论文，欧拉被公 认为图论的创始人。18 世纪的哥尼斯堡城中流过一 条河。河上游七座桥连接着河的两岸和河中的两个 小岛。当时那里的人们热衷于这样的游戏：一个游 者怎样才能一次连续走过这七座桥而每座桥只走一 次，回到原出发点。没有人想出这种走法，又无法 说明走法不存在，这就是著名的“七桥”难题。欧拉 将这个问题归结图论的问题。他用A,B,C,D 四点表 示河的两岸和小岛，用两点间的连线表示桥。七桥 问题变为：从A,B,C,D 任意点出发，能否通过每条 边一次且 仅一次，再回到原点？欧拉证明了这样的 走法不存在，并给出了这类问题的一般结论。 1857 年，英国数学家哈密顿发明了一种游戏，他用一个实心 正12 面体象征地球，正12 面体的20 个定点分别表示世界上 20 座名城，要求游戏者从任一城市出发，寻找一条可经由每 个城市一次切仅一次再回到原出发点的路，这就是“环球旅行 ”问题。如图53 所示。 他与七桥问题不同，前者要在图中找一
