手机百度网盘设置同步:最短路线（二）-小学数学网-学而思教育

例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为终点．

　　采取“取短法”，所谓取短法就是剪去长线，留取短线．并根据方向的限制，从地势最低点开始考虑（也可从其它点入手考虑）．D的临近点有E、H、C，它们都比D地势高，所以，这三点处的水都可以流入D，则只需取一条最短的即可，ED=16最短，留ED，将HD、CD去掉．

　　再看C点，有两条通道HC、BC（这里所说的通道是指地势高的点通向地势低的点的道路），HC比BC短，去掉BC，保留HC．E点有三条通道FE、GE、HE，其中HE最短，保留HE，去掉FE、GE．H点有两条通道BH、GH，其中GH最短，保留GH，去掉BH，最后剩下地势较高的三点B、F、G，它们与A都各有一条通道，不存在取舍问题，这样得到， 挖渠的最佳方案．

解：利用取短法并根据方向的限制，得到图146所示的挖渠的最佳方案．

　　17+15+13+4+7+6+16=78（千米）

例5 有八栋居民楼A₁、A₂、…、A₈分布在公路的两侧，如图147，由一些小路与公路相连，要在公路上设一个汽车站，使汽车站到各居民楼的距离之和最小，车站应设在哪里？

分析：住A₁楼的居民总要走到B，A₂楼的居民总要走到C，A₃、A₄楼的居民总要走到D，……，这些小路总要走，与车站建在哪无关，故问题可以简化成B、C、D、E、F、G处分别站着1人、1人、2人、1人、2人、1人，这些人用点的个数来表示，如图148，求一点使所有人走到这一点的距离和最小．当点数为奇数时，应设在中间点上，当点数为偶数时，应设在中间相邻的两点或这两点之间的任何地方，这样的距离和为最短．

解：将图147可以简化成图148，由于点的个数是偶数，所以应将车站设在D或E或DE之间的任何一点．