欧拉图在生活中的应用论文

LiaoningNormalUniversity（2013届）本科生毕业论文(设计)题目：欧拉图在生活中的应用学院：数学学院专业：数学与应用数学班级序号：11班22号学号：20111122060022学生姓名：陈旭指导教师：张楠2013年5月i目录摘要......................................................................1Abstract..................................................................1前言......................................................................21欧拉图问题提出的研究背景和定义..........................................31﹒1问题提出的研究背景...............................................31﹒2定义.............................................................32欧拉图的判定定理和实例..................................................42﹒1欧拉图的判定定理.................................................42﹒2欧拉图实例.......................................................53欧拉图的应用............................................................83﹒1中国邮递员问题及算法.............................................83﹒2牛奶配送问题....................................................13参考文献.................................................................17致谢.....................................................................18第1页欧拉图在生活中的应用摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。欧拉图在现实生活中有着较广泛的应用。本文主要介绍了欧拉图问题提出的研究背景、相关概念和常用的判定定理、判别法及算法以及欧拉图在生活中的实际应用例子。关键词：欧拉图；判定定理；算法；应用。Abstract:EulergraphoriginatedinKonigsbergsevenBridgesproblem,allthroughthepictureedgeonceandonlyoncetraveledalltheverticesinthegraphofpathwayscalledEulerpath,allthroughthepictureedgeonceandoncetraveledallverticesofEulercircuit.WithEulercircuitdiagramcalledEulergraph.Eulergraphhasawideapplicationinreallife.Eulergraphproblemismainlyintroducedinthispaperputsforwardtheresearchbackground,relatedconceptsandcommondecisiontheorem,Eulergraphmethodandalgorithmaswellaspracticalapplicationexampleinthelife.Keywords:Eulergraph;Judgmenttheorem;Algorithm;Application.欧拉图在生活中的应用第2页前言图论是近210年来发展十分迅速、应用比较广泛的一个新兴的数学分支，19世纪末期，图论已经用来研究电网络方程组和有机化学中的分子结构；20世纪中叶以后，借助于计算机，图论又用来求解生产管理、军事、交通运输、计算机以及通信网络等领域中的许多离散性问题，同时图论中的一些著名问题也借助于计算机科学、电子学、信息论、控制论、网络理论、社会科学和管理科学等领域中，因此受到全世界越来越广泛的重视。图论的内容十分丰富，涉及面也比较广。本文章所涉及的只是图论中的欧拉图的问题提出背景、一些基本定义、判定定理和生活中的应用。欧拉图是由哥尼斯堡七桥问题诞生的，讲述的是：18世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流，河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。这个问题困扰了人们许多年，成千上万的人试过了，但都没有成功。这个问题引起了欧拉的注意，为了寻找答案，欧拉对此问题进行观察、思考和研究，终于解决了这一难题，就是我们现在学习的欧拉图的判定方法。最后讲述了欧拉图在生活中的应用问题，是本文的重要组成部分。运用欧拉图的相关定理来解决生活中的实际应用问题任重而道远，需要我们共同努力为国家贡献力量！欧拉图在生活中的应用第3页1欧拉图问题提出的研究背景和定义1﹒1问题提出的研究背景18世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流（普雷格尔河），河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。这个问题困扰了人们许多年，成千上万的人试过了，但都没有成功。这个问题引起了欧拉的注意，为了寻找答案，欧拉对此问题进行观察、思考和研究，“也许并不存在这样的走法？”为了证明自己的猜想，他首先考虑到了集合中的“列举法”，但检验起来却十分麻烦，而且在同样的问题中，如果桥更多，那么“列举法”就无使用价值了，因此他放弃了这个方法，后来他改变了思考的角度，发现七桥问题仅仅涉及物体的位置关系，而与路程无关，于是他用点A、B表示岛屿，点C、D表示河的两岸，用连接两点的线表示桥，这样就可以画出如图1-1所示的无向图，这个问题就转化为“能否一笔画出该无向图且最后返回起点”。哥尼斯堡城七桥问题是否有解，就相当于这个无向图是否存在经过图中每条边一次且仅一次的简单回路。我们知道，从某一个点出发最后又回到这个点，经过这一点的边的条数一定是偶数；经过中间的每一点，有进去的一条边，又有出来的一条边，因此，经过这些点的边的条数也是偶数。根据这个道理，我们可以看到图中经过每一点巧妙地解决了这个困扰人们多年但又十分有趣的问题。那这个方法也就成了我们现在学习的欧拉图的判定方法。图1-11﹒2定义定义1图：图论中将图定义为一个偶对EVG,，其中V表示顶中点的集合，E是无序组集合VV的一个子集合，集合VV中的元素在E出现不止一次边的集合。分别用GV和GE表示图G的顶点集合与边的集合。如果GV和GE都是有限集合，则称G为有限图，否则称为无限图。若nGV，则称G为n阶图。定义2平凡图：只有一个顶点的图叫做平凡图。定义3关联：一条边的端点称为与这条边关联。定义4连通：设vu,是图G中的两个顶点，若G中存在一条vu,道路，则称顶点u和v是连通的。定义5度：设G中与顶点v关联的边的数目，称为v（在G中）的度，记作vd。定义6回路：设G为图，G中顶点与边的交替序列2110jjjievev…llijve称为0iv到liv的通路，若loiivv，则称通路为回路。（若的所有边各异，则称G为简单回路。）欧拉图在生活中的应用第4页定义7通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。定义8给定有向图D，经过D中每边一次且仅一次的有向迹称为有向欧拉图；经过D中每边一次且仅一次的有向闭迹(回路)称为有向欧拉回路。定义9含欧拉回路的无向连通图与含有向欧拉回路的弱连通有向图，统称为欧拉圈。定义10欧拉闭迹：经过图G的每条边恰好一次的闭迹。定义11欧拉迹：经过每条恰好一次的迹。2欧拉图的判定定理和实例2﹒1欧拉图的判定定理下面介绍欧拉图的一些判定定理：引理：设EVG,一般图，如果它的每个顶点的度数都是偶数，则G的每条边都属于一条闭迹，因而也属于一个圈。证明：利用下面的算法，可以找到一条包含任意指定边101,xx的闭迹。在该算法中，我们要构造一个顶点集W和一个边集F。求闭迹的算法i)令1iii)令10,xxWiii)令1Fiv)当0xxi时，执行a)找出一个不在F中的边11,iiixx。b)将1ix放人W中（也许1ix已在W中）。c)将1i放入F中。d)令1ii。这样，经过i)～iii)步初始化以后，在算法中的，我们都要找到一条新边11,iiixx，它邻接于最后一次放入W中的顶点ix，再将1ix和1i分别放入W和F中，并使i的值增1.重复这个过程，直到最终又到达0x为止。假设只要0xxi时，满足iv)a)的一条边1i总存在。设i的终值它为k，所产生的顶点集kxxxW,,,10，边的多重集kF,,1，于是，根据算法得到的k,1就是包含初始边1的一条闭迹。因此，我们只需证明：如果0xxi，那么就有一个不在F中的边与ix邻接。正是在这里，用到了偶度次顶点的假设。容易看到：算法中每步iv)的d)结束时，一般图FWH,的每个顶点都具有偶度次，只有顶点0x（它起始于奇度1）和最新加入的顶点ix（它的度数刚刚增加1）可能除外。此外，0x和ix具有偶度次，当且仅当ixx0，因此，如果0xxi，则ix在一般图H中就具有奇度次。既然ix在一般图G中具有偶度次，则必存在一个还不属于F的边11,iiixx与ix邻接。所以，当算法结束时，必有0xxk，从而式k,1是一条闭迹。由于一条闭迹中的边可以被划分为圈，所以我们完成了引理的证明。定理1设G是一个连通一般图，则G中存在闭欧拉迹，当且仅当G中每个顶点的度数欧拉图在生活中的应用第5页是偶数。证明：我们已经观察到了：如果G中有一条闭欧拉迹，则G的每个顶点都具有偶度次。现在设211,EVG是一个连通一般图，且它的每个顶点都具有偶度次，我们选定1G的任意一条边1，并应用引理证明中给出的求闭迹的算法，求得一条包含边1的闭迹1。令222,EVG是去掉1E中属于闭迹1的边后得到的一般图，则2G的所有顶点都具有偶度次。如果2E中至少含有一条边，则由于1G的连通性，2G中至少有一条边2与闭迹1中的某个顶点1z邻接，我们对2G和边2应用算法求出一条包含边2的闭迹2。现在我们把1和2在顶点1z处拼接在一起，得到一条包含1和2的所有边的闭迹211z。令333,EVG是2E中去掉2的边后得到的一般图，如果3E中至少含有一条边，则它必有一条边3与闭迹211z中的某个顶点2z邻接，再对3G和边3应用算法，求得一条包含边3与闭迹3，又将211z和3在顶点2z出拼接，得到一条包含1，2和3的所有边的闭迹32121zz。重复上述过程，直到所有的边都包含在一条闭迹kzzzk12121中为止。因此，重复调用求闭欧拉迹的算法。定理2设G是一个连通的一般图，则G中存在一条开欧拉迹，当且仅当G中恰好有两个奇度顶点u和v。此外，G中