haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

11最短路线问题

发布时间:2013-12-16 09:32:45  

12年春思维特训-11讲

最短路线问题 例题

我们把不能一笔画成的图,归纳为多笔画.首先,我们来考虑一个不能一笔画成的图,至少用几笔才能画完呢?(为了研究的方便,我们仍然只研究连通图,非连通图可转化为连通图.)

观察下面的图形,并列出奇点的个数与最少笔画数的关系表格。

奇点个数与笔画数的关系可列表如下:

得出结论:事实上,对于任意的连通图来说,笔画数恰等于奇点个数的一半;

1.

下图是某少年宫的平面图,共有五个大厅,相邻两厅之间都有门相通(D与

E两厅除外),并且有

一个入口和一个出口.

游人能否从入口入,一次不重复地穿过所有的门

呢,如果可以,请指明穿行路线;如果不能,请你想一想,关闭哪扇

门后就可以办到;

C D E

F

2. 下图中的线段表示的是汽车所能经过的所有马路,这辆汽车从A走到B

处共

有_____条最短路线;

B

3. 下图是一个街道的平面图,纵横各有5条路, 某人从A到B,按最短

路线走,共有_______种不同的走法;

4. 如图4

—6,从甲地到乙地最近的道路有______条;

5. 如图,按照向右或向上沿着方格线从A点走到B点,其中C点不能通过,共

有________种不同的走法;

6. 按图中箭头所示的方向行走,从A点走到B点的不同路线一共有_______条;

B

A

12年春思维特训-11讲

最短路线问题 课后练习

1. 下图是某个花房的平面图,它由六间展室组成,每相邻两室间有

F G E 一门相通.请你设计一个出口,使参观者能够从入口处A进去,一

次不重复地经过所有的门,最后由出口走出花房。

C D

B

2. 如果沿图4-11中的线段,以最短的路程,从A点出发到B点,共有_______种不同的走法;

A

3. 从A到B的最短路线有________条;

A

4. 按照向右或向上沿着图中的方格线从A走到B,有_____种走法;

B

5. 如图是一个从A到B的公路网络,现在画粗线的道路正在进行施工无法通行,

那么从A到B的最短路线一共有______条;

A

6. 右图是某地区街道的平面图,图上的数字表示那条街道的长度。清晨,洒水车从A出发,要洒遍

所有的街道,最后再回到A。问:如何设计洒水路线最合理?

B 7

D

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com