图的理论是应用在很多地方的，是运筹学里的一部分。已在科学管理，信息理论，化 学中的应用，计算机和电子等各个领域中广泛得到应用了。在实际生活、生产和科学研究 过程中，我们能够运用图的伦理和还有一些方法来处理很多的问题。就像在结合生产中， 为完成某些任务，各工学和理学之间怎么样联接，才能够使生产的任务完成变得方便又省 事。一个邮递员送邮件，要他走完他所负责邮递的所有街道，然后回到邮局，应该按照怎 么样的路线走，才能够找出最佳路线。中国邮递员问题是在 1960 年里，在实际过程中首 次提出数学问题。原本在实际生活问题是这样的：“一个邮递员要把他所负责的邮件送到 每条街道，应该怎么走才能让走的路程又快又短，”。在以前开始研究中国邮递员问题时， 国外就有人研究过旅行售货员的问题，即：“一个售货员要到 n 个城市去售货，要走遍所 有城市时，应当如何选择出一条最佳的路线，走的路程又短”。这个难题就比较难解决了。 当 n 较大时，即便使用大型的计算机，也是很难解决。邮递员在面临问题时显然可以归纳 为旅行售货员的问题。实际上，把邮递员必须送的每一个地点看作是一个城市就好了。但 是一般来说，邮递员要每次到约二、三百多个地点送信，若归纳为旅行售货员问题来解决， 这将是一个规模很大的问题了，是没有解决的。但是在仔细了解了邮递员遇到的问题后， 发觉这个问题具有一定的特点，即需要送邮件的地点一般都是比较稠密的排序在街道上 的。所以真实上像这样的“最短邮递路问题”，在 1965 年后来在国外就称为“中国邮员问 题”。论文网

1.2 国内外研究现状与发展趋势

1.3 基本概念及符号说明

1.3.1 基本概念

路(Walk)：图 G 中一个点边交替出现的序列 w v0e1v1e2 ek vk 。 迹(Trail)：边不重的途径。

路(Path)： 顶点不重复的迹。 圈(Cycle)：一条封闭的路称为圈。

简单图(Simple Graph)：如果一个图 G 没有环和多重边，那么称 G 为简单图。

欧拉链（Euler chain）：有一个非空连通图且存在一条链，过每边一次且仅一次。 欧拉圈（Euler circle）：若有一个简易圈，过每边一次且仅一次。 欧拉图（Euler）：一个图有欧拉圈。

连通性(Connectivity)：在图 G V , E中，若从点 v 到点 v 有路相连，则称 v 和 v 连通。

i j i j

割边(Cut edge)：若 e 是连通图 G 中的一边，如果从 G 中丢去 e，图就不连通了。 连通图(Connected graph)：如果图 G 中的任意的两个点间都是连通的，则称 G 为连通图。 无向图(Undirected graph)：一个图 G 是由点和边构成的。文献综述

弧(arc)：带箭头的连线。

简单图(Simple Graph)：如果一个图 G 没有环和多重边。

度(degree)： 一个图 G (V, E) ， vV (G)，图 G 与 v 有关联边的边数量。 环(ring)：图 G (V, E) 中端点重合为一点的边。

1.3.2 符号说明

V G：图 G 的顶点集

EG：图 G 的边集

w(e) ：每条边上的权

dG (V) ：图 G 上的顶点的度数

1.4 用到的定理

定理 1：若无向连通图 G (V, E) 是欧拉图，它的充要条件是在 G 中任何一个顶点的 度数为偶数。

定理 2：一个连通图有欧拉迹当且仅当它最多有两个奇点[11]

定理 3：设 C 是一条经过赋权连通图 G 的每条边至少一次的回路，则 C 是的最优回路， 当且仅当 C 对应的欧拉图 G* 满足：