初中数学竞赛专题讲解最短路径问题.docxVIP

初中数学竞赛专题讲解最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查． 【十二个基本问题】 【问题 【问题 1】 作法 图形 原理 A A l 连 AB，与 l 交点即为 P． P l B 在直线 l 上求一点 PA+PB 值最小． 两点之间线段最短． PA+PB 最小值为 AB． P，使 B 【问题 2】“将军饮马” 作法 图形 原理 A A B l 作 B 关于 l 的对称点 B＇ 连 A B＇，与 l 交点即为 P． B 在直线 l 上求一点 PA+PB 值最小． 【问题 3】 P，使 P l 两点之间线段最短． PA+PB 最小值为 A B＇． B 作法 图形 原理 l1 P l 1 P l2 1 2 分别作点 P 关于两直线 的对称点 P＇和 P ＇，连 P＇ P ＇，与两直线交点即为 M， N． M P 在直线 l 、l 上分别求点 N l 两点之间线段最短． PM+MN+PN 的最小值为线段 P＇P＇的长． 2 M、N，使△PMN 的周长最 小． 【问题 4】 P 作法 图形 原理 l1 l1 Q Q 分别作点 Q 、P 关于直 P 线l 、l 的对称点 Q＇和 M Q l 2 在直线 l1 、l2 上分别求点 M、N，使四边形 PQMN 的 周长最小． 1 2 P＇连 Q＇P＇，与两直线交点 即为 M，N． P N l2 两点之间线段最短． 四边形 PQMN 周长的最小值为线段 P＇P＇的长． P - 1 - 【问题 5】“造桥选址” 作法 图形 原理 A M m 将点A 向下平移 MN 的长 N n 度单位得 A＇，连 A＇B，交 n B 于点 N，过 N 作 NM⊥ m  A A M  两点之间线段最短． m AM+MN+BN 的最小值为 n 直线 m ∥ n ，在m 、n ，上分别求点 M、N，使 MN⊥ m ，且 AM+MN+BN 的值最小． 于 M． N A＇B+MN． B 【问题 6】 作法 图形 原理 A M a N  将点A 向右平移 a 个长度 B l 单位得 A＇，作 A＇关于l 的对称点 A ＇，连 A ＇B，交 A A B l M N  两点之间线段最短． AM+MN+BN 的最小值为 在直线 l 上求两点 M、N（M 在左），使 MN ? a ，并使AM+MN+NB 的值最小． 直线 l 于点 N，将 N 点向 左平移 a 个单位得 M． A A ＇B+MN． 【问题 7】 作法 图形 原理 l l 1 1 P P 作点 P 关于 l 1 的对称点  P 点到直线，垂线段最短． 在 l 上求点 A，在l 1  l 2 上求点 2 P＇，作 P＇B⊥ l 2 于 A． 于 B，交l A 2 B PA+AB 的最小值为线段 P＇ l B的长． 2 B，使 PA+AB 值最小． 【问题 8】 l 1 N A 作法 图形 原理 B l l M B 2 作点 A 关于 l 2 的对称点 1 A N A N A 为 l 1 上一定点，B 为l 上 2 A＇，作点 B 关于 l 的对 1 称点 B＇，连 A＇B＇交l 于 2 M AM+MN+NB 的最小值为 l 线段 A＇B＇的长． 一定点，在 l 2 上求点 M， M，交 l 1 于 N． B 2 A 在 l 上 求 点 N ， 使 1 AM+MN+NB 的值最小． 【问题 9】 作法 A A lB 连 AB，作 AB 的中垂线与 l 图形 原理 垂直平分上的点到线段两 B 端点的距离相等． 在直线 l 上求一点 P，使PA ? PB 的值最小． 直线 l 的交点即为 P． P l PA ? PB ＝0． - 2 - 【问题 【问题 10】 作法 图形 原理 A 三角形任意两边之差小于 B A l 作直线 AB，与直线 l 的交 点即为 P． B 第三边． PA ? PB ≤AB． l 在直线 l 上