第五节 Euler图

这是由哥尼斯堡七桥问题和Hamilton周游世界问题引出的图论问题。Euler图简称为E图，也称一笔画问题或遍历问题，是很有实际意义的。形象地说，E图就是从任一顶点出发通过每一条边恰好一次又能回到出发点的图。

设有一个连通多重图G，如果在G中存在一条链，经过G的每条边一次且仅一次，那么这条链叫做欧拉链。如在G中存在一个简单圈，经过G的每条边一次且仅一次，那么这个圈叫做欧拉圈。一个图如果是欧拉圈，那么这个图叫做欧拉图。很明显，一个图G如果能够一笔画出，那么这个图一定是欧拉图或者含有欧拉链。

定理5-1：一个连通多重图G是欧拉图的充分必要条件是G中无奇点。

证：必要性，显然。

充分性，不妨设，连通多重图G至少有三点，对G的边数q用数学归纳法。因为G是连通的，并且不含奇点，故q>=3。

当q=3时，显然G是欧拉图。假设q=n时成立，看q=n+1的情形：由于G是无奇点的连通图，并且G的点数p>=3，因此存在三个点μ，v，w,使得[μ,v],[w,v]∈E。从G中去掉边[μ,v],[w,v]，增加新的边[μ,w]，得到一个新的多重图G₁，G₁有q-1条边，且仍不含奇点，G₁至多有两个分图。

若G₁是连通的，则由归纳假设，G₁有欧拉圈C₁。把C₁中的边[w,μ]换成[μ,v],[w,v]，即是G中的欧拉圈。若G₁有两个分图G₁^’，G₁^’’，令v在G₁^’中。由归纳假设，G₁^’，G₁^’’分别有欧拉圈C₁^’，C₁^’’，把C₁^”中的边[μ,w]换成[μ,v]，C₁^’及[v,w]即是G中的欧拉圈。

推论：一个多重连通图G是欧拉链的充分必要条件是G有且仅有两个奇点。

一个连通图能否一笔画出的条件是它的奇点数。若有两奇点，就能一笔画出(欧拉链)。若没有奇点，就能够一笔画出，并回到原出发地。两个以上奇点肯定不能一笔画出。

比如前面提到的哥尼斯堡七桥问题，欧拉把它抽象成具有四个项点，并且都是奇点，见图5-20。很明显，一个漫步者无论如何也不可能重复的走完七座桥，并最终回到原出发地。

图5-20