所谓数学解题中的套路，应该是针对某一类具有相同模式的问题的解法。学习一种方法，可以解决一类问题，这本应是正道。可为什么现在套路成为贬义词，被大家所诟病呢？大家所不齿的套路真的就一无是处吗？且听我慢慢道来。
最近正好在备下学期离散数学的课，看到图论这部分时，联想到了之前公号里提到过的一个问题。
在一片大海上，有许多藏有金币的小岛，一些桥连接了这些小岛（如下图），每通过一座小岛，就可以收获相应数量的金币（每个小岛上的金币数量已经标记），从起点到终点，每座桥最多只能走一次，小朋友试着走一走，最后把每座经过的小岛上的金币数量加起来，算一算，最多能收获多少个金币？
有些人看到这样的图，就不假思索把它对应到一笔画问题。显然，这属于张冠李戴。不幸的是，这恰恰是不少人学了套路的结果。
在数学里确实有不少长得挺像的问题，欧拉图和哈密尔顿图就算一对。
一笔画问题在图论里被称作欧拉图，由七桥问题发展而来，在我之前的文章《数学在哪里（上）》里有解释。欧拉回路（或欧拉通路）要经过一个图里所有的边一次且仅一次，但对于点经过多少次并没有限制。
而哈密尔顿回路（或通路）则是经过图中每个顶点一次且仅一次。存在哈密尔顿回路的图被称为哈密尔顿图。
在上面的这个问题里，由于金币并不在桥上，而是在岛上，所以显然不用经过所有的边（即桥），因此不是欧拉路径问题。
由于金币在岛上，因此，上面的问题如果能经过所有的点，那就最好。从这个意义上讲，有点哈密尔顿图的味道。
之前，我给的解析如下：
如果我们按下图方式用0、1对所有节点进行间隔标号，那起点标号为0，终点标号也为0。在这个图中，标号为0和1的节点分别有8个。由于0-1间隔标号，走过的路一定呈现0-1-0-1-0-1-...的排列，要遍历所有节点（8个0，8个1），最后一个应该是1才对，因此无法遍历。所以，至少要去掉1个节点才行。
我们发现，如果去掉有3个金币的岛，那么左上角的点将成为度数为1的悬挂点，因此不行。而如果去掉4个金币的岛，则是可以的，具体的走法如下图：
但当我今天再次回顾这个问题时，我发现了一个大问题：题目中只限制每座桥走一次，但没有限制每座岛只能走一次！因此，这个与哈密尔顿通路完全是两码事！
去掉了这个限制以后，我们很容易可以找到一条如下图所示的从起点到终点经过所有小岛的通路。在这条通路中，有9个金币的小岛被经过了两次。所以，这个问题的正确答案应该就是把所有岛上的金币数加起来，为133个金币，而不是129个。
一想到以前写的东西可能出现原理性错误，心里就觉得有点慌，生怕耽误了读者。
我赶紧回过头去又看了一下之前的那篇文章。好在，那篇文章的出题人已经手动把桥改成岛了，也就是当时的解析其实没错，是我事后记错了，万幸！
问题讲完了，我们可以回答一下开头的问题：套路，该怎么学？
学套路本身不可耻！而且，解题套路是我们学习过程中该提倡的。会求1 2 3 ... 100的和，难道不应该推而广之，学会求1 2 3 ... 1000和1 3 5 ... 99的和吗？
小孩子记忆力强，塞给他们一个方法，他们很快就能记住并加以简单运用。
那么套路学习中最大的障碍在哪里呢？其实在于问题的辨识和分类。看上去长得差不多的问题，有可能完全属于两类不同的问题。
因此，套路学习的第一要务，在于搞清楚套路方法所适用的前提。碰到具体问题，要分析问题的条件，看适用哪一种方法。而这一点，恰恰是现在的教学过程中所欠缺的。
那到底该怎么学套路？
我建议在教与学的过程中，可以多搞一些相似问题辨析，就像这篇文章的案例一样。这样才能加深大家对方法适用性的认知，从而把对套路的记忆转变为对套路的理解。
最后，就欧拉图和哈密尔顿图多说两句。
一个连通图是否存在欧拉回路（通路）很好判断，只要看这个图的节点度数即可。
- 如果这个图的所有节点度数都是偶数，那么存在欧拉回路
- 如果这个图只有两个奇点，那么存在欧拉通路，且这两个奇点即为欧拉通路的起点和终点；
- 如果这个图有多余两个奇点，则不存在欧拉通路。
相比较而言，一个图是否是哈密尔顿图则难判断得多。到目前为止，除了定义之外，人们还没有找到判断一个图是否存在哈密尔顿回路或通路的充分必要条件。
有这么一个充分条件：对于一个有n（n≥3）个节点的图G，如果任何两个不相邻顶点的度数之和都大于等于n，则G是哈密尔顿图。
然而，基本没啥大用，一方面复杂度比较高，另一方面既然只是充分条件，也就说存在一些图是哈密尔顿图，但不满足这个条件，比如一个六边形。
作者简介：昍(xuan)爸，中科院计算机博士，现为211大学计算机专业教授。曾获初中和高中全国数学奥林匹克联赛一等奖，江苏赛区第一名，高考数学满分。平时注重在生活中引导孩子进行数学思考，开设有公众号xuanbamath，著有《给孩子的数学思维课》一书。
,
