2024年3月7日发(作者：楼典)
目 录
中国邮路问题及其算法
Xxxxxx 系本 xxxxx 班 xxxxxx
指导教师： xxxxxxx
摘 要：本文利用图论中的相关概念阐述并解决中国邮路问题，通过比较不同路
目 录
径，归纳总结，找到其具体算法，再利用上述方法找到的具体算法，求解实例，加以
验证，然后将其推广到实际生活中，帮助人们快速找到欧拉回路，即找到省时，省
力，省钱的最佳路线，对于图论教学及理论研究均有一定的指导意义。
关键词： 中国邮路，欧拉回路，最佳路线。
China's postal problem and its algorithm
Xxxxxxxxx
Class xxxxx,The Department of mathematics
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,es
em
，即结点数V n，边数E m。
(2) 图G的边可以是有方向的，也可以是无方向的，它们分别称为有向边 和无向边，用ek
Vi,Vj表示。
定义2
G V,E的某结点所关联的边数称为该结点的度，用d v表 示。
v定义3任意两结点间最多只有一条边，且不存在自环的无向图称为简单 图。
性质1设G V,E有n个结点，m条边，则
性质2
G中度为奇数的结点必为偶数个。
定义4若图G V,E的每条边ek
vi,vj都赋以一个实数Wk作为该边的 权，则称G是赋权图，特别地，如果这些权都是正实数，就称
G是正权图，权 可以表示该边的长度，时间，费用或容量等，如下图所示：d v 2m。
v V 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
存在欧拉道路。
推论2若有向连通图G中各结点的正、负度相等，贝U G存在有向欧拉回 路。
中国邮路问题
中国邮路问题，它是由中国数学家管梅谷教授首先提出而得名。设邮递员 从邮局出发，遍
历他所管辖的每一条街道，将信件送到后返回邮局，要求所走 的路径最短，当然如若他所管辖的街道构成一欧拉回路，贝这欧拉回路便是所 求的路径，如若不然，即存在度数为奇数的顶点时，必然有些街道需要走多于 1 遍，如何寻求最短的路？ (基本思路：根据欧拉圈原理，用奇偶点图上作业法， 使邮递路线为最短)
现将中国邮路问题用图论的语言描述如下：
设G V,E是连通图，而且对于所有的e E
,都赋以权ce 0，求以点
v V出发，通过所有边至少一次，最后返回 v点的回路C,使得 ce达到最
eC
小。
无向图的中国邮路问题
邮递员从邮局出发，走完投递线路后又回到邮局，这就要求邮递员的行走 路径必须是欧拉圈，但是由于城市街道及邮递点组成的图有三种基本类型，相 应的就有三种类型线路，不管何种类型，归根到底，都要设法使之形成欧拉 圈。
(1) 图G里没有奇次定点。即G中各结点的度都是偶数，那么G
一定有欧 拉回路，显然任何一条欧拉回路都是该问题的解。如下图所示：
图
投递路线为： A B C I J K H G E
H G E D H K J I
D
C
H
B
I
A
A
或者可为：
A I
这时没有重复行走的街道，当然邮路最短。
(2) 图G中只有2个结点Vi, Vj的度是奇数，则一定存在从Vi到Vj的一条欧 拉道路，它经过了
G的各边一次。在G中再找一条从vj到vi的最短道路Pji，则 G G Pji中存在欧拉回路。这样G中的欧拉回路，即对应于G中pjj的边重 复一次而其余边只过一次的回路是一条中国邮路，即最佳邮路。如下图所示：
图(
b)
如图，B , E是奇次顶点，因此要构成一个欧拉回路，
一次，这样存在许多重复走的方案，例如
B F E ; B F C E ; B C D E ; B C E 等。
B E线路必须重复走
我们计算一下重复走的长度分别为 4， 6， 5， 5；当然需要重复走的线路以
B F E 为最好，故巧加边，是使其形成欧拉回路的方法，故此时线路为
A B F E D C E F C B F A. 总长度为 21，且此路 线是最短的。
(3) 图
G
中度为奇数的结点数多于 2 个，则需要添加很多条边，才能形成欧 拉回路，且有几对奇次顶点，就要加几条边，此时巧加边问题更加重要。如下 图：
如图，有 8个奇次顶点，它们是 B ,C,E ,H ,G
,J ,I , L .如何巧妙地把这 8个奇次 顶点恰当地组合成 4对呢？我们参照上一题的例子，便可将 8 个奇次顶点配成以 下 4对： LI ,BC,JG,HE .这是必须重复走的最短线路，且长度为 11，最优投递 路线总长为 60，其中一条最佳路线为
A B C D E F G H E H C B I J G J K
LILA
有向图的中国邮路问题
(1) 图
G
中含有正度或负度为 0 的结点，此时不存在最佳邮路。如图所
示：
图
图
G
中各结点的正，负度相等，此时
G
中一定存在有向欧拉回路。它过
每边一次且仅一次，因此任意一条欧拉回路都是中国邮路。如下图所示：
图 图
G
不对称，即存在一些结点 v ， d v d v ，其中 d v 的值是以
iiiv为始点的边的数目，d v的值是以v为终点的边的数目。
不妨设d Vi
d Vi，由于邮递员要经过进入Vi的每条边，因此他一定
要重复走以Vi为始点的某条边。设fij表示边Vi
,Vj的重复次数，Wij表示该边的 权，那么中国邮路要选择重复一些边后存在有向欧拉回路，并且使
最小的一个解，显然此时满足 d Vi
即
j
wij
fij
为
i, j E G
fji
d Vi
fij
，
Vi
V G
fij
f
ji
d vi
d vi
d i .
(i) 若
d i 0
，表示邮路中 vi
要
d i
次重复经过 vi
所发出的一些边，或者说 vi
可供应
d i
个j j
单位量。
(ii) 若d i 0,表示邮路中Vi要d i次重复经过进入M的一些边，或者说w 可接收
d i
个单位量。
(iii)
若d i 0,则称Vi是中间结点。由于
d Vid v，所以
d i 0，这样可以逐次保证每个可供应点 vi
经过一些边向某个接收点 vj
供 应一个单位量，最后达到平衡，或者说这些道路上的边出现重复，最后得到的 图
G
是有向欧拉图，若这些重复边的总长最小，它即是最佳邮路。
例1求下图的中国邮路。
解 此题显然是有向中国邮路问题中的不对称型，故
(1) 各结点的
d i
为
d
1 d 5
0
，
d 2 2，
d 3 1，
d 4
1
(2) 构造
G
图
图 得到 2 条总和最小的
Pst 道路
P1
Vs,V2,V4,Vt
,
Vs,V2,V4,V3,Vt
P1
5
?
6;故 Pi
11. 这样边
V2,V4
重复 2 次，边
2
P，
P2
V4,V3
重复 1 次，得图，其中虚线边表示重复 1 次
(4) 图是欧拉图，其中一条欧拉回路，如
V1,V2,V4,V3,V2,V4,V3,V5,V2,V4,V5,V1
就是最佳邮路。
3 中国邮路问题的算法
无向图的中国邮路问题的算法 奇偶点图上作业法
(1) 把G中所有奇度数顶点配成对，将每对奇度数顶点之间的一条路上的每 边改为二重边，得到一个新图 G,新图G中没有奇度数顶点，即G为多重Euler 图。
(2) 若G中某一对顶点之间有多于2条边连接，则去掉其中的偶数条边，留 下 1 条或 2条边连接这两个顶点，直到每一对相邻顶点至多由 2条边连接，得到 图 G2
。
(3) 检查G2的每一个圈C,若某一个圈C上重复边的权和超过此圈权和的一 半，则将C进行调整。重复这一过程，直到对 G2的所有圈，其重复边的权和不 超过此圈权和的一半，得到图
G3
。
(4) 求Ga的Euler回路。
例2求下图所示图G的中国邮路。
图G
解 图G中有6个奇度数顶点v2, v4, v5, v7, v9, v10.把它们配成三对：v2与
V5, V4与V7
, V9与Vio，在图G中，取一条V2与V5的路V2V3V4V5，把边
V2,Va
, Va,V4
, V4, V5作为重复边加入图中；再取V4与V7之间一条路V4V5V6V7， 把边V4,V5
,
V5,V6
, V6,V7作为重复边加入图中，在V9和血之间加一条重复边
V9,Vio，如图⑵，这个圈没有奇度数点，是一个 Euler图。
(2) (3)
在图(2)中，顶点V4与V5之间有三条重边，去掉其中两条，得到图(3)，该 图仍是一个Euler图。
在图⑶中，圈V2V3V4V11V2的总权为24，而圈上重复边的权和为14，大于该 圈总权的一半，于是去掉边 V2,V3
和 V3,V4
上的重复边，而在
V2,V11
和
V4,V11
上加入重复边，此时重复边的权和为 10，小于该圈总权的一半。同理，圈
V5V6V7V12V5的总权和为15,去掉边V5,V6和V6,V7上的重复边，在边V5,Vi2和
V7,W2上加重复边，如下图 ⑷：
⑷ (5)
图(4)中，圈V4V5V12V11V4的总权为15,而重复边的权和为8,从而调整为图
⑸。
图⑸ 中，圈V1V2V11V12V7V8V9V10V1的总权为36,而重复边的总权为20,继续调整 为图⑹：
(6)
经检验，图(6)为最优方案，其中一条欧拉回路就是最佳邮路。
最小权匹配算法
(1) 确定G中度为奇数的结点，构成Vo
G
。
(2) 求V。G各结点在G中的最短路径R及其长度 Vi,Vj。
(3) 对Vo G的结点进行最小权匹配，即选出 Vo G /2个 Vi,Vj ,保证每个
结点Vi
Vo
G在Rj中只出现一次，同时满足这些
(4) 在最小权匹配里各
得到G。
(5)
G是欧拉图，它的一条欧拉回路即为最优解。
例3求下图所示图G的中国邮路。
解显然此题属于无向图的中国邮路问题，故
(1) 首先找到奇数结点，Vo
G
V2,V3, V4,V5,V6,V7。
Vi,Vj的总和最小。
R中的诸边在G中重复一次，
V ,Vj所对应的路径(2) 求V。G各结点在G中的最短路径R及长度 Vi,Vj，
V2,V7
, V3
，
23
V2,V7,V5
，
V2,V7
，
27
25
R23
4 ；
7 ；
R24
R26
R34
V2.V7.V4，
V2,V1,V6
，
V3,V4
，
34
24
4
R25
R27
26
；4
；
2 ；
3
；
R35
V3,V4,V5，
35
6 ；
P36
V3,V7,V6，
36
6
；
R37
V3,V7
，
37
2；
46
R45
V4,V5
，
V4,V7
45
57473
2
5
R46
V4,V5,V6
V5,V6
，
V6,V7
，
56
6 ；
R47
R57
R56
3；
，
V5,V7
，
R67
67
4.
；
(3)
对V°G的结点进行最小权匹配，得最佳匹配
V2,7
,
V3N4
,
V5N6
。
(4) 在最小权匹配里各 Vj,Vj所对应的路径Rj中的诸边在G中重复一次，
得到下图
G
。
(5)
G
是欧拉图，故它的一条欧拉回路即为最优解。
破圈法
(1) 奇点处作出标记如加“ *”或“ o”;
(2) 求该图的最小树(用破圈法，尽可能多的保留与奇点相连的边)；
(3) 在最小树上的奇点处添加重复边，以消灭奇点；
(4) 回到原问题，且按判优准则检验与调整，直至最优。
注1最小生成树的求法：设G是连通加权简单图，若G不是树，则G中 必有回路，我们删去G中含于某回路内权最大的一条边，所得图记为 G，G是
G的连通生成子图，下一步，若
G不是树，又从G的某回路内删去权最大的一 条边，如此下去，最后不能按上述方法删边时，得到的图
树，即 T 是
G
的最小生成树。
例 4 求下面图中的最优邮路。
解 显然此题属于无向图的中国邮路问题，故
(1) 先在图中找到奇点，并记上“ o”，如图(1):
(1)
T便是G的一棵生成
(2) 求出该图最小树，如图 (2) ：
(2(3))
(3) 在最小树上添加重复边，以消灭奇点，如图 (3) ：
(4) 经检验，此已是最优解(3)
此题的一条最优路线为
D I F E D I H G
I B A H ABC
有向图的中国邮路问题的算法
对称有向图的中国邮路算法较为简单，下面只研究非对称有向图的中国邮
路算法，算法如下：
⑴计算各结点的正，负度，求出
d i，且d i d Vj
d w。
(2) 添加一个超发点vs，对满足d i
0的结点Vi，加入d i条有向边
Vs，v，权均为0;添加一个超收点v，对满足d j 0的结点Vj，加入|d j |条 有向边vj,vt，权均为0,得到图G。
(3) 在G中求d vs条过以vs, vt为两端点的形如vs,v，vj,vt每边一次且 仅一次的总和最小的 巳道路，记下G中各边在这些道路中的重复次数。
(4) 计入各边的重复次数，G中存在有向欧拉回路，其中一条即为解。 例5求下图的中国邮路。
解 显然此题属于非对称有向图的中国邮路问题，故
(1)先求各结点的d i为d 1
⑵构造G如下图(a):
(a)
2，d 2 1，d 3 1，
(3) 得到2条总和最小的FSt道路P
F2
vs,w,v3, v2,vt
,
vs,v1,v3,vt
,
R 2
；
F2
4
； F 6.这样边
My
重复 2 次，边
v3,2
重
复1次，得下图，其中虚线边表示重复 1次。
(4) 上图即为欧拉图，其中一条欧拉回路如
v1,v3, v2,v1, v3,v2,v4,v1,v3,v4, v5, W
就是最佳邮路。
4中国邮路问题在实际生活中的应用与推广
无向图的中国邮路问题在实际生活中的应用
(b)
例6如下图(1)所示是忻州师范学院主区俯视图，图(2)是校内主干道的简
略图，其中每条道路上至少有一个垃圾筒，收垃圾大叔每天需将校内所有的垃
圾倒掉，下图中各边上的数字表示在此条路上完成任务所需时间(单位为分
钟)，问如何设计路线才能使大叔在完成任务的同时，所用时间最短？
⑴
分析 我们把这个问题抽象成上图 ⑵所示，其中G的结点v表示几条相交
道路的交点，各道路可用交点间的边表示，于是此问题就等价于图
在经过图G的每边一次且仅一次的闭迹问题。
方法一用奇偶点图上作业法
解 在G中有6个奇度数顶点V2, v3, v5, v4, v9,
V11.把它们配成三对:v与
V4
, V3与V5, V9与vn .在G中，取一条连接 5与V4的路7去驭4，并把边^2,v ，
G中是否存
乂
N4作为重复边加入图中；再将V3与V5间一条路V3V4V5，把边V3,V4
，
V4,V5
作为重复边加入图中，在v9与V11之间加一条重复边V9，Vii，如下图(a)中，这 个图中没有奇度数点，是一个 Euler图。
(b)
在图 (a) 中，顶点 v3， v4 间有三条重边，去掉其中两条，得到图 (b) ，该图 仍是一个 Euler 图。
在图(b)中，圈Vi,V2,V3,w的总权为6,而重复边的权和为2,小于该圈总 权的一半；圈
v2,v3,v4,v5,v6,v2
的总权为 11，而重复边的权和为 4，小于该圈总 权的一半；圈
v5,v4,v9,v8,v5
的总权为 8,而重复边的权和为 2,小于该圈总权 的一半；圈
v8,v9,v10,v11,v8
的总权为 12,而重复边的权和为 6,等于该圈总权的 一半；圈
v5,v4,v9,v10,v11,v8,v5
的总权为 16,而重复边的权和为 8,等于该圈总 权的一半；圈
v7,v8,v9,v10,v11,v12,v7
的总权为 20,而重复边的权和为 6,小于该 圈总权的一半。由此看来,在每个圈上,都满足重复边的权和不超过此圈权和 的一半,故图 (b) 为最优方案,其中一条欧拉回路即为最佳邮路,如
v1,v2,v6,v5,v8,v7,v12,v11,v8,v9,v10,v11,v10,v9,v4,v5,v4,v3,v2,v3,v1
即为一条最优邮 路,且最短时间为
49。
方法二 最小权匹配算法
解 显然此题属于无向图的中国邮路问题,故
(1) 先找出奇数结点
V0
G
(2)
v2,v3,v4,v5,v9,v11
；
再求V G各结点在G中的最短路径p及长度 y,Vj
,
P23
P25
P2,11
V2,V3
,
V2,V6,V5
,
23
2
?
25
P24
P29
V2,V3,V4
,
V2,V3,V4,V9
24
5
；
4；
2,11
,
29
7；
V2,V6,V5,V8, V11
,
V3,V4
10 ；
P35
P34
,
334
；
39
V3,V4,V5
,
5
35
?
3,11
P39
V3,V4,V9
,
V4,V5
,
45
5；
P3,11
,,VV3,V4,V9,V
1011
11；
P45
P4,11
2；
P49
V4,V9
,
49
2
；
V4,V9,V10,V11
V5,V4,V9
,
59
4,11
8；
P5,11
P59
4； V5,V8,V11
,
5,11
6；
,11
v9
, v10
, v11
，
9,11
6。
v与V3, V4与V5, V9与V11
,在 对Vo
G的结点进行最小权匹配，得最佳匹配为
最小权匹配里各 Vj,Vj所对应的路径Rj中的诸边在G中重复一次，得到上图
(b) ，且其为欧拉图，故它的一条欧拉回路即为最优邮路。
方法三 用破圈法来求解此题
解 显然此题属于无向图的中国邮路问题，故
(1) 先在图中找出奇点，并记上“ o”，如下图(a):
(2) 求出该图最小树，如下图 (b) ：
(a) (b)
(3) 在最小树上添加重复边，以消灭奇点 , 如图 (c) :
(c)
(4) 经检验，此解已是最优解，其中任意一条欧拉回路即为最优解，如
V1,V2,V6,V5,V8,V7,V12,V11,V8,V9,V10,V11,V10,V9,V4,V5,V4,V3,V2,V3,V1
即为解，且最短时 间为 49。
例 7 下图是忻州师院校内某超市的内部过道，刚刚开学时，某同学需要购 买的物品比较多，下图中的数字表示在此货架上寻找自己所需物品的时间 (单位 为分钟)，问若他能一次性购齐所有物品，如何规划路线能使其所用时间最短？
分析 本题用上述的三种方法均可求解，下面用破圈法为例解决此题。
解(1)先找到图中的奇点，并记上“ o”，如图(a)所示：
(a)
(2) 求出该图的最小树，如图 (b) 所示：(方法用破圈法)
(b)
(3) 在最小树上添加重复边，以消灭奇点 , 如图 (c) ：
(c)
(4) 经检验，此解已是最优解，如
V1,V2,V3,V4,V5,V2,V1,V6,V7,V8,V9,V10,V1,V6,V7,V10,V1
就是一条最优中国邮路，且最 短用时为
41。
,11
v9
, v10
, v11
，
9,11
6。
有向图的中国邮路问题在实际生活中的应用
例 8 实例图仍为忻州师范学院，校内由于道路较窄，每到开学季，进入校 内的车辆较多，故每条道路都为单行线，其方向如图所示，某家长想开车环游 整个校园，问如何规划路线才能使其在不违反规定的条件下，将校内每条道的 风景都领略到呢？
解 显然此题属于非对称有向图的中国邮路问题，故
(1) 求得各结点的
d i
为
d 1 d 6 d 7 d 10 d 12 0，
d 3 d 4 d 9 d 11 1，d 2 d 5 1，d 8 2。
(2) 构造
G
如图 (b) ：
(b)
(3) 得到4条总和最小的 巳道路R
vs,v2,v1,v3,vt ,
R 4;
P2
vs,v5,v6,v2,v1,v3,v4,vt
,
P2
11;
P3
vs,v8,v5,v6,v2,v1,v3,v4,v9,vt
,
P3
15;
P4
vs,v8,v5,v6,v2,v1,v3,v4,v9,v10,v11,vt
,
P4
21; Pi
51.
这样边
v2,v1
,
v1,v3
各重复 4次，边
v6,v2
,
v5,v6
,
v3,v4
各重复 3次，边
v8,v5
,
v4,v9
各重复 2次，边
v9,v10
,
v10,v11
各重复 1次，得到下图 (c) ，其中 虚线边数表示重复次数。
(c)
(4) 图(c)是欧拉图，其中一条欧拉回路即为最佳邮路。
5 结束语
中国邮路问题是我国着名图论学者管梅谷教授首先提出并解决的，后人在 其已有的基础上进行了深入研究，取得了瞩目的成果，本文通过对不同种情况 的详细研究与总结，找到了几种不同的中国邮路问题的算法，并将其再次应用 于现实生活中，尤其以我的大学校园 --- 忻州师范学院为素材，全面运用中国邮 路知识进行分析，并解决了实际生活中的最短路问题，为后人学习和生活提供 帮助。
参考文献
[1] 顾守淮.中国邮路问题的一个算法 [J]. 兰州交通大学学报 , 1992,8(1):10-13.
[2] 吴杰.求解中国邮递员问题的一种思路 [J]. 科技资讯 ,2007,4(5):1-5.
[3] 吴正奎,王全文, 刘振航. 中国邮路问题的一个解法 [J] .运筹与管理 ,
2004,3(3):5-9.
[4] 管梅谷 . 中国投递员问题综述 [J]. 数学研究与评论 , 1984,5(1):18-21.
[5] 孟亚坤 . 时间依赖网络中国邮路问题的列生成算法 [J]. 大连理工大学 ,
2010,8(11):6-10.
[6] 孙景昊.时变中国邮路问题的整数规划模型及算法研究 [J]. 大连理工大学 ,
2012, 6(3):6-9.
[7] 耿素云,屈婉玲, 王扞平. 离散数学教程 [M] .北京: 北京大学出版社 , 2002.
[8] 汪海森,林耿, 卓彩娥.中国邮递员问题的匹配算法 [J] .长江大学学院， 2013, 8(9):12-15.
[9] 殷剑宏,吴开亚. 图论及其算法 [M] . 北京: 中国科学技术大学出版社 , 2003.
[10] 戴一奇, 胡冠章, 陈卫. 图论与代数结构 [M] . 北京:清华大学出版社 , 1995.
致谢
岁月如梭，短暂而有意义的大学生活即将结束，此时看着毕业设计摆在面 前，我感慨万分。它不仅承载了我四年来的学习收获，更让我学会了如何求 学、如何进行科学研究甚至如何做人。回想起四年的学习生活，有太多的人给 我以帮助与支持，指导与鼓励。在此我对我所有的恩师以及所有的同学们表示 我最真诚的谢意！
首先衷心感谢我的恩师曹教授对我的悉心教诲与指导！在跟随曹老师的这 段日子里，我不仅跟曹老师学到了许多专业知识，同时也学习到了她严谨求 实、一丝不苟的治学态度和孜孜不倦的伟大精神，它会使我受益终身。在此， 我对曹老师的教育与培养表示衷心的感谢！
同时我还要感谢学校领导和数学系的师生对我日常生活的关心和照顾，思 想上的启发，以及为我提供了如此良好的学习环境。谢谢你们！
2024年3月7日发(作者：楼典)
目 录
中国邮路问题及其算法
Xxxxxx 系本 xxxxx 班 xxxxxx
指导教师： xxxxxxx
摘 要：本文利用图论中的相关概念阐述并解决中国邮路问题，通过比较不同路
目 录
径，归纳总结，找到其具体算法，再利用上述方法找到的具体算法，求解实例，加以
验证，然后将其推广到实际生活中，帮助人们快速找到欧拉回路，即找到省时，省
力，省钱的最佳路线，对于图论教学及理论研究均有一定的指导意义。
关键词： 中国邮路，欧拉回路，最佳路线。
China's postal problem and its algorithm
Xxxxxxxxx
Class xxxxx,The Department of mathematics
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,es
em
，即结点数V n，边数E m。
(2) 图G的边可以是有方向的，也可以是无方向的，它们分别称为有向边 和无向边，用ek
Vi,Vj表示。
定义2
G V,E的某结点所关联的边数称为该结点的度，用d v表 示。
v定义3任意两结点间最多只有一条边，且不存在自环的无向图称为简单 图。
性质1设G V,E有n个结点，m条边，则
性质2
G中度为奇数的结点必为偶数个。
定义4若图G V,E的每条边ek
vi,vj都赋以一个实数Wk作为该边的 权，则称G是赋权图，特别地，如果这些权都是正实数，就称
G是正权图，权 可以表示该边的长度，时间，费用或容量等，如下图所示：d v 2m。
v V 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
存在欧拉道路。
推论2若有向连通图G中各结点的正、负度相等，贝U G存在有向欧拉回 路。
中国邮路问题
中国邮路问题，它是由中国数学家管梅谷教授首先提出而得名。设邮递员 从邮局出发，遍
历他所管辖的每一条街道，将信件送到后返回邮局，要求所走 的路径最短，当然如若他所管辖的街道构成一欧拉回路，贝这欧拉回路便是所 求的路径，如若不然，即存在度数为奇数的顶点时，必然有些街道需要走多于 1 遍，如何寻求最短的路？ (基本思路：根据欧拉圈原理，用奇偶点图上作业法， 使邮递路线为最短)
现将中国邮路问题用图论的语言描述如下：
设G V,E是连通图，而且对于所有的e E
,都赋以权ce 0，求以点
v V出发，通过所有边至少一次，最后返回 v点的回路C,使得 ce达到最
eC
小。
无向图的中国邮路问题
邮递员从邮局出发，走完投递线路后又回到邮局，这就要求邮递员的行走 路径必须是欧拉圈，但是由于城市街道及邮递点组成的图有三种基本类型，相 应的就有三种类型线路，不管何种类型，归根到底，都要设法使之形成欧拉 圈。
(1) 图G里没有奇次定点。即G中各结点的度都是偶数，那么G
一定有欧 拉回路，显然任何一条欧拉回路都是该问题的解。如下图所示：
图
投递路线为： A B C I J K H G E
H G E D H K J I
D
C
H
B
I
A
A
或者可为：
A I
这时没有重复行走的街道，当然邮路最短。
(2) 图G中只有2个结点Vi, Vj的度是奇数，则一定存在从Vi到Vj的一条欧 拉道路，它经过了
G的各边一次。在G中再找一条从vj到vi的最短道路Pji，则 G G Pji中存在欧拉回路。这样G中的欧拉回路，即对应于G中pjj的边重 复一次而其余边只过一次的回路是一条中国邮路，即最佳邮路。如下图所示：
图(
b)
如图，B , E是奇次顶点，因此要构成一个欧拉回路，
一次，这样存在许多重复走的方案，例如
B F E ; B F C E ; B C D E ; B C E 等。
B E线路必须重复走
我们计算一下重复走的长度分别为 4， 6， 5， 5；当然需要重复走的线路以
B F E 为最好，故巧加边，是使其形成欧拉回路的方法，故此时线路为
A B F E D C E F C B F A. 总长度为 21，且此路 线是最短的。
(3) 图
G
中度为奇数的结点数多于 2 个，则需要添加很多条边，才能形成欧 拉回路，且有几对奇次顶点，就要加几条边，此时巧加边问题更加重要。如下 图：
如图，有 8个奇次顶点，它们是 B ,C,E ,H ,G
,J ,I , L .如何巧妙地把这 8个奇次 顶点恰当地组合成 4对呢？我们参照上一题的例子，便可将 8 个奇次顶点配成以 下 4对： LI ,BC,JG,HE .这是必须重复走的最短线路，且长度为 11，最优投递 路线总长为 60，其中一条最佳路线为
A B C D E F G H E H C B I J G J K
LILA
有向图的中国邮路问题
(1) 图
G
中含有正度或负度为 0 的结点，此时不存在最佳邮路。如图所
示：
图
图
G
中各结点的正，负度相等，此时
G
中一定存在有向欧拉回路。它过
每边一次且仅一次，因此任意一条欧拉回路都是中国邮路。如下图所示：
图 图
G
不对称，即存在一些结点 v ， d v d v ，其中 d v 的值是以
iiiv为始点的边的数目，d v的值是以v为终点的边的数目。
不妨设d Vi
d Vi，由于邮递员要经过进入Vi的每条边，因此他一定
要重复走以Vi为始点的某条边。设fij表示边Vi
,Vj的重复次数，Wij表示该边的 权，那么中国邮路要选择重复一些边后存在有向欧拉回路，并且使
最小的一个解，显然此时满足 d Vi
即
j
wij
fij
为
i, j E G
fji
d Vi
fij
，
Vi
V G
fij
f
ji
d vi
d vi
d i .
(i) 若
d i 0
，表示邮路中 vi
要
d i
次重复经过 vi
所发出的一些边，或者说 vi
可供应
d i
个j j
单位量。
(ii) 若d i 0,表示邮路中Vi要d i次重复经过进入M的一些边，或者说w 可接收
d i
个单位量。
(iii)
若d i 0,则称Vi是中间结点。由于
d Vid v，所以
d i 0，这样可以逐次保证每个可供应点 vi
经过一些边向某个接收点 vj
供 应一个单位量，最后达到平衡，或者说这些道路上的边出现重复，最后得到的 图
G
是有向欧拉图，若这些重复边的总长最小，它即是最佳邮路。
例1求下图的中国邮路。
解 此题显然是有向中国邮路问题中的不对称型，故
(1) 各结点的
d i
为
d
1 d 5
0
，
d 2 2，
d 3 1，
d 4
1
(2) 构造
G
图
图 得到 2 条总和最小的
Pst 道路
P1
Vs,V2,V4,Vt
,
Vs,V2,V4,V3,Vt
P1
5
?
6;故 Pi
11. 这样边
V2,V4
重复 2 次，边
2
P，
P2
V4,V3
重复 1 次，得图，其中虚线边表示重复 1 次
(4) 图是欧拉图，其中一条欧拉回路，如
V1,V2,V4,V3,V2,V4,V3,V5,V2,V4,V5,V1
就是最佳邮路。
3 中国邮路问题的算法
无向图的中国邮路问题的算法 奇偶点图上作业法
(1) 把G中所有奇度数顶点配成对，将每对奇度数顶点之间的一条路上的每 边改为二重边，得到一个新图 G,新图G中没有奇度数顶点，即G为多重Euler 图。
(2) 若G中某一对顶点之间有多于2条边连接，则去掉其中的偶数条边，留 下 1 条或 2条边连接这两个顶点，直到每一对相邻顶点至多由 2条边连接，得到 图 G2
。
(3) 检查G2的每一个圈C,若某一个圈C上重复边的权和超过此圈权和的一 半，则将C进行调整。重复这一过程，直到对 G2的所有圈，其重复边的权和不 超过此圈权和的一半，得到图
G3
。
(4) 求Ga的Euler回路。
例2求下图所示图G的中国邮路。
图G
解 图G中有6个奇度数顶点v2, v4, v5, v7, v9, v10.把它们配成三对：v2与
V5, V4与V7
, V9与Vio，在图G中，取一条V2与V5的路V2V3V4V5，把边
V2,Va
, Va,V4
, V4, V5作为重复边加入图中；再取V4与V7之间一条路V4V5V6V7， 把边V4,V5
,
V5,V6
, V6,V7作为重复边加入图中，在V9和血之间加一条重复边
V9,Vio，如图⑵，这个圈没有奇度数点，是一个 Euler图。
(2) (3)
在图(2)中，顶点V4与V5之间有三条重边，去掉其中两条，得到图(3)，该 图仍是一个Euler图。
在图⑶中，圈V2V3V4V11V2的总权为24，而圈上重复边的权和为14，大于该 圈总权的一半，于是去掉边 V2,V3
和 V3,V4
上的重复边，而在
V2,V11
和
V4,V11
上加入重复边，此时重复边的权和为 10，小于该圈总权的一半。同理，圈
V5V6V7V12V5的总权和为15,去掉边V5,V6和V6,V7上的重复边，在边V5,Vi2和
V7,W2上加重复边，如下图 ⑷：
⑷ (5)
图(4)中，圈V4V5V12V11V4的总权为15,而重复边的权和为8,从而调整为图
⑸。
图⑸ 中，圈V1V2V11V12V7V8V9V10V1的总权为36,而重复边的总权为20,继续调整 为图⑹：
(6)
经检验，图(6)为最优方案，其中一条欧拉回路就是最佳邮路。
最小权匹配算法
(1) 确定G中度为奇数的结点，构成Vo
G
。
(2) 求V。G各结点在G中的最短路径R及其长度 Vi,Vj。
(3) 对Vo G的结点进行最小权匹配，即选出 Vo G /2个 Vi,Vj ,保证每个
结点Vi
Vo
G在Rj中只出现一次，同时满足这些
(4) 在最小权匹配里各
得到G。
(5)
G是欧拉图，它的一条欧拉回路即为最优解。
例3求下图所示图G的中国邮路。
解显然此题属于无向图的中国邮路问题，故
(1) 首先找到奇数结点，Vo
G
V2,V3, V4,V5,V6,V7。
Vi,Vj的总和最小。
R中的诸边在G中重复一次，
V ,Vj所对应的路径(2) 求V。G各结点在G中的最短路径R及长度 Vi,Vj，
V2,V7
, V3
，
23
V2,V7,V5
，
V2,V7
，
27
25
R23
4 ；
7 ；
R24
R26
R34
V2.V7.V4，
V2,V1,V6
，
V3,V4
，
34
24
4
R25
R27
26
；4
；
2 ；
3
；
R35
V3,V4,V5，
35
6 ；
P36
V3,V7,V6，
36
6
；
R37
V3,V7
，
37
2；
46
R45
V4,V5
，
V4,V7
45
57473
2
5
R46
V4,V5,V6
V5,V6
，
V6,V7
，
56
6 ；
R47
R57
R56
3；
，
V5,V7
，
R67
67
4.
；
(3)
对V°G的结点进行最小权匹配，得最佳匹配
V2,7
,
V3N4
,
V5N6
。
(4) 在最小权匹配里各 Vj,Vj所对应的路径Rj中的诸边在G中重复一次，
得到下图
G
。
(5)
G
是欧拉图，故它的一条欧拉回路即为最优解。
破圈法
(1) 奇点处作出标记如加“ *”或“ o”;
(2) 求该图的最小树(用破圈法，尽可能多的保留与奇点相连的边)；
(3) 在最小树上的奇点处添加重复边，以消灭奇点；
(4) 回到原问题，且按判优准则检验与调整，直至最优。
注1最小生成树的求法：设G是连通加权简单图，若G不是树，则G中 必有回路，我们删去G中含于某回路内权最大的一条边，所得图记为 G，G是
G的连通生成子图，下一步，若
G不是树，又从G的某回路内删去权最大的一 条边，如此下去，最后不能按上述方法删边时，得到的图
树，即 T 是
G
的最小生成树。
例 4 求下面图中的最优邮路。
解 显然此题属于无向图的中国邮路问题，故
(1) 先在图中找到奇点，并记上“ o”，如图(1):
(1)
T便是G的一棵生成
(2) 求出该图最小树，如图 (2) ：
(2(3))
(3) 在最小树上添加重复边，以消灭奇点，如图 (3) ：
(4) 经检验，此已是最优解(3)
此题的一条最优路线为
D I F E D I H G
I B A H ABC
有向图的中国邮路问题的算法
对称有向图的中国邮路算法较为简单，下面只研究非对称有向图的中国邮
路算法，算法如下：
⑴计算各结点的正，负度，求出
d i，且d i d Vj
d w。
(2) 添加一个超发点vs，对满足d i
0的结点Vi，加入d i条有向边
Vs，v，权均为0;添加一个超收点v，对满足d j 0的结点Vj，加入|d j |条 有向边vj,vt，权均为0,得到图G。
(3) 在G中求d vs条过以vs, vt为两端点的形如vs,v，vj,vt每边一次且 仅一次的总和最小的 巳道路，记下G中各边在这些道路中的重复次数。
(4) 计入各边的重复次数，G中存在有向欧拉回路，其中一条即为解。 例5求下图的中国邮路。
解 显然此题属于非对称有向图的中国邮路问题，故
(1)先求各结点的d i为d 1
⑵构造G如下图(a):
(a)
2，d 2 1，d 3 1，
(3) 得到2条总和最小的FSt道路P
F2
vs,w,v3, v2,vt
,
vs,v1,v3,vt
,
R 2
；
F2
4
； F 6.这样边
My
重复 2 次，边
v3,2
重
复1次，得下图，其中虚线边表示重复 1次。
(4) 上图即为欧拉图，其中一条欧拉回路如
v1,v3, v2,v1, v3,v2,v4,v1,v3,v4, v5, W
就是最佳邮路。
4中国邮路问题在实际生活中的应用与推广
无向图的中国邮路问题在实际生活中的应用
(b)
例6如下图(1)所示是忻州师范学院主区俯视图，图(2)是校内主干道的简
略图，其中每条道路上至少有一个垃圾筒，收垃圾大叔每天需将校内所有的垃
圾倒掉，下图中各边上的数字表示在此条路上完成任务所需时间(单位为分
钟)，问如何设计路线才能使大叔在完成任务的同时，所用时间最短？
⑴
分析 我们把这个问题抽象成上图 ⑵所示，其中G的结点v表示几条相交
道路的交点，各道路可用交点间的边表示，于是此问题就等价于图
在经过图G的每边一次且仅一次的闭迹问题。
方法一用奇偶点图上作业法
解 在G中有6个奇度数顶点V2, v3, v5, v4, v9,
V11.把它们配成三对:v与
V4
, V3与V5, V9与vn .在G中，取一条连接 5与V4的路7去驭4，并把边^2,v ，
G中是否存
乂
N4作为重复边加入图中；再将V3与V5间一条路V3V4V5，把边V3,V4
，
V4,V5
作为重复边加入图中，在v9与V11之间加一条重复边V9，Vii，如下图(a)中，这 个图中没有奇度数点，是一个 Euler图。
(b)
在图 (a) 中，顶点 v3， v4 间有三条重边，去掉其中两条，得到图 (b) ，该图 仍是一个 Euler 图。
在图(b)中，圈Vi,V2,V3,w的总权为6,而重复边的权和为2,小于该圈总 权的一半；圈
v2,v3,v4,v5,v6,v2
的总权为 11，而重复边的权和为 4，小于该圈总 权的一半；圈
v5,v4,v9,v8,v5
的总权为 8,而重复边的权和为 2,小于该圈总权 的一半；圈
v8,v9,v10,v11,v8
的总权为 12,而重复边的权和为 6,等于该圈总权的 一半；圈
v5,v4,v9,v10,v11,v8,v5
的总权为 16,而重复边的权和为 8,等于该圈总 权的一半；圈
v7,v8,v9,v10,v11,v12,v7
的总权为 20,而重复边的权和为 6,小于该 圈总权的一半。由此看来,在每个圈上,都满足重复边的权和不超过此圈权和 的一半,故图 (b) 为最优方案,其中一条欧拉回路即为最佳邮路,如
v1,v2,v6,v5,v8,v7,v12,v11,v8,v9,v10,v11,v10,v9,v4,v5,v4,v3,v2,v3,v1
即为一条最优邮 路,且最短时间为
49。
方法二 最小权匹配算法
解 显然此题属于无向图的中国邮路问题,故
(1) 先找出奇数结点
V0
G
(2)
v2,v3,v4,v5,v9,v11
；
再求V G各结点在G中的最短路径p及长度 y,Vj
,
P23
P25
P2,11
V2,V3
,
V2,V6,V5
,
23
2
?
25
P24
P29
V2,V3,V4
,
V2,V3,V4,V9
24
5
；
4；
2,11
,
29
7；
V2,V6,V5,V8, V11
,
V3,V4
10 ；
P35
P34
,
334
；
39
V3,V4,V5
,
5
35
?
3,11
P39
V3,V4,V9
,
V4,V5
,
45
5；
P3,11
,,VV3,V4,V9,V
1011
11；
P45
P4,11
2；
P49
V4,V9
,
49
2
；
V4,V9,V10,V11
V5,V4,V9
,
59
4,11
8；
P5,11
P59
4； V5,V8,V11
,
5,11
6；
,11
v9
, v10
, v11
，
9,11
6。
v与V3, V4与V5, V9与V11
,在 对Vo
G的结点进行最小权匹配，得最佳匹配为
最小权匹配里各 Vj,Vj所对应的路径Rj中的诸边在G中重复一次，得到上图
(b) ，且其为欧拉图，故它的一条欧拉回路即为最优邮路。
方法三 用破圈法来求解此题
解 显然此题属于无向图的中国邮路问题，故
(1) 先在图中找出奇点，并记上“ o”，如下图(a):
(2) 求出该图最小树，如下图 (b) ：
(a) (b)
(3) 在最小树上添加重复边，以消灭奇点 , 如图 (c) :
(c)
(4) 经检验，此解已是最优解，其中任意一条欧拉回路即为最优解，如
V1,V2,V6,V5,V8,V7,V12,V11,V8,V9,V10,V11,V10,V9,V4,V5,V4,V3,V2,V3,V1
即为解，且最短时 间为 49。
例 7 下图是忻州师院校内某超市的内部过道，刚刚开学时，某同学需要购 买的物品比较多，下图中的数字表示在此货架上寻找自己所需物品的时间 (单位 为分钟)，问若他能一次性购齐所有物品，如何规划路线能使其所用时间最短？
分析 本题用上述的三种方法均可求解，下面用破圈法为例解决此题。
解(1)先找到图中的奇点，并记上“ o”，如图(a)所示：
(a)
(2) 求出该图的最小树，如图 (b) 所示：(方法用破圈法)
(b)
(3) 在最小树上添加重复边，以消灭奇点 , 如图 (c) ：
(c)
(4) 经检验，此解已是最优解，如
V1,V2,V3,V4,V5,V2,V1,V6,V7,V8,V9,V10,V1,V6,V7,V10,V1
就是一条最优中国邮路，且最 短用时为
41。
,11
v9
, v10
, v11
，
9,11
6。
有向图的中国邮路问题在实际生活中的应用
例 8 实例图仍为忻州师范学院，校内由于道路较窄，每到开学季，进入校 内的车辆较多，故每条道路都为单行线，其方向如图所示，某家长想开车环游 整个校园，问如何规划路线才能使其在不违反规定的条件下，将校内每条道的 风景都领略到呢？
解 显然此题属于非对称有向图的中国邮路问题，故
(1) 求得各结点的
d i
为
d 1 d 6 d 7 d 10 d 12 0，
d 3 d 4 d 9 d 11 1，d 2 d 5 1，d 8 2。
(2) 构造
G
如图 (b) ：
(b)
(3) 得到4条总和最小的 巳道路R
vs,v2,v1,v3,vt ,
R 4;
P2
vs,v5,v6,v2,v1,v3,v4,vt
,
P2
11;
P3
vs,v8,v5,v6,v2,v1,v3,v4,v9,vt
,
P3
15;
P4
vs,v8,v5,v6,v2,v1,v3,v4,v9,v10,v11,vt
,
P4
21; Pi
51.
这样边
v2,v1
,
v1,v3
各重复 4次，边
v6,v2
,
v5,v6
,
v3,v4
各重复 3次，边
v8,v5
,
v4,v9
各重复 2次，边
v9,v10
,
v10,v11
各重复 1次，得到下图 (c) ，其中 虚线边数表示重复次数。
(c)
(4) 图(c)是欧拉图，其中一条欧拉回路即为最佳邮路。
5 结束语
中国邮路问题是我国着名图论学者管梅谷教授首先提出并解决的，后人在 其已有的基础上进行了深入研究，取得了瞩目的成果，本文通过对不同种情况 的详细研究与总结，找到了几种不同的中国邮路问题的算法，并将其再次应用 于现实生活中，尤其以我的大学校园 --- 忻州师范学院为素材，全面运用中国邮 路知识进行分析，并解决了实际生活中的最短路问题，为后人学习和生活提供 帮助。
参考文献
[1] 顾守淮.中国邮路问题的一个算法 [J]. 兰州交通大学学报 , 1992,8(1):10-13.
[2] 吴杰.求解中国邮递员问题的一种思路 [J]. 科技资讯 ,2007,4(5):1-5.
[3] 吴正奎,王全文, 刘振航. 中国邮路问题的一个解法 [J] .运筹与管理 ,
2004,3(3):5-9.
[4] 管梅谷 . 中国投递员问题综述 [J]. 数学研究与评论 , 1984,5(1):18-21.
[5] 孟亚坤 . 时间依赖网络中国邮路问题的列生成算法 [J]. 大连理工大学 ,
2010,8(11):6-10.
[6] 孙景昊.时变中国邮路问题的整数规划模型及算法研究 [J]. 大连理工大学 ,
2012, 6(3):6-9.
[7] 耿素云,屈婉玲, 王扞平. 离散数学教程 [M] .北京: 北京大学出版社 , 2002.
[8] 汪海森,林耿, 卓彩娥.中国邮递员问题的匹配算法 [J] .长江大学学院， 2013, 8(9):12-15.
[9] 殷剑宏,吴开亚. 图论及其算法 [M] . 北京: 中国科学技术大学出版社 , 2003.
[10] 戴一奇, 胡冠章, 陈卫. 图论与代数结构 [M] . 北京:清华大学出版社 , 1995.
致谢
岁月如梭，短暂而有意义的大学生活即将结束，此时看着毕业设计摆在面 前，我感慨万分。它不仅承载了我四年来的学习收获，更让我学会了如何求 学、如何进行科学研究甚至如何做人。回想起四年的学习生活，有太多的人给 我以帮助与支持，指导与鼓励。在此我对我所有的恩师以及所有的同学们表示 我最真诚的谢意！
首先衷心感谢我的恩师曹教授对我的悉心教诲与指导！在跟随曹老师的这 段日子里，我不仅跟曹老师学到了许多专业知识，同时也学习到了她严谨求 实、一丝不苟的治学态度和孜孜不倦的伟大精神，它会使我受益终身。在此， 我对曹老师的教育与培养表示衷心的感谢！
同时我还要感谢学校领导和数学系的师生对我日常生活的关心和照顾，思 想上的启发，以及为我提供了如此良好的学习环境。谢谢你们！