第六十三章 省賽開考！哈密頓圖！(第2/2 頁)

，他的大腦嗡嗡作響，感覺就像生了鏽般，思維能力不及平時的七成，而且身體畏寒感越來越強，雙手也越來越冷。

秦克努力地保持著大腦的清醒，但知道自己感冒在加重，目前的狀態維持不了多久，多半會隨著時間而不斷變得更糟糕，必須抓緊時間答題了。

他翻了翻正卷和附加捲，一如老鄭所言，正卷是十道大題，每道20分，附加捲是兩道大題，每道50分。

秦克在開考前趴桌那會兒已定下了考試策略，那就是趁著目前狀態還算可以，先解決掉最難的國賽難度的兩道附加題，再去做省賽正卷的題目，哪怕到時狀態變得更差點，應該也能勉強應付得來。

他甩甩腦袋，先集中精神看向第一道附加題。

“附加題一：平面上n個點和若干條邊所成的圖不是哈密頓圖，但若任意去掉一點及與之相連的邊，則剩下的圖為哈密頓圖，求n的最小值。”

秦克倒抽了口涼氣，不愧是國賽難度，上來就是哈密頓圖。

哈密頓這個名字，估計全國九成九的高中生都沒留意過。

哈密頓是十八世紀的英國著名數學家，當年他提出一個名為“環遊世界”的遊戲，用一個正十二面體的二十個頂點代表二十個大城市，要求沿著稜，從一個城市出發，只經過每個城市一次，然後回到出發點，這就是著名的“哈密頓問題”。

後來數學界將“經過圖上各頂點一次並且僅僅一次的圈”稱之為“哈密頓圈”，一個圖如果包含哈密頓圈，那這個圖就可以被稱為“哈密頓圖”。

從表面上來看，這個哈密頓問題似乎與尤拉的哥尼斯堡七橋問題（哥尼斯堡七橋問題是指，河中有兩個島，河上有七座橋連線這兩個島及河的兩岸，請問能否透過每座橋一次且僅一次。它也被稱為“一筆畫”問題）非常相似，但兩者有著本質的區別。

哥尼斯堡七橋問題已被尤拉自己解決了，並由此開創了數學的新分支——“圖論”。

哈密頓問題卻迄今為止都未曾解決，一百多年來無數一流的數學家費盡心思，也沒找到判斷它的充分必要條件，只是提出了一些已被證實的必要條件和充分條件，應用到不同的場合。

這道題目難就難在不但要求解題人瞭解哈密頓圖的特點和那些已被證實的必要條件和充分條件，更要能靈活運用。

秦克一看到這題目，就知道寧青筠答不出來——因為時間有限，有關哈密頓圖他只是給寧青筠講解過兩道例題，並不算深入，以寧青筠對哈密頓圖的理解，不可能答得出來。

不只是寧青筠，估計整個考場，除了他也沒第二個人能答出來。

秦克揉揉有點發脹的太陽穴，沉思了三分多鐘，才開始動筆：

“解：首先每個點的度至少為3，不然存在一點A僅連出至多兩邊，則把其中一邊去掉後，剩下的A點必不在某個圈上，這與條件不符，因此可以得出，n≥3……”

“當n=4時……”

“……”

“當n=10時，條件才成立，所以本題的答案為10，具體圖示如下：”

秦克畫了一個正五邊形，中間是個“一筆畫”的五角星形，五星形的各個頂點再與包圍它的五邊形頂點相連。

這就是n=10的時候，最符合題意的圖，任意去掉一點及與之相連的邊，剩下的圖為哈密頓圖。

解答過程寫了整整大半頁紙，幾乎將答題區域寫滿。