《欧拉图在生活中的应用 2013年5月》由会员分享，可在线阅读，更多相关《欧拉图在生活中的应用 2013年5月（20页珍藏版）》请在金锄头文库上搜索。
1、LiaoningLiaoning NormalNormal UniversityUniversity （2013 届届）本本科科生生毕毕业业论论文文( (设设计计 ) )题题 目：目： 欧拉图在生活中的应用欧拉图在生活中的应用学学 院：院： 数学学院数学学院专专 业：业： 数学与应用数学数学与应用数学班级序号：班级序号： 11 班班 22 号号学学 号：号： 20111122060022学生姓名：学生姓名： 陈旭陈旭指导教师：指导教师： 张楠张楠2013 年年 5 5 月月i目目 录录摘要摘要 .1AbstractAbstract .1前言前言 .21 1 欧拉图问题提出的研究背景和定义欧拉图
2、问题提出的研究背景和定义.31 11 1 问题提出的研究背景问题提出的研究背景.31 12 2 定义定义.32 2 欧拉图的判定定理和实例欧拉图的判定定理和实例.42 21 1 欧拉图的判定定理欧拉图的判定定理.42 22 2 欧拉图实例欧拉图实例.53 3 欧拉图的应用欧拉图的应用.83 31 1 中国邮递员问题及算法中国邮递员问题及算法.83 32 2 牛奶配送问题牛奶配送问题.13参考文献参考文献 .17致谢致谢 .18第 1 页欧拉图在生活中的应用摘要：摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且一次行遍所有顶
3、点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。欧拉图在现实生活中有着较广泛的应用。本文主要介绍了欧拉图问题提出的研究背景、相关概念和常用的判定定理、判别法及算法以及欧拉图在生活中的实际应用例子。关键词：关键词：欧拉图；判定定理；算法；应用。Abstract: Euler graph originated in Konigsberg seven Bridges problem, all through the picture edge once and only once traveled all the vertices in the graph of pathways called Eu
4、ler path, all through the picture edge once and once traveled all vertices of Euler circuit. With Euler circuit diagram called Euler graph. Euler graph has a wide application in real life. Euler graph problem is mainly introduced in this paper puts forward the research background, related concepts a
5、nd common decision theorem, Euler graph method and algorithm as well as practical application example in the life.Key words: Euler graph; Judgment theorem; Algorithm; Application.欧拉图在生活中的应用第 2 页前言前言 图论是近 210 年来发展十分迅速、应用比较广泛的一个新兴的数学分支，19 世纪 末期，图论已经用来研究电网络方程组和有机化学中的分子结构；20 世纪中叶以后， 借助于计算机，图论又用来求解生产管理、军
6、事、交通运输、计算机以及通信网络等 领域中的许多离散性问题，同时图论中的一些著名问题也借助于计算机科学、电子学、 信息论、控制论、网络理论、社会科学和管理科学等领域中，因此受到全世界越来越 广泛的重视。图论的内容十分丰富，涉及面也比较广。本文章所涉及的只是图论中的 欧拉图的问题提出背景、一些基本定义、判定定理和生活中的应用。 欧拉图是由哥尼斯堡七桥问题诞生的，讲述的是：18 世纪，普鲁士的哥尼斯堡城 有一条贯穿全城的河流，河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当 时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。 这个问题困扰了人们许多年，成千上万的人试过了
7、，但都没有成功。这个问题引起了 欧拉的注意，为了寻找答案，欧拉对此问题进行观察、思考和研究，终于解决了这一 难题，就是我们现在学习的欧拉图的判定方法。最后讲述了欧拉图在生活中的应用问 题，是本文的重要组成部分。 运用欧拉图的相关定理来解决生活中的实际应用问题任重而道远，需要我们共同 努力为国家贡献力量！欧拉图在生活中的应用第 3 页1 1 欧拉图问题提出的研究背景和定义欧拉图问题提出的研究背景和定义 1111 问题提出的研究背景问题提出的研究背景 18 世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流（普雷格尔河） ，河中有两个 岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：
8、一个散 布者怎样不重复地走完七桥，最后回到出发点。这个问题困扰了人们许多年，成千上 万的人试过了，但都没有成功。 这个问题引起了欧拉的注意，为了寻找答案，欧拉对此问题进行观察、思考和研 究， “也许并不存在这样的走法？”为了证明自己的猜想，他首先考虑到了集合中的 “列举法” ，但检验起来却十分麻烦，而且在同样的问题中，如果桥更多，那么“列举 法”就无使用价值了，因此他放弃了这个方法，后来他改变了思考的角度，发现七桥 问题仅仅涉及物体的位置关系，而与路程无关，于是他用点、表示岛屿，点、ABC 表示河的两岸，用连接两点的线表示桥，这样就可以画出如图 1-1 所示的无向图，D 这个问题就转化为“能否
9、一笔画出该无向图且最后返回起点” 。哥尼斯堡城七桥问题是 否有解，就相当于这个无向图是否存在经过图中每条边一次且仅一次的简单回路。 我们知道，从某一个点出发最后又回到这个点，经过这一点的边的条数一定是偶数； 经过中间的每一点，有进去的一条边，又有出来的一条边，因此，经过这些点的边的 条数也是偶数。根据这个道理，我们可以看到图中经过每一点巧妙地解决了这个困扰 人们多年但又十分有趣的问题。那这个方法也就成了我们现在学习的欧拉图的判定方 法。图 1-1 1212 定义定义定义定义1 1 图图：图论中将图定义为一个偶对，其中表示顶中点的集合，是无EVG,VE 序组集合的一个子集合，集合中的元素在出现不
10、止一次边的集合。分别VV VV E用和表示图的顶点集合与边的集合。如果和都是有限集合，则 GV GEG GV GE称为有限图，否则称为无限图。若，则称为阶图。G nGVGn定义定义 2 2 平凡图平凡图：只有一个顶点的图叫做平凡图。 定义定义 3 3 关联关联：一条边的端点称为与这条边关联。 定义定义 4 4 连通连通：设是图中的两个顶点，若中存在一条道路，则称顶点和vu,GGvu,u 是连通的。v 定义定义 5 5 度度：设中与顶点 关联的边的数目，称为 （在中）的度，记作。GvvG vd欧拉图在生活中的应用第 4 页定义定义 6 6 回路回路：设为图，中顶点与边的交替序列称为到GG 211
11、0jjjievev llijve 0iv的通路，若，则称通路为回路。 （若的所有边各异，则称为简单回路。 ） liv loiivvG定义定义 7 7 通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图 中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为 欧拉图欧拉图。 定义定义 8 8 给定有向图，经过中每边一次且仅一次的有向迹称为有向欧拉图有向欧拉图；经过DD 中每边一次且仅一次的有向闭迹(回路)称为有向欧拉回路。有向欧拉回路。D 定义定义 9 9 含欧拉回路的无向连通图与含有向欧拉回路的弱连通有向图，统称为欧拉圈欧拉圈。 定义定义 1010 欧拉闭
12、迹：欧拉闭迹：经过图的每条边恰好一次的闭迹。G 定义定义 1111 欧拉迹：欧拉迹：经过每条恰好一次的迹。2 2 欧拉图的判定定理和实例欧拉图的判定定理和实例 2121 欧拉图的判定定理欧拉图的判定定理 下面介绍欧拉图的一些判定定理： 引理：引理：设一般图，如果它的每个顶点的度数都是偶数，则的每条边都属于EVG,G 一条闭迹，因而也属于一个圈。 证明：利用下面的算法，可以找到一条包含任意指定边的闭迹。在该算法101,xx中，我们要构造一个顶点集和一个边集。WF 求闭迹的算法求闭迹的算法 i)令1i ii)令10,xxW iii)令 1Fiv)当时，执行0xxia) 找出一个不在中的边。F11,
13、iiixxb) 将放人中（也许已在中） 。1ixW1ixWc) 将放入中。1iFd) 令。1 ii这样，经过 i)iii)步初始化以后，在算法中的，我们都要找到一条新边 ，它邻接于最后一次放入中的顶点，再将和分别放入和11,iiixxWix1ix1iW中，并使 的值增 1.重复这个过程，直到最终又到达为止。Fi0x假设只要时，满足 iv)a)的一条边总存在。设 的终值它为，所产生的0xxi1iik顶点集，边的多重集，于是，根据算法得到的kxxxW,10LkF,1L 就是包含初始边的一条闭迹。因此，我们只需证明：如果，那么就k,1L10xxi有一个不在中的边与邻接。正是在这里，用到了偶度次顶点的假设。Fix容易看到：算法中每步 iv)的 d)结束时，一般图的每个顶点都具有偶FWH,度次，只有顶点（它起始于奇度 1）和最新加入的顶点（它的度数刚刚增加 1）可0xix能除外。此外，和具有偶度次，当且仅当，因此，如果，则在一0xixixx 00xxiix般图中就具有奇度次。既然在一般图中具有偶度次，则必存在一个还不属于HixG欧拉图在
