文档介绍：LiaoningNormalUniversity(2013届)本科生毕业论文(设计)题目:欧拉图在生活中应用学院:数学学院专业:数学与应用数学班级序号:11班22号学号:201**********学生姓名:陈旭指导教师:张楠2013年5月目录摘要 1Abstract 1前言 21欧拉图问题提出的研究背景和定义 31﹒1问题提出的研究背景 31﹒2定义 32欧拉图的判定定理和实例 42﹒1欧拉图的判定定理 42﹒2欧拉图实例 53欧拉图的应用 83﹒1中国邮递员问题及算法 83﹒2牛奶配送问题 13参考文献 17致谢 18欧拉图在生活中应用摘要:欧拉图起源于哥尼斯堡七桥问题,通过图中所有边一次且仅一次行遍图中所有顶点通路称为欧拉通路,通过图中所有边一次并且一次行遍所有顶点回路称为欧拉回路。具有欧拉回路图称为欧拉图。欧拉图在现实生活中有着较广泛应用。本文主要介绍了欧拉图问题提出研究背景、相关概念与常用判定定理、判别法及算法以及欧拉图在生活中实际应用例子。关键词:欧拉图;判定定理;算法;应用。Abstract:EulergraphoriginatedinKonigsbergsevenBridgesproblem,allthroughthepictureedgeonceandonlyoncetraveledalltheverticesinthegraphofpathwayscalledEulerpath,,mondecisiontheorem,:Eulergraph;Judgmenttheorem;Algorithm;、应用比较广泛一个新兴数学分支,19世纪末期,图论已经用来研究电网络方程组与有机化学中分子结构;20世纪中叶以后,借助于计算机,图论又用来求解生产管理、军事、交通运输、计算机以及通信网络等领域中许多离散性问题,同时图论中一些著名问题也借助于计算机科学、电子学、信息论、控制论、网络理论、社会科学与管理科学等领域中,因此受到全世界越来越广泛重视。图论内容十分丰富,涉及面也比较广。本文章所涉及只是图论中欧拉图问题提出背景、一些基本定义、判定定理与生活中应用。欧拉图是由哥尼斯堡七桥问题诞生,讲述是:18世纪,普鲁士哥尼斯堡城有一条贯穿全城河流,河中有两个岛,有七座桥将两岸与岛屿及岛屿之间连接,当时当敌人们热衷于一个难题:一个散布者怎样不重复地走完七桥,最后回到出发点。这个问题困扰了人们许多年,成千上万人试过了,但都没有成功。这个问题引起了欧拉注意,为了寻找答案,欧拉对此问题进行观察、思考与研究,终于解决了这一难题,就是我们现在学习欧拉图判定方法。最后讲述了欧拉图在生活中应用问题,是本文重要组成部分。运用欧拉图相关定理来解决生活中实际应用问题任重而道远,需要我们共同努力为国家贡献力量!1欧拉图问题提出研究背景与定义1﹒1问题提出研究背景18世纪,普鲁士哥尼斯堡城有一条贯穿全城河流(普雷格尔河),河中有两个岛,有七座桥将两岸与岛屿及岛屿之间连接,当时当敌人们热衷于一个难题:一个散布者怎样不重复地走完七桥,最后回到出发点。这个问题困扰了人们许多年,成千上万人试过了,但都没有成功。这个问题引起了欧拉注意,为了寻找答案,欧拉对此问题进行观察、思考与研究,“也许并不存在这样走法?”为了证明自己猜想,他首先考虑到了集合中“列举法”,但检验起来却十分麻烦,而且在同样问题中,如果桥更多,那么“列举法”就无使用价值了,因此他放弃了这个方法,后来他改变了思考角度,发现七桥问题仅仅涉及物体位置关系,而与路程无关,于是他用点、表示岛屿,点、表示河两岸,用连接两点线表示桥,这样就可以画出如图1-1所示无向图,这个问题就转化为“能否一笔画出该无向图且最后返回起点”。哥尼斯堡城七桥问题是否有解,就相当于这个无向图是否存在经过图中每条边一次且仅一次简单回路。我们知道,从某一个点出发最后又回到这个点,经过这一点边条数一定是偶数;经过中间每一点,有进去一条边,又有出来一条边,因此,经过这些点边条数也是偶