最短路线(二)

 
  在我们现实生活中人人都会经常遇到这样的问题:在去某地时应该选择一条什么样的路线使得行程最短,这个问题仍是数学中的最短路线问题.
  例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为终点.
  采