《小学数学奥数习题讲义《最短路线问题》》由会员分享，可在线阅读，更多相关《小学数学奥数习题讲义《最短路线问题》（5页珍藏版）》请在金锄头文库上搜索。
1、1在日常生活、工作中,经常会遇到有关行程路线的问题.比如：邮递员送信,要穿遍所有的街道,为了少走冤枉路,需要选择一条最短的路线;旅行者希望寻求最佳旅行路线,以求能够走最近的路而达到目的地,等等.这样的问题,就是我们所要研究学习的“最短路线问题”.典型例题例1 假如直线 AB 是一条公路,公路两旁有甲乙两个村子,如下图 1.现在要在公路上修建一个公共汽车站,让这两个村子的人到汽车站的路线之和最短.问：车站应该建在什么地方?分析 如果只考虑甲村的人距离公路 AB 最近,只要由甲村向公路 AB 画一条垂直线,交 AB 于 C 点,那么 C 点是甲村到公路 AB 最近AB甲村甲村乙村乙村AB甲村甲村乙
2、村乙村图图1图图2最短路线2的点,但是乙村到 C 点就较远了.反过来,由乙村向公路 AB 画垂线,交 AB 于 D 点,那么 D 点是乙村到公路 AB 最近的点.但是这时甲村到公路 AB 的 D 点又远了.因为本题要求我们在公路 AB 上取的建站点,能够兼顾甲村和乙村的人到这个车站来不走冤枉路（既路程之和最短）,根据我们的经验：两个地点之间走直线最近,所以,只要在甲村乙村间连一条直线,这条直线与公路 AB 交点 P,就是所求的公共汽车站的建站点了（图 2）.解 用直线把甲村、乙村连起来.因为甲村乙村在公路的两侧,所以这条连线必与公路 AB 有一个交点,设这个交点为 P,那么在 P 点建立汽车站
3、,就能使甲村乙村的人到汽车站所走的路程之和最短.例2 一个邮递员投送信件的街道如图 3 所示,图上数字表示各段街道的千米数.他从邮局出发,要走遍各街道,最后回到邮局.问：走什么样的路线最合理?全程要走多少千米?分析 选择最短的路线最合理.那么,什么路线最短呢?一笔画路线应该是最短的.邮递员从邮局出发,还要回到邮局,按一笔画问题,就1242133是从偶点出发,回到偶点.因此,要能一笔把路线画出来,必须途径的各点全是偶点.但是图中有 8 个奇点,显然邮递员要走遍所有街道而又不走重复的路是不可能的.要使邮递员从邮局出发,仍回到邮局,必须使8 个奇点都变成偶点,就是要考虑应在哪些街道上重复走,也就是相
4、当于在图上添哪些线段,能使奇点变成偶点.如果有不同的添法,就还要考虑哪一种添法能使总路程最短.为使 8 个奇点变成偶点,我们可以用图 4 的 4 种方法走重复的路线.图 4 中添虚线的地方,就是重复走的路线.重复走的路程分别为：（a）34=12（千米）（b）3222=10（千米）（c）24=8（千米）（d）3242=14（千米）124213124213124213124213( a ) ( b ) ( c ) ( d ) 图图44当然,重复走的路程最短,总路程就最短.从上面的计算不难找出最合理的路线了.解 邮递员应按图 4（c）所示的路线走,这条路重复的路程最短,所以最合理.全程为：（1242
5、1）23624=20188=46（千米）例3 图 5 中的线段表示的是小明从家到学校所能经过的所有街道.小明上学走路的方向都是向东或向南,因为他不想偏离学校的方向而走冤枉路.那么小明从家到学校可以有多少条不同的路线?分析 为了叙述的方便,我们在各交叉点标上字母（见图 6）.小明家学校北北小明家小明家ABFEFDEF5我们从小明家出发,顺序往前推.由于从小明家到 A、B、C、D 各处都是沿直线行走,所以都只有一种走法.我们分别在交叉点处标上“1”.而从小明家到 E 处,就有先到 A 或先到 D 的两种走法,正好是两个对角上标的数 1+1 的和.从小明家到 F 点,则有 3 条路线,又正好是两个对角上标的数 1+2 的和.标在各交叉点的数,就是依次顺序推出的到各交叉点能有多少种不同的路线的数.从中我们可以看出,每个格内上右角与下左角两个对角上的数的和,正好等于下右角上的数.解 从小明家到学校有 13 条不同的路线.如图 7 所示.图 7小明家学校北北1121314259134ABCDEFGHMNK小结 寻找最短路线,不应该走“回头路”.要按照一定的逻辑次序来排列可能路线,既要做到不重复数,也不漏数.对比较复杂的图形,可以借助图表来寻找路线.
