本科毕业论文-—欧拉图在生活中的应用.doc

《本科毕业论文-—欧拉图在生活中的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、LiaoningNormalUniversity（2013届）本科生毕业论文(设计)题目：欧拉图在生活中的应用学院：数学学院专业：数学与应用数学班级序号：11班22号学号：20111122060022学生姓名：陈旭指导教师：张楠2013年5月目录摘要1Abstract1前言21欧拉图问题提出的研究背景和定义31﹒1问题提出的研究背景31﹒2定义32欧拉图的判定定理和实例42﹒1欧拉图的判定定理42﹒2欧拉图实例53欧拉图的应用83﹒1中国邮递员问题及算法83﹒2牛奶配送问题13参考文献17致谢1

2、8i欧拉图在生活中的应用欧拉图在生活中的应用摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。欧拉图在现实生活中有着较广泛的应用。本文主要介绍了欧拉图问题提出的研究背景、相关概念和常用的判定定理、判别法及算法以及欧拉图在生活中的实际应用例子。关键词：欧拉图；判定定理；算法；应用。Abstract:EulergraphoriginatedinKonigsbergse

3、venBridgesproblem,allthroughthepictureedgeonceandonlyoncetraveledalltheverticesinthegraphofpathwayscalledEulerpath,allthroughthepictureedgeonceandoncetraveledallverticesofEulercircuit.WithEulercircuitdiagramcalledEulergraph.Eulergraphhasawideapplicat

4、ioninreallife.Eulergraphproblemismainlyintroducedinthispaperputsforwardtheresearchbackground,relatedconceptsandcommondecisiontheorem,Eulergraphmethodandalgorithmaswellaspracticalapplicationexampleinthelife.Keywords:Eulergraph;Judgmenttheorem;Algorith

5、m;Application.第18页欧拉图在生活中的应用前言图论是近210年来发展十分迅速、应用比较广泛的一个新兴的数学分支，19世纪末期，图论已经用来研究电网络方程组和有机化学中的分子结构；20世纪中叶以后，借助于计算机，图论又用来求解生产管理、军事、交通运输、计算机以及通信网络等领域中的许多离散性问题，同时图论中的一些著名问题也借助于计算机科学、电子学、信息论、控制论、网络理论、社会科学和管理科学等领域中，因此受到全世界越来越广泛的重视。图论的内容十分丰富，涉及面也比较广。本文章所涉及的只是

6、图论中的欧拉图的问题提出背景、一些基本定义、判定定理和生活中的应用。欧拉图是由哥尼斯堡七桥问题诞生的，讲述的是：18世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流，河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。这个问题困扰了人们许多年，成千上万的人试过了，但都没有成功。这个问题引起了欧拉的注意，为了寻找答案，欧拉对此问题进行观察、思考和研究，终于解决了这一难题，就是我们现在学习的欧拉图的判定方法。最后讲述了欧拉图在生活

7、中的应用问题，是本文的重要组成部分。运用欧拉图的相关定理来解决生活中的实际应用问题任重而道远，需要我们共同努力为国家贡献力量！第18页欧拉图在生活中的应用1欧拉图问题提出的研究背景和定义1﹒1问题提出的研究背景18世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流（普雷格尔河），河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。这个问题困扰了人们许多年，成千上万的人试过了，但都没有成功。这个问题引起了欧拉的注意，为了寻找答案，

8、欧拉对此问题进行观察、思考和研究，“也许并不存在这样的走法？”为了证明自己的猜想，他首先考虑到了集合中的“列举法”，但检验起来却十分麻烦，而且在同样的问题中，如果桥更多，那么“列举法”就无使用价值了，因此他放弃了这个方法，后来他改变了思考的角度，发现七桥问题仅仅涉及物体的位置关系，而与路程无关，于是他用点、表示岛屿，点、表示河的两岸，用连接两点的线表示桥，这样就可以画出如图1-1所示的无向图，这个问题就转化为“能否一笔画出该无向图且最后返回起点”。哥尼斯堡城七桥问题是否有解，就相当于这个无向图是