中国邮路问题及其算法大学论文.doc

24目录1引言12中国邮路问题12.1图的概念12.2道路与回路22.2.1基本概念22.2.2欧拉回路32.3中国邮路问题32.3.1无向图的中国邮路问题42.3.2有向图的中国邮路问题63中国邮路问题的算法83.1无向图的中国邮路问题的算法83.1.1奇偶点图上作业法83.1.2最小权匹配算法103.1.3破圈法123.2有向图的中国邮路问题的算法144中国邮路问题在实际生活中的应用与推广154.1无向图的中国邮路问题在实际生活中的应用154.2有向图的中国邮路问题在实际生活中的应用215结束语23参考文献24致谢25中国邮路问题及其算法Xxxxxx系本xxxxx班xxxxxx指导教师：xxxxxxx摘要：本文利用图论中的相关概念阐述并解决中国邮路问题，通过比较不同路径，归纳总结，找到其具体算法，再利用上述方法找到的具体算法，求解实例，加以验证，然后将其推广到实际生活中，帮助人们快速找到欧拉回路，即找到省时，省力，省钱的最佳路线，对于图论教学及理论研究均有一定的指导意义。关键词：中国邮路，欧拉回路，最佳路线。China'spostalproblemanditsalgorithmXxxxxxxxxClassxxxxx,TheDepartmentofmathematicsInstructor:xxxxxxAbstract:inthispaper,usingtherelevantconceptsinthispaper,thegraphtheoryandsolvetheproblemofChinapostroad,throughcomparingthedifferentpaths,sumup,finditsspecificalgorithm,usingtheabovetofindthespecificalgorithm,solvingtheinstance,verified,andthentopromoteittoreallife,tohelppeoplequicklyfindeularloop,namelyfindtosavetime,effort,savemoney,thebestwayofthegraphtheoryteachingandtheoreticalresearchhavecertainguidingsignificance.Keywords:Chinapostroad,eularcircuit,thebestroute.1引言中国邮路问题是我国著名图论学者管梅谷教授首先提出并解决的。它起初为了帮助邮递员选择一条合适道路，使其在完成任务的同时所走路程最短，后来其方法在实际生产生活中有广泛的应用，如邮政部门，扫雪车线路，洒水车路线，警车巡逻路线等，具有很强的实用价值，本文紧抓其实质与核心，通过对传统中国邮路问题研究方法的归纳总结，帮助人们快速找出欧拉回路，实现了将数学知识应用于实际生活中，服务于人类。2中国邮路问题2.1图的概念定义1二元组称为图，其中是非空集合，称为结点集，是诸结点之间边的集合，常用表示图。(1)图可分为有限图与无限图两类，现只讨论,都是有限集，给定某个图，如果不加特别说明，认为，，即结点数，边数。(2)图的边可以是有方向的，也可以是无方向的，它们分别称为有向边和无向边，用表示。定义2的某结点所关联的边数称为该结点的度，用表示。定义3任意两结点间最多只有一条边，且不存在自环的无向图称为简单图。性质1设有个结点，条边，则。性质2中度为奇数的结点必为偶数个。定义4若图的每条边都赋以一个实数作为该边的权，则称是赋权图，特别地，如果这些权都是正实数，就称是正权图，权可以表示该边的长度，时间，费用或容量等，如下图2.1所示：图2.12.2道路与回路2.2.1基本概念定义1有向图中，若边序列，其中，满足是的终点,是的始点，就称是的一条有向道路，如果的终点是的始点，则称是的一条有向回路。如果中的边没有重复出现，则分别称为简单有向道路和简单有向回路，进而，如果中结点也不重复出现，又分别称它们为初级有向道路或初级有向回路，简称为路或回路。显然，初级有向道路（回路）一定是简单有向道路（回路）。如下图2.2.1(a)所示：图2.2.1(a)边序列是有向道路；边序列是有向回路；边序列是简单有向道路；边序列是简单有向回路；边序列是初级有向道路；边序列是初级有向回路。定义2无向图中，若点边交替序列满足,是的两个端点，则称是中的一条链或道路；如果,则称是中的一个圈或回路。如下图2.2.1(b)所示：图2.2.1(b)边序列是道路；边序列是回路；边序列是简单道路；边序列是简单回路；边序列是初级道路；边序列是初级回路。定义3设是无向图，若的任意两结点之间都存在道路，则称是连通图，否则称为非连通图。2.2.2欧拉回路定义1对于连通的无