邮路捷径

当你收到邮递员送来的报纸、信件的时候，你一定很高兴能从报纸上了解到国内外大事，从信中知晓亲戚朋友的消息。但不知道你是否注意到，邮递员每次送信都是沿着相同的街道、相同的方向送信。你会说，这些绿衣天使熟悉这些街道，甚至熟悉许多家庭，他们习惯于沿同样的路线送信，不管酷暑寒冬、刮风下雨，日复一日，年复一年。如何为他们选一条路程最短的“邮路”，使他们能相对轻松地完成他们的工作呢？这个问题是 1962 年由我国数学家管梅谷教授提出的，国际上因此而称为中国邮递员问题。

我们看一看下图所表示的一个简单的街区路线图，数字表示街道的长度

（米）。那么，假设邮递员从邮局出发，沿什么路线送完信件返回邮局，所走的路最少呢？

首先，要送完信、报等邮件，邮递员必须要经过每条街道至少一次。如果他能够每条街道只走一次而不重复，这样的路线当然就是最短路线。但在街道示意图上可以看出有 4 个交叉路口均与三条道路相连接（奇数条边）， 因此，这个图所表示的街道必然会有重复经过的路线。我们通过添加重复路线，使那些与奇数条边相连的点均变成与偶数条边相连。

然后，检查每一个回路，使重复路线的总长度不大于该回路总长度的一半。例如下图中，添加了 BC、CD、FG、GH 四条重复路线（在图中以弧线来表示）。检查回路 BCDE，回路总长度是 850 米，而重复边总长是 400 米，符合要求。再看 EFGH 回路，回路总长度是 750 米，重复边总长度是 350 米，也符合要求。这样，图上所有的点均与偶数条边相连接，每条原街道或者没添重复边，或者只添一条重复边。因此，上图就是邮递员所走的最小距离的“邮路”。你不妨试试看，如果不是这样的路线，其他路线均要走更长的路程。