最短路线（二）

　　在我们现实生活中人人都会经常遇到这样的问题：在去某地时应该选择一条什么样的路线使得行程最短，这个问题仍是数学中的最短路线问题．

　　例1 一个邮递员投送信件的街道如图141，图上数字表示各段街道的千米数．他从邮局出发，要走遍各街道，最后回到邮局．问走什么样的路线最合理，全程要走多少千米？

　　分析：最合理的路线就是选择最短路线．图中有很多路线，到底走哪一条路线最短呢？自然是能不重复走遍所有街道，最后回到邮局．因此这个问题就变成能否一笔画出这个图形，最后回到起点的“一笔画”问题．所谓一笔画，就是从图形上的某点出发，笔不离开纸，而且每条线都只画一次不准重复．

　　我们把一个图形中与偶数条线相连接的点叫做偶点，把与奇数条线相连接的点叫做奇点．图141中a、b、g、i都是偶点，其余的点均为奇点．

　　早在公元1736年，著名的大数学家欧拉发现了一笔画的原理：

　　（1）能一笔画出的图形必须是连通的（图形的各部分之间是连成一体的）；

　　（2）凡是全由偶点组成的连通图形，一定可以一笔画出，画时可以以任何一点为起点，最后仍回到这点；

　　（3）凡是只有两个奇点的连通图形一定可以一笔画出，画时必须以其中的一个奇点为起点，以另一个奇点为终点；

　　（4）奇点个数超过两个的图形不能一笔画出．

　　根据一笔画原理，可以判断出图141不是一笔画图形，因为这个图形奇点的个数超过两个．显然这个图形不能一笔画出，但我们可以将这个图形转化成一笔画图形．此题要求邮递员从邮局出发，最后回到邮局．按一笔画的原理，只有图形中的点全部是偶点时，才能从起点出发，最后又回到起点．图141中共有10个奇点，显然邮递员要不重复走遍所有的街道是不可能的．为使邮递员从邮局出发，最后仍回到邮局，必须使10个奇点都变为偶点，这就需要在每两个奇点之间添加一条线，使全部的奇点变为偶点．在实际问题中，就是邮递员在哪些街道上要重复走，由于各段街道的路程不同，究竟邮递员在哪些街道重复走，能使投邮路线最合理．当然必是重复走的路程最短，总路程才能最短．要达到这一点，连线时必须做到以下两点：

　　（1）连线不能出现重迭；

　　（2）在每一个首尾相接的封闭图上，连线的长度总和不能超过总封闭图的长的一半．

　　按照上面两点，这个题最佳连线如图142所示虚线．

　　解：根据图142，将10个奇点全变为偶点，且相应的投递路线为：

　　b（邮局）→n→a→i→h→j→f→g→h→j→k→e→f→e→d→l→k→l→m→n→m→c→d→c→b．

　　这条路线最合理（走法不唯一），全程长为：

　　（1+0.5+2+1+0.5）×4+2×6+1×2=34（千米）

　　例2 图143是一个城市道路图，数字表示各段路的路程（单位：千米），求出图中从a到f的最短路程．

　　分析：从图中可以看出，从a到f有许多条路，要确定一条最短的路线，可以采用排除的方法，逐步去掉比较长的道路，最后确定一条由a到f的最短路线．根据图中给出的路程的长度，有些明显较长的路可以不去考虑．从a出发到f，有三条路线相对较短，沿aihgf路线走，它的长度是：7+1+5+4=17；沿ajkgf路线走，它的长度是：4+3+5+4=16；沿abef路线走，它的长度是：5+7+6=18；比较结果得出最短路线．

　　解：由a到f的最短路线为：a→j→k→g→f，路线的长为：4+3+5+4=16（千米）

　　例3 某乡有八个行政村，如图144，点表示村的位置，线表示村与村之间的道路，路的长度由线旁的数字表示．现在要在这个乡建立通讯网，沿道路架设电线，问沿怎样的路线架设电线最省（单位：千米）？

　　分析：要在八个村架设电线形成通讯网，这个线路必须是连通的，这样才能形成网络．由于题目要求确定的路线最省，当然应该是电线的总长度尽可能短．如果采用圈形网络会出现若干个闭路，造成电线的浪费，所以采用树形网络可以达到节省电线的目的．图144是乡村分布图，它是一个圈形网络，可以将它转化成树形网络．为了使所得到的树形网络中的曲线（架线时所用电线）尽可能短，可以将圈形网络中较长的线剪掉，这种方法叫剪圈法．在agefa这个封闭圈中，af最长，把它剪掉．在abhga这个封闭圈中，ag最长，把它剪掉．在gheg这个封闭圈中，ge最长，把它剪掉．在ehde这个封闭圈中，hd最长，把它剪掉．在hdch这个封闭圈中，dc最长，把它剪掉．在hbch这个封闭圈中，bc最长，把它剪掉．这样把原题圈形网络转化成了树形网络图，且这个网络图的总长度最短．

　　解：根据剪圈法将圈形网络图144转化成了树形网络图145，此网络的总长度为：

　　13+12+4+6+16+8=69（千米）

　　由于通讯线路是双线，所以电线的总长度为

　　69×2=138（千米）．

　　例4 仍取图144中八个行政村的位置和线路图，乡政府要在全乡沿村与村之间的道路挖渠修道，建立排灌系统．全乡的地势是西高东低，即a村最高，依次为b、f、g、h、e、c、d，水源在a村，问沿什么路线修道最合理？

　　分析：由题意，要确定一条合理的挖渠路线，而且要省工省料，并符合“水往低处流”的客观规律．由于所修水渠是连通的，渠道可以看作是网络，而且也是树形网络．只是在本题中增加了“地势不同”这一条件，所以，力求树形网络总长尽可能短的情况下，所求的树形网络的方向应该是由西向东，以a为起点，以距离a最远的d为终点．

　　采