在18世纪时，在普鲁士的哥尼斯堡市上。那时候，哥尼斯堡市的人民们喜欢在桥边漫 步，在当时就产生了这样的问题：可不可以制出一个方案，从自家里出发，经过的每一座 桥刚好一次，最后回到家里。后来这就是著名的“哥尼斯堡七桥问题”。这个问题人们想 尽了很多办法去解决这个问题，可是居然在一段时间内没有人能够解决的出来，这个问题 在后来就传到了著名数学家欧拉那里，却也让他感起了兴趣。经过他的研究之后，在人们 寻求路线中屡遭的失败的教训里敏锐地领悟到了，欧拉相信这个方案是不存在的。于是在 1736年解答了这个问题，还向圣彼得堡科学院递交了一份为《哥尼斯堡的七座桥》的文章。66327

这篇文章的重要的焦点是有名的“一笔画问题原理”。适合以下的要求的图就可以一 笔画出：一是图要连着，就是点和点之间有线连着；二是奇点的多少个情形，当且仅当奇 点个数为0时，起点开始，不能断线，最后回到起点，这就形成了一笔搞定，这就是欧拉

回路。而当奇点个数为2时，也能够形成的一笔画就是欧拉迹。如果奇次点的个数大于了 两个，这样的路就找不出来了。像这种情景后来总结是：没有欧拉圈和欧拉链。

首先考虑最简易的情形，即 G 是Euler图的情形。若 G 是Euler图，则由于任何Euler 有向回路都是一条通过 G 的每条边正好一次的邮路，因而是最佳邮路。在这种情形下， 中国邮递员问题是容易解决的。因为在这样的图中存在着确定Euler有向回路的有效算法。

一位送邮件的邮递员，准备开始送邮件，先是在邮局里挑出他要送出去所经过的街道 的邮件，再就是开始按照街道开始投递这些邮件，依次投递完邮件，最后回到邮局。在邮 递员投递邮件的过程中他必须走过他要去投递点的街区每条街道至少一次的，怎么走才能 够让邮递员所走的路程最短。如果能找到这样的一条最短投递路的问题，学术上就是称为 中国邮递员问题，因为它是在1956年第一次由中国的数学家管梅谷研究和提起的。

其中图论描写的是如果无向连通图 G  (V , E) 其中V  v1, v2 ,..., vn 是图 G 中点的集

合，则 E e     , e

,..., e 是图 G 的边集，令 w

是边 e

上加权的值，则对图 G 中给定的点 v  ，

11     12 ij ij ij n

然后要从所有的路径集 P 里找到一条这样的最佳路径 P 。而 P 要能够服从：1) P 从点 v

j j j j 1

开始到点 vn 终止；2) e11, e12,..., eij  Pj ；其中 Pj  满足 D(Pj )  min{D(Pj )}，全部的边用 Dx

来表示。 在数学的历史长河里上，能够以中国开头取名字的定理和理论不见的多。就像“中国邮递 员问题（Chinese Postman’s Problem，以下简称CPP）”[1]，也是近代出现的问题，所以当 时研究这个问题还是比较火的。

在1965年，J.Edmonds国就发表了一篇文章，关于CPP问题的。文章的名称就是“The Chinese Postman’s Problem”[1]。而在这篇论文中只有一页，Chinese Postman’s Problem的 由来是Edmonds把管的奇偶点图上作业法当中提出的问题，并说明了他在1965年上发表的 求任一图的最小权匹配的算法[1]。论文网

奇偶点图上作业法是管梅谷在1960年时在中国就发表了，然后在1962年的时候它在美 国就刊出了它的文章翻译成英文了。就在1965年时，The Chinese postman problem这一文 Ed-mond所写的文章就在这时发表了 [1]。之后有关于CPP的论文和文章就比较少了，在 R.Bellman与K.Cooke这两人共同发表了题为The Konigsberg bridges problem generalized一 文中，这还是和CPP的问题有关联的。在这篇文章中，这两个人是提出了一笔画问题被推 广为“可以反复并且让复制的边数是最小”的问题，并提起了用动态规划处理这个问题的