中国邮递员问题为著名图论问题之一，问题情况如下：邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线？此问题由中国数学家管梅谷于1960年首先研究并给出算法，因此被命名为“中国邮递员问题”。

讲到这里同学们可能会联想到一个熟悉的游戏-一笔画问题：在一张纸上，给定若干个点与若干连接点的线段，不抬起笔尖，怎样划出一条闭合的路线。

（图片来源于网络）

图文简介

图，简单来说，是点与线的集合。图论，即为研究图的性质，关系，算法的科学。

图论的概念起源于18世纪初期，当时瑞典数学家Euler解决了著名的Konisberg七桥问题，为图论的理论应用立下了一个坚实的基础。伴随随着工业技术的发展与计算机科技的诞生，不断精化的图论理论开始在各领域大放异彩。

解决邮递员问题的核心概念—度

想要系统化地解决邮递员问题，必须先了解一个概念：点的度（degree），也可被称作阶（order）。

接下来，咱们看看什么是度？

点的度定义：在图中，与某一点关联的边的数目。

奇数度的顶点称为奇点，反之为偶点。

举两个简单的例子：

例1：

下图中与点A相关联的边有AB与BC，因此点A的度为2。与点B相关联的边只有AB，因此点B的度为1，与点C相关联的边只有AC，因此点C的度为1

例2：

下图中与点A相关联的边有AB与BC，因此点A的度为2。与点B相关联的边只有AB、BC，因此点B的度为2，与点C相关联的边有AC、BC、CD、CE，因此点C的度为4。下图中与点D相关联的边有CD与DE，因此点D的度为2。同理点E的度也为2。

值得一提的是，在本张图中，每一个点的度都为偶数。换言之，每个点都是点。此时，例2的图被称为欧拉图。找到或者构造欧拉图，是中国邮递员问题的核心目标。现在回到中国邮递员问题的目标，在例2 图中，从任意一个点出发，都可以构造出一条邮递员路径，例如：从点A出发，我们通过 A-B-C-E-D-C-A的路径，即可以经过图中所有的线，这里有的同学可能会问了，如果一个图中存在奇点，即度为奇数的点，该怎么办呢？

我们这里把例2的图稍微改一下，此时点B和点E的度都变成了3，根据不同的目标和限制条件，有两种优化方式：

1.继续连接BE，使得BE的度全部变为4，此时图再次成为欧拉图。

2.我们选择B作为路径起点，E作为路径终点，这样同样可以构造出中国邮递员问题的解。

思考题：

构造一条从A点出发，在A点结束的邮递员路径。（提示：某些边可以重复走）如果可以，找到总长最短的路径。

本期IB学习干货文章由美国罗彻斯特大学统计硕士Joseph老师整理编辑！更多国际教育学习干货我将持续更新，欢迎关注！遇到学习或申请疑问的同学也可以来私聊咨询。