小学奥数讲义最短路线专题

.最短路线的主题在日常生活和工作中，经常会遇到旅行相关的问题。 例如，邮递员必须选择最短的路线，以免穿过每条街道，走不正当的路线。旅行者希望找到最合适的路线，以便走最近的路线到达目的地，等等。 这类问题是我们必须研究的“最短路线问题”。典型例题例1假设直线AB为道路，道路两侧有甲乙两个村庄，则如下图1所示。 现在在道路上修建公共汽车站，使这两个村子的人到公共汽车站的路线和最短。 问：车站应该建在哪里？a.a乙组联赛甲村乙村a.a乙组联赛甲村乙村图1图2在分析中，只考虑甲村的人离道路AB最近的事情的话，从甲村到道路AB画垂直线，把AB和c点交叉的话，c点是从甲村到道路AB最近的点，但是从b村到c点很远。相反，从乙村向道路AB画垂线，把AB交给d点的话，d点是从乙村到道路AB最近的点。 但是，此时从甲村到道路AB的d点又远了。这个问题是，因为我们要求在道路AB上取得的网站，所以甲村和乙村的人能够同时不走无辜的道路(距离之和最短)，根据我们的经验，在两个地方之间直线最近，所以在甲村和乙村之间连接直线的话，这条直线和道路AB的交点p用解放线连接甲村乙村。 由于甲村乙村在道路的两侧，所以这个连接必定有和道路AB的交点，如果把这个交点作为p的话，通过在p点建立公共汽车站，可以使甲村乙村的人到公共汽车站的路程之和最短。例2邮递员投递信件的街道如图3所示，图中的数字表示各街道的公里数。 他从邮局出发，绕过各条街，最后返回邮局。 问：走什么路线最合理？全程多少公里？124213分析了选择最短的课程是最合理的。 那么，哪条路线最短呢？一画的路线必须最短。 邮递员从邮局出发，回到邮局，线的问题是从偶数点出发，回到偶数点。 因此，要想一条一条地画出路线，路线的各点都必须是偶数点。 但是，图中有8个特点，明确了邮递员要绕过所有的街道，不走重复的道路是不可能的。 为了让邮递员从邮局出发，回到邮局，8个特点都必须是偶数点。 也就是说，应该重复什么样的操作，也就是说相当于在图中追加哪条线段，必须考虑可以使奇点成为偶数点。 如果有不同的添加方法，还要考虑哪种添加方法可以使总路程最短。124213124213124213124213(a )(b )(c )(d )图4可以以图4的四种方式遵循重叠路线，以便使八个奇点成为偶数点。在图4中标注虚线是反复行走的路线。 重复走的路程分别是：(a) 34=12 (公里)(b) 32 22=10 (公里)(c) 24=8(公里)(d) 32 42=14 (公里)当然，重复行走的路程最短，总路程最短。 从以上计算中找到最合理的路线是不容易的。邮递员应该按图4(c )所示的路线去，这条路线重复的路程最短，所以最合理。 所有课程：(一二四二一)二三六二四=20 18 8=46 (公里)小明家学校北例3图5中的线段表示小明从家到学校能通过的所有街道。 小明不想偏离学校的方向，所以走的方向是东或南。 那么，小明从家到学校有多少条路线？分析是为了便于记述，在各个交叉路口标注了字母(参照图6 ).小明家a.a乙组联赛f.fef.fd.def.f我们从小明家出发，按顺序进行。 从小明家到a、b、c、d到处都是直线走，走的方法只有一个。 我们分别在十字路口打了个“1”。 从小明家到e处，有先到a或先到d两种走法，正好是对角写的数1之和。 从小明家到f点，有3条路线，正好是对角写的数1 2之和。在各个交叉点显示的数据是按顺序提示各个交叉点有多少不同的路线的数据。 由此可知，各格内的上右角和下左角对角上的数之和正好等于下右角上的数。小明家学校北1121314259134a.a乙组联赛c.cd.def.fghmnK解从小明家到学校有十三条不同的路线。