中国邮路问题及其算法
Xxxxxx 系本 xxxxx 班 xxxxxx
指导教师： xxxxxxx
摘 要：本文利用图论中的相关概念阐述并解决中国邮路问题，通过比较不同路
径，归纳总结，到其具体算法，再利用上述方法到的具体算法，求解实例，加以
验证，然后将其推广到实际生活中，帮助人们快速到欧拉回路，即到省时，省 力，省钱的最佳路线，对于图论教学及理论研究均有一定的指导意义。
关键词： | 中国邮路，欧拉回路，最佳路线。 China's postal problem and its algorithm Xxxxxxxxx Class xxxxx,The Department of mathematics Instructor: xxxxxx |
| |
Abstract: in this paper, using the relevant concepts in this paper, the graph theory and solve the problem of China post road, through comparing the different paths, sum up, find its specific algorithm, using the above to find the specific algorithm, solving the instance, verified, and then to promote it to real life, to help people quickly find eular loop, namely find to save time, effort, save money, the best way of the graph theory teaching and theoretical research have certain guiding significance.
Key words: China post road, eular circuit, the best route.
收缩薄膜
1引言
中国邮路问题是我国着名图论学者管梅谷教授首先提出并解决的。它起初 为了帮助邮递员选择一条合适道路，使其在完成任务的同时所走路程最短，后 来其方法在实际生产生活中有广泛的应用，如邮政部门，扫雪车线路，洒水车 路线，警车巡逻路线等，具有很强的实用价值，本文紧抓其实质与核心，通过 对传统中国邮路问题研究方法的归纳总结，帮助人们快速出欧拉回路，实现 了将数学知识应用于实际生活中，服务于人类。
2中国邮路问题
图的概念
定义1二元组V G ,E G称为图，其中V G是非空集合，称为结点集， EG是V G诸结点之间边的集合，常用G V,E表示图。
(1)图可分为有限图与无限图两类，现只讨论 V, E都是有限集，给定某 个图G V,E，如果不加特别说明，认为V Vi，V2,V3 Vn，
E ei,e2,ebbzss em ，即结点数V n，边数E m。
(2)图G的边可以是有方向的，也可以是无方向的，它们分别称为有向边 和无向边，用ek Vi,Vj表示。
定义2 G V,E的某结点v所关联的边数称为该结点的度，用d v表 示。
定义3任意两结点间最多只有一条边，且不存在自环的无向图称为简单 图。
性质1设G V,E有n个结点，m条边，则 d v 2m。
v V G
性质2 G中度为奇数的结点必为偶数个。
定义4若图G V,E的每条边ek vi,vj都赋以一个实数Wk作为该边的 权，则称G是赋权图，特别地，如果这些权都是正实数，就称 G是正权图，权 可以表示该边的长度，时间，费用或容量等，如下图所示：
道路与回路
基本概念
定义 1 有向图 G V,E 中，若边序列 P ei1,ei2,ei3 eiq ，其中
ek Vj,Vj ,满足vi是eik i的终点,Vj是eik i的始点，就称P是G的一条有向道
路，如果 eiq 的终点是 ei1 的始点，则称 P 是 G 的一条有向回路。
如果P中的边没有重复出现，则分别称为简单有向道路和简单有向回路， 进而，如果P中
结点也不重复出现，又分别称它们为初级有向道路或初级有向 回路，简称为路或回路。显然，初级有向道路（回路）一定是简单有向道路 （回 路）。如下图所示：
图边序列 e5,e4,e5,e7 是有向道路；边序列 e5,e4,e5,e7,e3 是有向回路；
边序列 e5, e4, e1 ,e2 是简单有向道路；边序列 e5,e4,e1,e2,e3 是简单有向回路；
边序列 e1,e2 是初级有向道路；边序列 e1 ,e2, e3 是初级有向回路。
定义 2 无向图 G V,E 中，若点边交替序列 无人机北京天宇创通P Vi1,ei1,Vi2,ei2 eiq 1,Viq 满
足Vik , Vik i是eik的两个端点，则称P是脱模剂原料G中的一条链或道路；如果Viq Vii ,则 称P是G
图边序列 e4水塔水位控制系统,e5,e4,e6 是道路；边序列 e4,e5,e4,e6,e3 是回路；
边序列 e4,e5山体滑坡监测,e1,e2 是简单道路；边序列 e4,e5,e1,e2,e3 是简单回路；
边序列 e1,e2 是初级道路；边序列 e1,e2,e3 是初级回路。
定义3设G是无向图，若G的任意两结点之间都存在道路，则称 G是连 通图，否则称为非连
通图。
欧拉回路
定义 1 对于连通的无向图 G ，若存在一简单回路，它通过 G 的所有边， 则这回路称为G的Euler回路。
定理1无向连通图G存在欧拉回路的充要条件是G中各结点的度都是偶 数。
推论 1 若无向连通图 G 中只有 2个度为奇数的结点，则 G 存在欧拉道路。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议