相邻两厅之间有门相通,并且设有入口.请问你能否从入口进入一次不重复地穿过所有的门. 如果可以, 请指明穿行路线, 如果不能, 应关闭哪个门就可以办到? 【解析】可以将图中的五个小厅以及厅外的部分都抽象成点,为方便解题,给它们分别编号.这时,连通厅与厅之间的门就相当于各点之间的连线.于是题目中餐厅的平面图就抽象成为一个连通的图形,求穿形路线的问题就转化成一笔画的问题.在抽象出的图形中,我们可以找到四个奇点,即①、④、③和厅外,所以图形不能一笔画出也就是说,从入口进入不可能一次不重复的穿过所有的门.但根据一笔画问题的知识,只要关闭门,把③、④变为偶点,就可以办到,可行路线如下图: B 【例 16】在3×3 的方阵中每个小正方形的边长都是 100 米.小明沿线段从 A 点到 B 点,不许走重复路, 他最多能走多少米? 【解析】这道题大多数同学都采用试画的方法, 实际上可以用一笔画原理求解. 首先, 图中有 8 个奇点,在8 个奇点之间至少要去掉 4 条线段, 才能使这 8 个奇点变成偶点; 其次,从A 点出发到 B点,A,B两点必须是奇点, 现在 A,B 都是偶点, 必须在与 A,B 连接的线段中各去掉 1 条线段,使A,B 成为奇点.所以至少要去掉 6 条线段,也就是最多能走 1800 米,走法如图. 【例 17】一个邮递员投递信件要走的街道如右图所示,图中的数字表示各条街道的千米数,他从邮局出发, 要走遍各街道,最后回到邮局.怎样走才能使所走的行程最短?全程多少千米? 【解析】图中共有 8 个奇点,必须在 8 个奇点间添加 4 条线,才能消除所有奇点,成为能从邮局出发最后返回邮局的一笔画. 在距离最近的两个奇点间添加一条连线, 如左下图中虚线所示, 共添加 4 条连线, 这4 条连线表示要重复走的路,显然,这样重复走的路程最短,全程 30 千米.走法参考右下图(走法不唯一).
全文预览
