欧拉图的应用

中图分类号：O157.6本科生毕业论文（设计）（申请学士学位）论文题目欧拉图的应用作者姓名黄敏专业名称数学与应用数学指导教师王龙芹2011年6月4日学号：2007211364论文答辩日期：2011年6月4日指导教师：（签字）滁州学院本科毕业设计（论文）原创性声明本人郑重声明：所呈交的设计（论文）是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果。本人完全意识到本声明的法律后果由本人承担。作者签名：年月日目录摘要................................................................错误!未定义书签。Abstract.............................................................错误!未定义书签。1.背景和基本概念...................................................................22.预备知识.........................................................................32.1欧拉图的判定定理..............................................................32.2中国邮路问题及其算法..........................................................43.牛奶配送问题.....................................................................93.1牛奶配送路径优化模型.........................................................93.2模型描述与建立..............................................................103.3案例应用....................................................................113.4结论........................................................................14参考文献...........................................................................15致谢...............................................................................161欧拉图的应用摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。欧拉图在现实生活中有着较广泛的应用。本文主要介绍了欧拉图的研究背景、基本概念和常用的判定定理及算法，并利用中国邮路问题算法来解决牛奶配送问题。通过计算得出数据判断此算法的优缺点。关键词：欧拉图；判定定理；中国邮路问题算法；牛奶配送问题中图分类号：0157.6ApplicationsofEulerGraphsAbstract：EulerGraphoriginatesfromKonigsbergbridgesproblem.TheEulerpathistheonewhichpassesthroughallthesidesonceaswellasallthevertexesatonetimeinthegraph,withwhichthegraphiscalledEulergraph,anditiswidelyusedinreallife.ThisessaymainlyintroducesthebackgroundofresearchonEulergraph,itsbasicconcept,thecommonjudgmenttheoremandalgorithm,putsforwardsolutiontothemilkdistributionproblembymakinguseofthealgorithmforChinesepostmanproblem,anddeterminesthemeritsanddemeritsofthisalgorithmwithdatastemmedfromcalculation.Keywords:Eulergraph;Judgmenttheorem;AlgorithmforChinesepostmanproblem;Milkdistributionproblem21研究背景与基本概念欧拉图起源于哥尼斯堡的七桥问题。哥尼斯堡城位于雷格尔河畔，河中有两个岛屿，河两岸与两岛之间通过7座桥彼此相连，如图1所示。当时，人们热衷于这样一个问题：游人从两岸A，D或两个小岛C、B中任一个地方出发，能否找到一条路线，对每座桥恰通过一次而最后返回原地。问题看来似乎很简单，但经很多人的努力，谁也不能解决这个问题。公元1736年，欧拉仔细研究了这个问题，他将4块陆地A、B、C、D分别用4个点来表示，若两块陆地之间有一座桥相连，则在这两点之间连一条线。于是，哥尼斯堡七桥问题就变成由点和边所组成的图(见图2)的如下问题：是否存在从图中的任一点出发，经过图中每条边一次且仅一次的路线，最后返回到出发点?欧拉指出：这样的路线是不存在的。事实上，对每一顶点来说，有一进就必须有一出，这样才能保证从任一点出发，恰好经过每条边一次，最后返回出发点。于是从每一顶点所引出的边均应为偶数，但图中A、B、D引出的边均为3条，而C引出的边为5条，故哥尼斯堡七桥问题无解。下面给出本文经常用到的概念：定义1图：图论中将图定义为一个偶对(,)GVE，其中V表示顶点的集合，E是无序组集合VV的一个子集合，集合VV中的元素在E中出现不止一次边的集合。分别用()VG和()EG表示图G的顶点集合与边的集合。如果()VG和()EG都是有限集合，则称G为有限图，否则称为无限图。若()VGn，则称G为n阶图。定义2平凡图：只有一个顶点的图叫做平凡图。定义3关联：一条边的端点称为与这条边关联。C3定义4连通：设,uv是图G中的两个顶点，若G中存在一条(,)uv道路，则称顶点u和v是连通的。定义5度:设G中与顶点v关联的边的数目，称为v（在G中）的度，记作()dv。定义6回路：设G为图，G中顶点与边的交替序列0112llijijjiveveev称为0iv到liv的通路，若0liivv，则称通路为回路。(若的所有边各异，则称G为简单回路。)定义7通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。2预备知识2.1欧拉图的判定定理下面介绍欧拉图的一些判定定理：定理1([1])图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。证明：若G为平凡图，结论显然成立，下面设G为非平凡图，设G是m条边的n阶无向图。并设G的顶点集12{,,}nVvvv。必要性因为G为欧拉图，所有G中存在欧拉回路，设C为G中任意一条欧拉回路，,ijvvV，,ijvv都在C上，因而,ijvv连通，所以G为连通图。又ivV，iv在C上每出现一次获得2度，若出现k次就获得2k度，即()2idvk，所以G中无奇度顶点。充分性由于G为非平凡的连通图可知，G中边数1m。对m作归纳法。(1)1m时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图。(2)设(1)mkk时结论成立，要证明1mk是结论也成立。由G的连通性及无奇度顶点可知，()2G。无论G是否为简单图，都可以证明G中必含圈，设C为G中一个圈，删除C上的全部边，得G生成子图G,设G有s个连通分支12,,,sGGG，每个连通分支至多有k条边，且无奇度顶点，并且设iG与C的公共顶点*,1,2,,ijvis。由归纳假设可知12,,,sGGG都是4欧拉图，因而都存在欧拉回路,1,2,,iCis。最后将C还原（即将删除的边重新加上），并从C上的某顶点rv开始行遍，每遇到*ijv，就行遍iG中的欧拉回路,1,2,,iCis，最后回到rv，得回路1122******ssrjjjjjjrvvvvvvvv，此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路，故G为欧拉图。2.2中国邮路问题及其算法2.2.1中国邮路问题中国邮递员问题[3,5,6]，是我国管梅谷教授于1960年首先提出而得名。设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到目的地后返回邮局，要求所走的路径最短。当然如若他所管辖的街道构成一欧拉回路，则这欧拉回路便是所求路径。如若不然，即存在度数为奇数的顶点，必然有些街道需要多走至少1遍，这时用中国邮路问题算法可求出最短路径。现将中国邮路问题用图论的语言描述如下：设(,)GVE是连通图，而且对于所有的eE，都赋以权()0ce，求从点vV出发，通过所有边至少一次最后返回v点的回路C，使得()eCce达到最小。不失一般性，假定图(,)GVE存在度数为奇数的顶点，如若不然，存在一条欧拉回路，它就是所求的邮路。我们可以设想，有些边添加若干次使得到得图(,)aaGVE的所有顶点的度数均为偶数，即aG为欧拉图，问题导致求aG图的欧拉回路，但图aG不再是简单图，它具有平行边，设e边重复了(2)k次，去掉偶数条后，仍保持各顶点的度数为偶数，即所得到的图仍是欧拉图。为使总数()eCce达到最小，我们不妨假定每条边重复数目不超过1。仍使邮路达到最短，也就是要求重复边的长度达到最短。设*E是所求的重复边的集合，使**()()eEWEce达到最小，对于任一简单回路C，可分解为与*E相交的部分*()ECE，及其余*()\ECE。52.2.2引理定理6([2])设*EE是使**()()eEWEce达到最小的重复边集合，当且仅当对于aG图的任一回路C，恒有**(())(()\)WECEWECE。证明：必要性.如若不然，假定存在C使**(())(()\)WECEWECE，这意味*()ECE部分的权超过其余*()\ECE部分的权，令*()EECE即**(())\(())EECEECE。E也可作为重复边使G图成为欧拉图。这里是对称差。显然，E可使图G的所有顶点保持其度数为偶数，由于假定**()()\()()eECEeECEcece，故*eEeEc(e)c(e)。跟*E的假设相矛盾.必要性得到了证明。注意这里*E分解为与()EC共同部分，还有其余部分，后者出现在E中。充分性证明。假定存在(),1,2,iEEi由()iE的边作为重复的边，满足定理的条件：对于任一回路C有()()()()\()(),1,2iieECEeECEcecei，可以证明等式(1)(2)()()eEeEcece。令*(1)(2)EEE，则图**(,)GVE没有度数为奇数的顶点，*E可分解成若干简单回路12,,,hCCC，或记以*(1)(2)12hEEECCC，6则有(1)(1)()()\()(),1,2,,iieECEeECEceceih。但(1)(2)()\()iiECEECE，故(1)(2)()\()()(),1,2,,iieECEeECEceceih。同理(2)(2)(1)()()\()()()(),1,2,,