中国邮路问题及其算法

i目录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致谢..............................................................................................................................................25ii中国邮路问题及其算法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.11引言中国邮路问题是我国著名图论学者管梅谷教授首先提出并解决的。它起初为了帮助邮递员选择一条合适道路，使其在完成任务的同时所走路程最短，后来其方法在实际生产生活中有广泛的应用，如邮政部门，扫雪车线路，洒水车路线，警车巡逻路线等，具有很强的实用价值，本文紧抓其实质与核心，通过对传统中国邮路问题研究方法的归纳总结，帮助人们快速找出欧拉回路，实现了将数学知识应用于实际生活中，服务于人类。2中国邮路问题2.1图的概念定义1二元组GEGV,称为图，其中GV是非空集合，称为结点集，GE是GV诸结点之间边的集合，常用EVG,表示图。(1)图可分为有限图与无限图两类，现只讨论V,E都是有限集，给定某个图EVG,，如果不加特别说明，认为nvvvvV321,,，meeeeE321,,，即结点数nV，边数mE。(2)图G的边可以是有方向的，也可以是无方向的，它们分别称为有向边和无向边，用jikvve,表示。定义2EVG,的某结点v所关联的边数称为该结点的度，用vd表示。定义3任意两结点间最多只有一条边，且不存在自环的无向图称为简单图。性质1设EVG,有n个结点，m条边，则mvdGVv2。性质2G中度为奇数的结点必为偶数个。定义4若图EVG,的每条边jikvve,都赋以一个实数kw作为该边的权，则称G是赋权图，特别地，如果这些权都是正实数，就称G是正权图，权可以表示该边的长度，时间，费用或容量等，如下图2.1所示：234734.2562v2v1v5v4v3图2.12.2道路与回路2.2.1基本概念定义1有向图EVG,中，若边序列iqiiieeeeP321,,，其中jiikvve,，满足iv是1ike的终点,jv是1ike的始点，就称P是G的一条有向道路，如果iqe的终点是1ie的始点，则称P是G的一条有向回路。如果P中的边没有重复出现，则分别称为简单有向道路和简单有向回路，进而，如果P中结点也不重复出现，又分别称它们为初级有向道路或初级有向回路，简称为路或回路。显然，初级有向道路（回路）一定是简单有向道路（回路）。如下图2.2.1(a)所示：e7e6e5e4e3e1e2v1v3v2v4图2.2.1(a)边序列7545,,,eeee是有向道路；边序列37545,,,,eeeee是有向回路；边序列2145,,,eeee是简单有向道路；边序列32145,,,,eeeee是简单有向回路；3边序列21,ee是初级有向道路；边序列321,,eee是初级有向回路。定义2无向图EVG,中，若点边交替序列iqiqiiiiveevevP,,,,12211满足ikv,1ikv是ike的两个端点，则称P是G中的一条链或道路；如果1iiqvv,则称P是G中的一个圈或回路。如下图2.2.1(b)所示：e5e4e3e1e2e6v1v3v2v4图2.2.1(b)边序列6454,,,eeee是道路；边序列36454,,,,eeeee是回路；边序列2154,,,eeee是简单道路；边序列32154,,,,eeeee是简单回路；边序列21,ee是初级道路；边序列321,,eee是初级回路。定义3设G是无向图，若G的任意两结点之间都存在道路，则称G是连通图，否则称为非连通图。2.2.2欧拉回路定义1对于连通的无向图G，若存在一简单回路，它通过G的所有边，则这回路称为G的Euler回路。定理1无向连通图G存在欧拉回路的充要条件是G中各结点的度都是偶数。推论1若无向连通图G中只有2个度为奇数的结点，则G存在欧拉道路。推论2若有向连通图G中各结点的正、负度相等，则G存在有向欧拉回路。2.3中国邮路问题中国邮路问题，它是由中国数学家管梅谷教授首先提出而得名。设邮递员从4邮局出发，遍历他所管辖的每一条街道，将信件送到后返回邮局，要求所走的路径最短，当然如若他所管辖的街