欧拉图的应用

1、精选优质文档-倾情为你奉上 中图分类号：O157.6本 科 生 毕 业 论 文（设计） （申请学士学位）论文题目 欧拉图的应用 作者姓名 黄 敏 专业名称 数学与应用数学 指导教师 王龙芹 2011年6月4日学 号：论文答辩日期：2011年6月4日指 导 教 师： （签字） 滁州学院本科毕业设计（论文）原创性声明本人郑重声明：所呈交的设计（论文）是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果。本人完全意识到本声明的法律后果由本人承担。作者签名： 年 月 日目 录2 3 32.2中国邮路问题及其算法43.1

2、3.2 3.3 3.4 专心-专注-专业欧拉图的应用摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。欧拉图在现实生活中有着较广泛的应用。本文主要介绍了欧拉图的研究背景、基本概念和常用的判定定理及算法，并利用中国邮路问题算法来解决牛奶配送问题。通过计算得出数据判断此算法的优缺点。关键词：欧拉图；判定定理；中国邮路问题算法；牛奶配送问题中图分类号：0157.6Applications of Euler GraphsAbstract：Euler Graph ori

3、ginates from Konigsberg bridges problem. The Euler path is the one which passes through all the sides once as well as all the vertexes at one time in the graph, with which the graph is called Euler graph, and it is widely used in real life. This essay mainly introduces the background of research on

4、Euler graph, its basic concept, the common judgment theorem and algorithm, puts forward solution to the milk distribution problem by making use of the algorithm for Chinese postman problem, and determines the merits and demerits of this algorithm with data stemmed from calculation.Key words: Euler g

5、raph; Judgment theorem; Algorithm for Chinese postman problem; Milk distribution problem1 研究背景与基本概念欧拉图起源于哥尼斯堡的七桥问题。哥尼斯堡城位于雷格尔河畔，河中有两个岛屿，河两岸与两岛之间通过7座桥彼此相连，如图1所示。当时，人们热衷于这样一个问题：游人从两岸A，D 或两个小岛C、B中任一个地方出发，能否找到一条路线，对每座桥恰通过一次而最后返回原地。问题看来似乎很简单，但经很多人的努力，谁也不能解决这个问题。公元1 736年，欧拉仔细研究了这个问题，他将4块陆地A、B、C、D分别用4个点来表示

6、，若两块陆地之间有一座桥相连，则在这两点之间连一条线。于是，哥尼斯堡七桥问题就变成由点和边所组成的图(见图2)的如下问题：是否存在从图中的任一点出发，经过图中每条边一次且仅一次的路线，最后返回到出发点? 欧拉指出：这样的路线是不存在的。事实上，对每一顶点来说，有一进就必须有一出，这样才能保证从任一点出发，恰好经过每条边一次，最后返回出发点。于是从每一顶点所引出的边均应为偶数，但图中A、B、D引出的边均为3条，而C引出的边为5条，故哥尼斯堡七桥问题无解。下面给出本文经常用到的概念：定义 1 C图：图论中将图定义为一个偶对，其中表示顶点的集合，是无序组集合的一个子集合，集合中的元素在中出现不止一次

7、边的集合。分别用和表示图的顶点集合与边的集合。如果和都是有限集合，则称为有限图，否则称为无限图。若，则称为阶图。定义 2 平凡图：只有一个顶点的图叫做平凡图。定义 3 关联：一条边的端点称为与这条边关联。定义 4 连通：设是图中的两个顶点，若中存在一条道路，则称顶点和是连通的。定义 5 度:设中与顶点关联的边的数目，称为（在中）的度，记作。定义 6 回路：设为图，中顶点与边的交替序列称为到的通路，若，则称通路为回路。(若的所有边各异，则称为简单回路。)定义7 通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的

8、图称为欧拉图。2 预备知识2.1欧拉图的判定定理下面介绍欧拉图的一些判定定理：定理1(1) 图是欧拉图当且仅当是连通图，且中没有奇度顶点。证明：若为平凡图，结论显然成立，下面设为非平凡图，设是条边的阶无向图。并设的顶点集。必要性 因为为欧拉图，所有中存在欧拉回路，设为中任意一条欧拉回路，都在上，因而连通，所以为连通图。又，在上每出现一次获得2度，若出现次就获得度，即，所以中无奇度顶点。充分性 由于为非平凡的连通图可知，中边数。对作归纳法。 (1) 时，由的连通性及无奇度顶点可知，只能是一个环，因而为欧拉图。 (2) 设时结论成立，要证明是结论也成立。由的连通性及无奇度顶点可知，。无论是否为简单

