七桥问题

这个问题看似简单，然而许多人作过尝试始终没有能找到答案。因此，一群大学生就写信给当时年仅20岁的大数学家欧拉，请他分析一下。欧拉从千百人次的失败中，以深邃的洞察力猜想，也许根本不可能不重复地一次走遍这七座桥。为了证明这种猜想是正确的，欧拉用简单的几何图形来表示陆地和桥。他是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D 4个点，7座桥表示成7条连接这4个点的线，如图“七桥连线”所示。 七桥连线简化图 再把它简化成图形，就成了右图“七桥连线简化图”。 在说欧拉的推论前，我们先说说偶点和奇点的问题。 奇偶数点图 什么是偶点呢？一个点如果有偶数条边，它就是偶点。如下面“奇偶数点图”的A、B、E、F点。反之，如果一个点有奇条边数，它就是奇点。如图中的C、D这两点。 偶点和奇点与能不能一次通过这座桥有关系吗？别急，我们慢慢来说。 欧拉认为，如果一个图能一笔画成，那么一定有一个起点开始画，也有一个终点。图上其它的点是“过路点”——画的时候要经过它。 “过路点”有什么特点呢？它应该是“有进有出”的点，有一条边进这点，那么就要有一条边出这点，不可能是有进无出或有出无进。如果只进无出，它就是终点；如果有出无进，它就是起点。因此，在“过路点”进出的边总数应该是偶数，即“过路点”是偶点。 如果起点和终点是同一点，那么它也是属于“有进有出”的点，因此必须是偶点，这样图上全体点都是偶点。 如果起点和终点不是同一点，那么它们必须是奇点，因此这个图最多只能有二个奇点。 把上面所说的归纳起来，说简单点就是： 能一笔画的图形只有两类