欧拉图的应用

中图分类号：O157.6 本 科 生 毕 业 论 文（ 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ） （申请学士学位） 论文题目         欧拉图的应用              作者姓名         黄 敏              专业名称             数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 与应用数学        指导教师               王龙芹             2011年6月4日 学        号：2007211364 论文答辩日期：2011年6月4日 指 导 教 师：            （签字） 滁州学院本科 毕业设计 机械毕业设计下载球磨机的毕业设计下载关于网络爬虫的毕业设计下载关于网络爬虫的毕业设计下载河南城建学院毕业设计论文下载 （论文）原创性声明 本人郑重声明：所呈交的设计（论文）是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 或撰写的成果。本人完全意识到本声明的法律后果由本人承担。 作者签名：            年    月    日 目 录 摘要    1 Abstract    1 1. 背景和基本概念    2 2. 预备知识    3 2.1欧拉图的判定定理    3 2.2中国邮路问题及其算法    4 3. 牛奶配送问题    9 3.1 牛奶配送路径优化模型    9 3.2 模型描述与建立    10 3.3 案例应用    11 3.4 结论    14 参考文献    15 致谢    16 欧拉图的应用 摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。欧拉图在现实生活中有着较广泛的应用。本文主要介绍了欧拉图的研究背景、基本概念和常用的判定定理及算法，并利用中国邮路问题算法来解决牛奶配送问题。通过计算得出数据判断此算法的优缺点。 关键词：欧拉图；判定定理；中国邮路问题算法；牛奶配送问题 中图分类号：0157.6 Applications of Euler Graphs Abstract：Euler Graph originates 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 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 graph; Judgment theorem; Algorithm for Chinese postman problem; Milk distribution problem 1 研究背景与基本概念 欧拉图起源于哥尼斯堡的七桥问题。哥尼斯堡城位于雷格尔河畔，河中有两个岛屿，河两岸与两岛之间通过7座桥彼此相连，如图1所示。当时，人们热衷于这样一个问题：游人从两岸A，D 或两个小岛C、B中任一个地方出发，能否找到一条路线，对每座桥恰通过一次而最后返回原地。问题看来似乎很简单，但经很多人的努力，谁也不能解决这个问题。公元1 736年，欧拉仔细研究了这个问题，他将4块陆地A、B、C、D分别用4个点来表示，若两块陆地之间有一座桥相连，则在这两点之间连一条线。于是，哥尼斯堡七桥问题就变成由点和边所组成的图(见图2)的如下问题：是否存在从图中的任一点出发，经过图中每条边一次且仅一次的路线，最后返回到出发点? 欧拉指出：这样的路线是不存在的。事实上，对每一顶点来说，有一进就必须有一出，这样才能保证从任一点出发，恰好经过每条边一次，最后返回出发点。于是从每一顶点所引出的边均应为偶数，但图中A、B、D引出的边均为3条，而C引出的边为5条，故哥尼斯堡七桥问题无解。 下面给出本文经常用到的概念： 定义 1 C 图：图论中将图定义为一个偶对 ，其中 表示顶点的集合， 是无序组集合 的一个子集合，集合 中的元素在 中出现不止一次边的集合。分别用 和 表示图 的顶点集合与边的集合。如果 和 都是有限集合，则称 为有限图，否则称为无限图。若 ，则称 为 阶图。 定义 2 平凡图：只有一个顶点的图叫做平凡图。 定义 3 关联：一条边的端点称为与这条边关联。 定义 4 连通：设 是图 中的两个顶点，若 中存在一条 道路，则称顶点 和 是连通的。 定义 5 度:设 中与顶点 关联的边的数目，称为 （在 中）的度，记作 。 定义 6 回路：设 为图， 中顶点与边的交替序列 称为 到 的通路，若 ，则称通路为回路。(若 的所有边各异，则称 为简单回路。) 定义7 通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。 2 预备知识 2.1欧拉图的判定定理 下面介绍欧拉图的一些判定定理： 定理1([1]) 图 是欧拉图当且仅当 是连通图，且 中没有奇度顶点。 证明：若 为平凡图，结论显然成立，下面设 为非平凡图，设 是 条边的 阶无向图。并设 的顶点集 。 必要性 因为 为欧拉图，所有 中存在欧拉回路，设 为 中任意一条欧拉回路， ， 都在 上，因而 连通，所以 为连通图。又 ， 在 上每出现一次获得2度，若出现 次就获得 度，即 ，所以 中无奇度顶点。 充分性 由于 为非平凡的连通图可知， 中边数 。对 作归纳法。 (1) 时，由 的连通性及无奇度顶点可知， 只能是一个环，因而 为欧拉图。 (2) 设 时结论成立，要证明 是结论也成立。由 的连通性及无奇度顶点可知， 。无论 是否为简单图，都可以证明 中必含圈，设 为 中一个圈，删除 上的全部边，得 生成子图 ,设 有 个连通分支 ，每个连通分支至多有 条边，且无奇度顶点，并且设 与 的公共顶点 。由归纳假设可知 都是欧拉图，因而都存在欧拉回路 。最后将 还原（即将删除的边重新加上），并从 上的某顶点 开始行遍，每遇到 ，就行遍 中的欧拉回路 ，最后回到 ，得回路 ，此回路经过 中每条边一次且仅一次并行遍 中所有顶点，因而它是 中的欧拉回路，故 为欧拉图。 2.2中国邮路问题及其算法 2.2.1 中国邮路问题 中国邮递员问题[3,5,6]，是我国管梅谷教授于1960年首先提出而得名。设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到目的地后返回邮局，要求所走的路径最短。当然如若他所管辖的街道构成一欧拉回路，则这欧拉回路便是所求路径。如若不然，即存在度数为奇数的顶点，必然有些街道需要多走至少1遍，这时用中国邮路问题算法可求出最短路径。 现将中国邮路问题用图论的语言描述如下： 设 是连通图，而且对于所有的 ，都赋以权 ，求从点 出发，通过所有边至少一次最后返回 点的回路 ，使得 达到最小。 不失一般性，假定图 存在度数为奇数的顶点，如若不然，存在一条欧拉回路，它就是所求的邮路。我们可以设想，有些边添加若干次使得到得图 的所有顶点的度数均为偶数，即 为欧拉图，问题导致求 图的欧拉回路，但图 不再是简单图，它具有平行边，设 边重复了 次，去掉偶数条后，仍保持各顶点的度数为偶数，即所得到的图仍是欧拉图。为使总数 达到最小，我们不妨假定每条边重复数目不超过1。仍使邮路达到最短，也就是要求重复边的长度达到最短。设 是所求的重复边的集合，使 达到最小，对于任一简单回路 ，可分解为与 相交的部分 ，及其余 。 2.2.2 引理 定理6 ([2]) 设 是使 达到最小的重复边集合，当且仅当对于 图的任一回路 ，恒有 。 证明：必要性.如若不然，假定存在 使 ， 这意味 部分的权超过其余 部分的权，令 即 。 也可作为重复边使 图成为欧拉图。这里 是对称差。显然， 可使图 的所有顶点保持其度数为偶数，由于假定 ， 故 。 跟 的假设相矛盾.必要性得到了证明。 注意这里 分解为与 共同部分，还有其余部分，后者出现在 中。 充分性证明。假定存在 由 的边作为重复的边，满足定理的条件：对于任一回路 有 ， 可以证明等式 。 令  ， 则图 没有度数为奇数的顶点， 可分解成若干简单回路 ，或记以 ， 则有 。 但  ，故 。 同理 。 即 ， 所以 。 充分得证。 2.2.3 算法 从上定理的证明过程提供了构造中国邮路问题的算法。设已知图 中顶点的度数为奇数的点为 。 第一步： 从1到 ，引从 到 得链 ，并对 的每条边附加一条使成为重复边。 第二步：检查图 的每条边.若添加的重复边数超过1，则除去其中偶数条，使得每条边之多有一条添加的边，且每一个顶点的度为偶数，从而得图 。图 中重复边的集合记为 。 第三步： ， (a)  若 对于回路 有 ， 则作【 ，转(a)】否则转 (b)。 (b)  输出 ， 便是最优集。 例题：给出中国邮路问题求解的过程。 解：图(a)到图(e)给出了中国邮路问题的求解过程。(a)便是 图，其中 点是度数为奇数的点，引重复边 便得(b)。(b)中不存在重复边数超过1的边。 考察回路  ， 由于 ， ， ， 不满足定理的要求，作 。 得图(c)，考察(c)中的回路 ， ， ， 显然不满足定理的要求，作 。 修改(c)得图(d) 考察回路 ， ， 。 不满足定理，修改得图(e)。 易知，图(e)满足定理6，故图(e)是欧拉回路。 3. 牛奶配送问题 目前我国绝大数牛奶生产企业以人工、凭主观、靠经验对配送线路进行优化，也有少部分企业开始借助于信息技术实现配送路线的优化工作，但能够提出完整的物流配送线路优化系统[9,10,11,12]的企业还非常少。而国外的一些路径优化软件由于交通规则、道路规划等各方面不符合我国国情，很难符合改革中的中国牛奶的管理流程[11]，因此牛奶配送路径优化问题已成为制约我国牛奶物流发展 的主要因素之一。 目前，国内外大多数研究很难一次形成合适的配送线路，往往需要辅助很多人工干预和调整，增加了工作的复杂性。本文将中国邮路问题引入配送路径的优化中，在邮路问题中引用指派问题来处理奇点对之间增加重复边[12]的问题，大大简化了多奇点对之间增加重复边的繁琐性，试图寻求一种新的适合我国牛奶配送系统的路径优化方法，并力求有所突破。 继续阅读