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

Liaoning Normal University
（2013届）
本科生毕业论文(设计)
题 目： 欧拉图在生活中的应用
学 院： 数学学院
专 业： 数学与应用数学
班级序号： 11班22号
学 号： 022
学生： 旭
指导教师： 楠
2013年5月
目 录
摘要 1
Abstract 1
前言 2
1欧拉图问题提出的研究背景和定义 3
1﹒1问题提出的研究背景 3
1﹒2定义 3
2欧拉图的判定定理和实例 4
2﹒1欧拉图的判定定理 4
2﹒2欧拉图实例 5
3欧拉图的应用 8
3﹒1中国邮递员问题及算法 8
3﹒2牛奶配送问题 13
参考文献 17
致 18
欧拉图在生活中的应用
摘要：欧拉图起源于哥尼斯堡七桥问题，通过图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。欧拉图在现实生活中有着较广泛的应用。本文主要介绍了欧拉图问题提出的研究背景、相关概念和常用的判定定理、判别法及算法以及欧拉图在生活中的实际应用例子。
关键词：欧拉图；判定定理；算法；应用。
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 Euler 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 and 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.
前言
图论是近210年来发展十分迅速、应用比较广泛的一个新兴的数学分支，19世纪末期，图论已经用来研究电网络方程组和有机化学中的分子结构；20世纪中叶以后，借助于计算机，图论又用来求解生产管理、军事、交通运输、计算机以及通信网络等领域中的许多离散性问题，同时图论中的一些著名问题也借助于计算机科学、电子学、信息论、控制论、网络理论、社会科学和管理科学等领域中，因此受到全世界越来越广泛的重视。图论的容十分丰富，涉及面也比较广。本文章所涉及的只是图论中的欧拉图的问题提出背景、一些基本定义、判定定理和生活中的应用。
欧拉图是由哥尼斯堡七桥问题诞生的，讲述的是：18世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流，河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。这个问题困扰了人们许多年，成千上万的人试过了，但都没有成功。这个问题引起了欧拉的注意，为了寻找答案，欧拉对此问题进行观察、思考和研究，终于解决了这一难题，就是我们现在学****的欧拉图的判定方法。最后讲述了欧拉图在生活中的应用问题，是本文的重要组成部分。
运用欧拉图的相关定理来解决生活中的实际应用问题任重而道远，需要我们共同努力为国家贡献力量！
1欧拉图问题提出的研究背景和定义
1﹒1问题提出的研究背景
18世纪，普鲁士的哥尼斯堡城有一条贯穿全城的河流（普雷格尔河），河中有两个岛，有七座桥将两岸与岛屿及岛屿之间连接，当时当敌人们热衷于一个难题：一个散布者怎样不重复地走完七桥，最后回到出发点。这个