9、图，都可以证明中必含圈，设为中一个圈，删除上的全部边，得生成子图,设有个连通分支，每个连通分支至多有条边，且无奇度顶点，并且设与的公共顶点。由归纳假设可知都是欧拉图，因而都存在欧拉回路。最后将还原（即将删除的边重新加上），并从上的某顶点开始行遍，每遇到，就行遍中的欧拉回路，最后回到，得回路，此回路经过中每条边一次且仅一次并行遍中所有顶点，因而它是中的欧拉回路，故为欧拉图。2.2中国邮路问题及其算法2.2.1 中国邮路问题中国邮递员问题3,5,6，是我国管梅谷教授于1960年首先提出而得名。设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到目的地后返回邮局，要求所走的路径最短。当然如若他所

10、管辖的街道构成一欧拉回路，则这欧拉回路便是所求路径。如若不然，即存在度数为奇数的顶点，必然有些街道需要多走至少1遍，这时用中国邮路问题算法可求出最短路径。现将中国邮路问题用图论的语言描述如下：设是连通图，而且对于所有的，都赋以权，求从点出发，通过所有边至少一次最后返回点的回路，使得达到最小。不失一般性，假定图存在度数为奇数的顶点，如若不然，存在一条欧拉回路，它就是所求的邮路。我们可以设想，有些边添加若干次使得到得图的所有顶点的度数均为偶数，即为欧拉图，问题导致求图的欧拉回路，但图不再是简单图，它具有平行边，设边重复了次，去掉偶数条后，仍保持各顶点的度数为偶数，即所得到的图仍是欧拉图。为使总数达

11、到最小，我们不妨假定每条边重复数目不超过1。仍使邮路达到最短，也就是要求重复边的长度达到最短。设是所求的重复边的集合，使达到最小，对于任一简单回路，可分解为与相交的部分，及其余。2.2.2 引理定理6 (2) 设是使达到最小的重复边集合，当且仅当对于图的任一回路，恒有。证明：必要性.如若不然，假定存在使，这意味部分的权超过其余部分的权，令即。也可作为重复边使图成为欧拉图。这里是对称差。显然，可使图的所有顶点保持其度数为偶数，由于假定 ，故。跟的假设相矛盾.必要性得到了证明。 注意这里分解为与共同部分，还有其余部分，后者出现在中。 充分性证明。假定存在由的边作为重复的边，满足定理的条件：对于任一

12、回路有，可以证明等式 。令 ，则图没有度数为奇数的顶点，可分解成若干简单回路 ，或记以 ，则有 。但 ，故 。同理。即，所以。充分得证。2.2.3 算法从上定理的证明过程提供了构造中国邮路问题的算法。设已知图中顶点的度数为奇数的点为。第一步：从1到，引从到得链，并对的每条边附加一条使成为重复边。第二步：检查图的每条边.若添加的重复边数超过1，则除去其中偶数条，使得每条边之多有一条添加的边，且每一个顶点的度为偶数，从而得图。图中重复边的集合记为。第三步：，(a) 若对于回路有，则作【，转(a)】否则转 (b)。(b) 输出，便是最优集。例题：给出中国邮路问题求解的过程。解：图(a)到图(e)给出

13、了中国邮路问题的求解过程。(a)便是图，其中点是度数为奇数的点，引重复边便得(b)。(b)中不存在重复边数超过1的边。55433332221V7V6V5V4V3V2V1(a)5534v4v3v25433332221V7V6V5V1 (b) 考察回路 ，由于，不满足定理的要求，作。得图(c)，考察(c)中的回路 V5 V65 V3 V25433332221V7V4V1(c)，显然不满足定理的要求，作 。修改(c)得图(d)V5V63V45V3V2543332221V7V1 (d)考察回路 ，。不满足定理，修改得图(e)。V4 5V6V5V2V35433332221V7V1 (e)易知，图(e)满

14、足定理6，故图(e)是欧拉回路。3. 牛奶配送问题目前我国绝大数牛奶生产企业以人工、凭主观、靠经验对配送线路进行优化，也有少部分企业开始借助于信息技术实现配送路线的优化工作，但能够提出完整的物流配送线路优化系统9,10,11,12的企业还非常少。而国外的一些路径优化软件由于交通规则、道路规划等各方面不符合我国国情，很难符合改革中的中国牛奶的管理流程11，因此牛奶配送路径优化问题已成为制约我国牛奶物流发展的主要因素之一。目前，国内外大多数研究很难一次形成合适的配送线路，往往需要辅助很多人工干预和调整，增加了工作的复杂性。本文将中国邮路问题引入配送路径的优化中，在邮路问题中引用指派问题来处理奇点对

