5.3.1 再谈七桥问题

我们在第一章中已经给出七桥问题的图论模型，但未给出解法。这里先行给出这类所谓“一笔画”问题的一般解法，然后在进一步探讨图模型的其他问题。
   模型的求解与分析
    首先，如果这个图能够一笔画出，则只有两种情况出现， 其一是从一顶点出发走遍所有边一次而回到该顶点 ；其二是从一顶点出发走遍所有边一次后到达另一顶点 。
    其次，图中顶点可分为两种点，一种是过路点，另一种是出发点或结束点。所谓过路点是指沿某条边到达该点后，又从该点沿另一条边走向其它顶点，因此与过路顶点相连接的边的个数必为偶数，称这种顶点为偶顶点 。非偶顶点的顶点称为奇顶点。奇、偶顶点简称 奇点、偶点。
    最后，若一笔画问题是第一种情况，那么，其顶点均应为偶点。事实上，过路点必为偶点，而出发点和结束点重合，必亦为偶点，这时该图中无奇点。如果一笔画问题属于第二种情况，即首尾不重合，过路点仍必为偶点，而出发点与结束点不重合，则意味着出发点与结束点均应为奇点( 与出发点连线至少有一次只出而来回 ，与结束点连线至少有一次只进而未出 )。这时，图中奇点个数应为 2。于是欧拉给出以下的定理 。
    一个连通图能够一笔画的充分必要条件是图中奇点个数为 0或2 。
    注意，一个图称为连通的是指图中所有顶点间都有一条简单开链。七桥问题的图显然是连通图。
    这样，我们便轻松地解决了七桥问题 : 因为问题的图模型中奇点个数为 4, 故不可能无重复地一次走遍七座桥 ，更不必说从一地出发返回原地。
    思考 : 你能设计一座新桥使得能够无重复地一次走遍八桥 ，倘若有机会去哥尼斯堡,您会看到,河上真的建了一座铁路大桥呢!
    关于一笔画问题的更为一般的题目参看“进一步研究的材料”。