如何使邮递线路最短

大家知道，邮递员为了完成投递任务，每天必须从邮局出发，走经投递区域内的所有道路，最后返回邮局。邮递员应当怎样安排自己的投邮路线， 才能使邮递线路最短呢？这显然是邮递员所苦恼的问题。

下面让我们分析一下邮递线路问题的实质。

很清楚，投递的线路必须是连通的。因而，对某个邮递员来说，他所负责的投邮路线，可以看成是一个脉络。

如果上述脉络所含的全是偶点，那么脉络中的所有弧线，便能形成一条封闭的回路。此时，求最短邮递线路，实际上就是一笔画问题。而且邮递员从邮局出发，最后回到了邮局，完成了一次循环。

如果一个邮递网络，除了偶点之外还含有奇点，由于网络的奇点必定成双，因而我们可以将奇点分为若干对，在每对奇点之间用弧线连接，使添加弧线后的新图形成为不含奇点的脉络。前面说过，这样的脉络的全部弧线， 可以构成一条封闭回路，从而为邮递员提供了一条可行的投邮线路。

下图是一个简单的例子。图中的方格状道路网代表投邮区域；“★”为邮局；奇点间添加的弧线画成虚线，相应的投邮路线为：

K（★）→H→G→F→E→D→C→B→A→I→A

→B→J→D→E→K→J→I→H→K（★）。

容易算出这条投邮路线的总长度为 140 个单位。

读者可能已经注意到：对于一个网络，奇点间用弧线联接的方法是多种多样的，各种添加的方法都提供了一种可行的投邮路线。问题是：哪一种投邮路线才是最合理的呢？

答案几乎是显而易见的！即添加进去的弧线应当越短越好。要达到这一点，必须做到以下两点：

（甲）添加进去的弧线不能出现重叠；

（乙）在每一个圈状的道路图上，添加进去的弧线，其长度的总和不能超过该圈长的一半。

用上面两条原则，判断一下前面例子中的那种弧线的添加方法，就会发现其中有不合理的地方。在[ABKH]圈中，添进弧线的总长度，显然大于该圈长度的一半！

对于添加进去弧线的总长度大于圈长一半的情形，有一种简单易行的调整办法，可以使得添加弧线的总长度小于半圈长。这种方法读者只要看一看下图，便会明了：

即在该圈中，撤去原先添加的弧线，改为添加原先没有添加的部分。这样做，网络所有顶点的奇偶性都没有改变，但却使总弧线的长度减小的，其道理是显而易见的！现在回到前面的例子上来。按上面的办法调整后可得下图。此时，相应的投邮路线为：

K（★）→J→K→H→G→F→E→D→C→B→A

→I→H→I→J→B→J→D→E→K（★）。

投邮路线的总长容易算得为 132 个单位，比原先净少了 8 个单位。读者不难看出，所得的新的网络（下图）已经符合前面提到的（甲）、（乙）两条原则，因而相应投邮线路已是最为合理的了！

邮递线路问题的解决，是奇偶点原理与图上作业法的科学结合，是数学知识古为今用的典范。以下生动的口诀，将帮助你记住这一有用的方法：“先分奇偶点，奇点对对联；联线不重叠，重叠要改变；圈上联线长，不得过半圈。”