路线经过的站少就一定路程短吗:把每一段长度加起来

B034 · 学生页 姓名________ 日期________

独立原创静态材料。先做本页;下一页为成人参考,发放前分开。在下方记录你的判断、运算或操作;需要时画箭头说明理由。

从起点S走到终点T,每条标长边都可双向走,不重复经过站点,走到T即结束。列全所有这类路径并逐段相加(单位米)。分别求最少路段数与最短总长度,给出对应路径及两栏证明;图不按比例绘制。

662348SABCT
序号站点序列边长串段数总米数
1________________
2________________
3________________
4________________

分别证明

最少段数与对应路径:________________。为什么不可能更少?

最短总长与对应路径:________________。怎样与全部候选比较?

推导与订正记录

B034 成人参考页

本页含答案,不与学生页混发。图非按比例;不以画线长度判断距离。

路径边长串段数米
['S', 'A', 'T']6+6212
['S', 'A', 'C', 'T']6+8+4318
['S', 'B', 'C', 'T']2+3+439
['S', 'B', 'C', 'A', 'T']2+3+8+6419

最少段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仍用八米,不因方向反转就换一个数。全路径清单共有四条,列举时从起点的两个邻点分支展开,到终点立即停止;若继续离开终点绕回,会把已经完成的路线变成重复站点,超出约定。