独立原创静态材料。先做本页;下一页为成人参考,发放前分开。在下方记录你的判断、运算或操作;需要时画箭头说明理由。
从起点S走到终点T,每条标长边都可双向走,不重复经过站点,走到T即结束。列全所有这类路径并逐段相加(单位米)。分别求最少路段数与最短总长度,给出对应路径及两栏证明;图不按比例绘制。
| 序号 | 站点序列 | 边长串 | 段数 | 总米数 |
|---|---|---|---|---|
| 1 | ____ | ____ | ____ | ____ |
| 2 | ____ | ____ | ____ | ____ |
| 3 | ____ | ____ | ____ | ____ |
| 4 | ____ | ____ | ____ | ____ |
最少段数与对应路径:________________。为什么不可能更少?
最短总长与对应路径:________________。怎样与全部候选比较?
本页含答案,不与学生页混发。图非按比例;不以画线长度判断距离。
| 路径 | 边长串 | 段数 | 米 |
|---|---|---|---|
| ['S', 'A', 'T'] | 6+6 | 2 | 12 |
| ['S', 'A', 'C', 'T'] | 6+8+4 | 3 | 18 |
| ['S', 'B', 'C', 'T'] | 2+3+4 | 3 | 9 |
| ['S', 'B', 'C', 'A', 'T'] | 2+3+8+6 | 4 | 19 |
最少段S-A-T;最短S-B-C-T。
| 目标 | 证明 |
|---|---|
| 最少段数 | 没有S到T的直接边,所以至少2段;S-A-T有2段,达到下界。 |
| 最短总长 | 四条完整简单路径总长依次为12、18、9、19米,最小9米,路线S-B-C-T。 |
路线长度表以无向边记录,走C到A仍用八米,不因方向反转就换一个数。全路径清单共有四条,列举时从起点的两个邻点分支展开,到终点立即停止;若继续离开终点绕回,会把已经完成的路线变成重复站点,超出约定。