甲从 A 出发，乙 从 B 出发，两人都要走遍所有的街道，最后到达 C ，谁的路径更短？

ccmmjj

甲乙两个邮递员去送信如图，两人同时出发同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？

chaoshikong

B先到，因为B只需要围着外面走一圈，加B-C这一截，而A要比B多走一截。。。

ccmmjj

chaoshikong 发表于 2020-6-9 12:33
B先到，因为B只需要围着外面走一圈，加B-C这一截，而A要比B多走一截。。。

好象不是这样讨论的。

luyuanhong

题  甲从 A 出发，乙 从 B 出发，两人都要走遍所有的街道，最后到达 C ，谁的路径更短？

解  在图中，只有 A 和 C 是“奇结点”（即向外伸出的路径条数为奇数的结点），其他结点

都是“偶结点”（即向外伸出的路径条数为偶数的结点）。

    根据“一笔画”原理，在一个连通图中，如果只有两个奇结点，其他都是偶结点，则必

存在一条以两个奇结点为起点和终点的“一笔画”路径，即无重复地走遍所有道路的路径。

在这样的图中，如果是从偶结点出发，则不可能找到一条无重复地走遍所有道路的路径。

    在本题中，甲从奇结点 A 出发，走到奇结点 C ，可以无重复地走遍所有的道路。而乙

从偶结点 B 出发，不可能无重复地走遍所有道路，乙要走遍所有道路，就不可避免地要走

一些重复路。所以，乙走过的路径，一定要比甲走过的路径更长。