所謂數學解題中的套路，應該是針對某一類具有相同模式的問題的解法。學習一種方法，可以解決一類問題，這本應是正道。可為什麼現在套路成為貶義詞，被大家所诟病呢？大家所不齒的套路真的就一無是處嗎？且聽我慢慢道來。

最近正好在備下學期離散數學的課，看到圖論這部分時，聯想到了之前公号裡提到過的一個問題。

在一片大海上，有許多藏有金币的小島，一些橋連接了這些小島（如下圖），每通過一座小島，就可以收獲相應數量的金币（每個小島上的金币數量已經标記），從起點到終點，每座橋最多隻能走一次，小朋友試着走一走，最後把每座經過的小島上的金币數量加起來，算一算，最多能收獲多少個金币？

有些人看到這樣的圖，就不假思索把它對應到一筆畫問題。顯然，這屬于張冠李戴。不幸的是，這恰恰是不少人學了套路的結果。

在數學裡确實有不少長得挺像的問題，歐拉圖和哈密爾頓圖就算一對。

一筆畫問題在圖論裡被稱作歐拉圖，由七橋問題發展而來，在我之前的文章《數學在哪裡（上）》裡有解釋。歐拉回路（或歐拉通路）要經過一個圖裡所有的邊一次且僅一次，但對于點經過多少次并沒有限制。

而哈密爾頓回路（或通路）則是經過圖中每個頂點一次且僅一次。存在哈密爾頓回路的圖被稱為哈密爾頓圖。

在上面的這個問題裡，由于金币并不在橋上，而是在島上，所以顯然不用經過所有的邊（即橋），因此不是歐拉路徑問題。

由于金币在島上，因此，上面的問題如果能經過所有的點，那就最好。從這個意義上講，有點哈密爾頓圖的味道。

之前，我給的解析如下：

如果我們按下圖方式用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，著有《給孩子的數學思維課》一書。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!