下面介绍欧拉图的一些判定定法:
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遍。
上一篇:基于C++的教师档案管理系统的设计与实现
下一篇:ASP.NET通用权限管理系统设计+文献综述

基于Apriori算法的电影推荐

PHP+IOS的会议管理系统的设计+ER图

数据挖掘在电子商务中的应用

数据挖掘的主题标绘数据获取技术与实现

基于PageRank算法的网络数据分析

基于神经网络的验证码识别算法

基于网络的通用试题库系...

AT89C52单片机的超声波测距...

10万元能开儿童乐园吗,我...

医院财务风险因素分析及管理措施【2367字】

C#学校科研管理系统的设计

神经外科重症监护病房患...

国内外图像分割技术研究现状

承德市事业单位档案管理...

中国学术生态细节考察《...

公寓空调设计任务书

志愿者活动的调查问卷表