欧拉图的判定方法及其在实际生活中的应用(2)
下面介绍欧拉图的一些判定定法：
2.1用欧拉图的定义来判定
定义1 经过图G的每条边一次且仅一次的路径，称为欧拉路径。经过图G的每条边一次且仅一次的回路，称为欧拉回路。具有欧拉回路的图称为欧拉图。
定义2 有向连通图D含有欧拉通路，当且仅当该图为连通图且D中除两个结点外，其余每个结点的入度=出度，且此两点满足deg－(u)-deg+(v)=±1。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的入度=出度)。
如图3可用定义判定为欧拉图：
2.2用定理来判定
定理1 一个无向连通图是欧拉图的充分必要条件是图中各点的度数为偶数 。
定理2 设图G是有向连通图，图G是欧拉图的充分必要条件是图中每个顶点的入度和出度相等。
定理3 有向图D是单向连通的半欧拉图，且D中恰有两个奇度顶点，其中一个的入度比出度大1，相反，另一个的出度比入度大1，而其余顶点的入度都等于出度 。
3.欧拉图在实际生活中的应用
3.1一笔画问题
所谓“一笔画问题”就是画一个图形，笔不离开纸，每条边只画一次不许重复地画完该图。“一笔画问题”本质上就是一个无向图是否存在欧拉通路（回路）的问题。如果该图为欧拉图，则能够一笔画完该图，并且笔能回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。
3.1.1欧拉图中一笔画原理
(1)一笔画必须是连通的(图形的各部分之间连接在一起)；
(2)没有奇点的连通图形是一笔画，画时可以以任一偶点为起点，最后仍回到这点；
(3)只有两个奇点的连通图形是一笔画，画时必须以一个奇点为起点，以另一个奇点为终点；
(4)奇点个数超过两个的图形不是一笔画。
综合成一条判定法则：
有0个或2个奇点的连通图能够一笔画成，否则不能一笔画成;能够一笔画成的图形，叫做“一笔画”。
如图4和图5所示：图4 一笔画图
图4 一笔画图
图5 非一笔画图
3.2 中国邮路问题
中国邮路问题是著名图论问题之一，假使一名邮递员从邮局出来送信，必须让他经过辖区内的每条街，且不能有没经过的街道（可以重复经过），然后重新回起点。在此条件下，怎样选择一条才是最短路线?
1960年，我国管梅谷教授首先提出这样的中国邮路问题。管梅谷通过给出奇偶点图上作业法的方法解决这一问题。同样Edmonds 等科学家对于中国邮递员问题也进行了必要改进, 较前者而言，计算更为有效。最终，管梅谷详细综述了中国邮递员问题的研究情况，并指出最为可行且符合中国国情的邮路方法。
早期关于中国邮路问题是在基于无向图的情况下进行讨论的,事实上,由于无向图自身的弊端（单行线或上下行路线的坡度等原因）, 这一问题的研究和解决有时就必须借助于有向图。因此，目前,该问题主要是从图论各种启发式算法或递推算法的角度展开研究的。众所周知，借助相关数学逻辑求解起来比较方便、 易于修改,对于解决、建模分析大型问题也是运用了其优点。本文的研究是结合离散数学、数据结构等相关知识来进行。
中国邮路问题解法就是设邮递员从邮局出发，若要求他所走的路径最短，且要遍历所管辖的每一条街道，然后将信件送到目的地后再返回邮局。如果他管辖的街道可以构成一欧拉回路，则所要的最短路径就是这条欧拉回路。如若不然，也就是顶点的度数是奇数，这时所求的最短路径必然有些街道需要多走至少1遍。