二、邮递路线

问题 一个邮递员每次送信，要走遍他负责投递的范围内的街道，完成任务后回到邮局。问他按怎样的路线走，所走的路程最短？

这个问题叫做最短邮递路线问题，是一个即有趣又实用的问题。

例 3 图 8－4（a）、（b）都表示街道图。图中 A 是邮局的位置，问邮递员应如何设计他的邮递路线，才能使他所走的路程最短？

分析与解：由于（a）所表示的图无奇结点，所以是一个欧拉图。他可以从邮局出发，不重复地走遍每条街道，回到邮局，这就是投递员的最短路

线。而（b）所表示的图有六个奇结点，它不是一笔画，要不重复地走遍街道是不可能的。为了走遍所有的街道，必须重复走某些街道。重复走哪些街道才能使总路程最短呢？

由于任何一个图中奇结点的个数都是偶数，所以可把奇结点两两配对。如果在一对奇结点之间连一条虚线当作增添的重复边，奇结点就变成了偶结点，用这种方法可使原来的图变成没有奇结点的欧拉图（增添了重复边）。现在的问题是如何去连这些虚线，才能保证总路程最短。其原则是：

1. 连线（虚线）不能有重叠线段；

2. 在每一个圈上，连线长度之和不能超过圈长的一半。

例如，图 8－5（a）中，连虚线时在 KG 一段上发生重叠。根据原则（1）， 应去掉重叠部分改成图 8－5（b）。但在（b）中，对于 BKJCB 这个圈来说， 增添的虚线长超过圈长的一半。根据原则（2），可以继续改进成（c）中增添虚线的情形，这是一种最好的增添虚线的方法。因此，最好的投递路线是ABCDE－FIFJCBKGFGHNA（参看图 8－6）

例 4 图 8－7 表示某城市的街道图，九个区都是边长为 1 公里的正方形，现需设一牛奶站，希望找一最佳地址，要能使送奶车以最短路程跑遍城市的所有街道，然后返回奶站。如果小明把奶站选在 P 点，试问他选的地方对吗？送一遍奶所走的最短路程比该城市全部街道的总长长多少？

分析与解：由于图 8－7 中有 8 个奇结点，所以必须重复走某些街道， 才能送遍全城回到奶站。根据例 3 中的两条原则，重复路线可添设如图 8－8。这样图中的结点全部为偶结点，说明奶站设在街道任何一处都一样。因此， 小明选在 P 点没有错。一次送遍全城回到奶站的最短路程应是 24＋4＝28（公里）比城市全部街道总长多 4 公里，多走城市街道总长的 16.7%。