广州地铁数学题
前不久我在校内贴了这么一个数学思考题：
设计一条最短的路线，使得你能不重复地在目前广州地铁的全部换乘站都换乘过，且最终回到起点站。
题目的具体要求：
1. 每个换乘站能且只能换乘一次（即题中所指的“不重复换乘”）；
2. 乘坐地铁经过换乘站而不下车换乘，不能算作“换乘过”；
3. “换乘”的具体定义是换线，即从A号线换乘到B号线；
4. 允许重复经过站点；
5. 按途经的站点数计算路程距离，不包括起点站，包括终点站；
6. 给出路线的起点站可任意设置。
附广州地铁（至五号线运营）线路图（图1）
图1
最初我想出了35站的路线，以为是最短路程了，后来，宋云龙同学给出了33站的路线，这看来确实是少得不能再少了。下面是我对两个答案的一些思考。
题干的重点有三个：1. 最终回到起点站，这意味着设计出来的路线必须是环状的；2. 不重复换乘，这就是说一个换乘过的换乘站不能回头再次换乘，即意味着路线是单向的；3. 最短的，这意味着重复经过的普通站点要尽可能减到最少。
基于环状、单向、重复量最小化的原则，我们知道了路线的起点不能在地铁线路环外的站点上。因此我们可以将路线经过站点的范围缩小到地铁线路环内（图2）。
图2
接下来需要更深一层的理解了。由于学科的关系，我极少接触图论的知识，因此我没能轻易搞明白twitter上朋友说的“哈密顿图”解法。我只能依靠旧有的一点“一笔画”知识和一些常识来枚举路线了。
考虑到从西到东或从东到西的路线的站点重复量，理应要比从中间到一边然后又经过中间到另一边的路线要少，因此我一开始就随手选择了小北站作为起点。
（起点）（5号线）小北 – 广州火车站（转2）- 公园前（转1）- 杨箕（转5）- 珠江新城（转3）- 体育西路（转1）- 广州东站（转3）- 客村（转2）- 万胜围（转4）- 车陂南（转5）- 小北（终点），共35站（如图3）。
图3
因为设计出来符合要求的路线必定呈环状，因此在路线内起点可以随意选择，而且出发方向也是没有限制的。所以，我们可以在图3内以任意一个非换乘站为起点，在上述路线内以正反方向行走。
后来，宋云龙同学给出一条更短的33站的路线：
（起点）（3号线）林和西- 广州东站（转1）- 公元前（转2）- 广州火车站（转5）- 杨箕（转1）- 体育西路（转3）- 珠江新城（转5）- 车陂南（转4）- 万盛围（转2）- 客村（转3）- 林和西（终点），共33站（如图4）。
图4
这条路线精妙之处在于不经过五羊邨站，从而使得西北部（广州火车站-公园前-杨箕）、北部（广州东站-体育西路）、东部（珠江新城-客村-万胜围-车陂南）三个独立地铁圈的形象异常清晰。而串联起这三个地铁圈的杨箕、体育西路、珠江新城这至关重要的三站，重复途经它们就成了必然的需要。
现在问题的关键是如何证明宋同学的“33站”路线就是符合题目要求的路线中最短的。还是说，正在阅读这篇文章的你，脑海闪过一丝灵感，发现“33站”才不是最短的路线？
我猜你还会喜欢看：
我也没学图论，只是了解期货相关知识时接触过“二叉树”模型。
前来围观一下答案先！
哎呀~~我那次又理解错题意了。
我以为每个中转站之间的那段必须要经过呢~~~
后来我再想时，发现中间就是有段没法经过，就放弃了。
原来也可以不经过吖~~~
看来做题前没审题的后果就是不妙！