15、之间增加重复边12的问题，大大简化了多奇点对之间增加重复边的繁琐性，试图寻求一种新的适合我国牛奶配送系统的路径优化方法，并力求有所突破。3.1 牛奶配送路径优化模型本文结合我国牛奶配送的特点，建立了市区间的牛奶配送路径优化模型13，其前提条件如下：(1)某市牛奶零售网点分布在全市各地，其总体数量大致稳定；(2)该市根据配送辐射半径，将全市划分多个配送区域，并确定每一区域的配送中心及每个配送中心所覆盖的零售网点；(3)零售网点的配送任务由所在区域的牛奶需求量都必须在单车车载量以内，区域内各零售网点所在道路的长度可知；(4)配送车辆有某一区域的配送中心出发，经过该区域内各零售网点，配送完成后车辆返

16、回该物流中心。 符号规定如下：为某牛奶配送区域内零售网点的个数 ； 表示配送路径是否经过个零售网点；为该区域零售网点所在道路形成的边权连通无向图；为道路交叉点的集合，点数，其中表示该区域的牛奶配送中心；表示中所有道路的集合，道路个数，；的长度；、表示中的某两个奇点，（）；为从牛奶配送中心出发经过每个零售网点后重新回到配送中心的一个配送路径；表示配送路径的总长度。3.2 模型描述与建立对于某一个牛奶配送区域，零售网点是固定分布在道路上的，可将配送路径必须经过零售网点的问题转化为必须经过零售网点所在道路的问题，这样如果配送车辆能以最短路线遍行零售网点所在的道路，即能完成送货任务。所以在道路可知的边

17、权连通无向图中 目标函数为: 约束条件为： 该问题在本质上与中国邮递员问题是一致的，故我们把该牛奶配送最短路径问题，转化为求解网络图的中国邮递员问题。3.3 案例应用某市一牛奶企业的物流配送具有客户多、批量小、品种多、时间要求高的特点，该企业按照单车车载量将本市划分为多个区域，每个区域分别由该地区的配送中心来进行分配，如图1是该牛奶企业的某个配送区域，在该区域有12个零售户，则该配送区域构成如下的边权连通无向图，目前该牛奶企业在该地区的配送路线为：配送路径的长度=70。图 (a) 构成的边权连通无向图(1) 找出奇点及奇点数表1 各点对应的度数值奇点度数3233232334332共有8个奇点，

18、分别为，引重复边 便得图(f)。(f)中不存在重复边数超过1的边。(2)考察回路 图 (f)利用中国邮路算法，考察图(f)中回路，不满足定理的要求，作，。得图(m)图 (g)考察图(m)中回路，。满足定理， 。满足定理，。满足定理，。也满足定理。在邮路图中对每个配对奇点之间按照最短路径添加重复边,此图中已没有奇点,并且满足定理6。如图(g)所示。在图(k)中,此时配送路径的长度, 即为该配送区域的最短路径，从配送中心出发找出欧拉回路：此回路即该配送区域内送货车辆的最短行驶路线。显然，求出的最短配送路径远远小于目前该牛奶公司的配送路径长度。考虑到现实配送过程所耗费的人员和车辆等费用后，该牛奶公司

19、改用最短配送路径后可大大提高配送的效率，并将节省大量物流成本。3.4 结论利用中国邮路问题的最短路径算法，能快速求出每个牛奶配送区域内的最短路径和最优路线，使得牛奶配送路径的实时计算成为现实，其成果在牛奶的区域配送系统中具有普遍适用性和广阔的应用前景.但是该方法的主要困难在于检查回路，当图中点、边数较多时，回路的个数将会很多。给算法增加复杂度和计算量。参考文献1，耿素云，张立昂，离散数学M. 北京：高等教育出版社， 2008: 128-170.2卢开澄，卢华明，图论及其应用M.北京：清华大学出版社，1998: 26-2.3王朝瑞，图论M，北京：北京理工大学出版社，2004：41-51.4周炳生， 高向阳， 哈密顿图和欧拉图的一种判别方法J. 广西科学院学报， 2006（01）: 1-5.5王淑栋， 郑惠琴， 关于欧拉图的一个猜想的新结果J. 山东矿业学院学报， 1999(1): 90-95.6陈显强，吴集林，论哈密尔顿图的判定问题J. 广东广播电视大学学报， 2005(1): 106-109.7黄永华， 欧拉图与哈密顿图J. 唐山师专学报