哥尼斯堡七橋問題與一筆畫

請你做下面的游戲：一筆畫出圖1的圖形來.規則：筆不離開紙，每根線都只能畫一次.你能畫出來嗎？

如果你畫出來了，那么請你再看圖2能不能一筆畫出來？

雖然你動了腦筋，但我相信你肯定不能一筆畫出圖2！這就是一筆畫問題，它是一種有名的數學游戲.

所謂一筆畫指的是：從圖的一點出發，筆不離紙，遍歷每條邊恰好一次，即每條邊都只畫一次，不準重復.從圖1中容易看出：能一筆畫出的圖首先必須是連通圖.但是否所有的連通圖都可以一筆畫出呢？

有關這個問題的討論，要追溯到兩百多年前的一個著名問題——哥尼斯堡七橋問題.十八世紀，東普魯士哥尼斯堡城（今俄羅斯加里寧格勒）有一條河叫普萊格爾河，它有兩個支流，在城市的中心匯成大河，中間是島區，河上有7座橋，將河中的兩個島和河岸連接，如圖3所示.由于島上有古老的哥尼斯堡大學，有教堂，還有哲學家康德的墓地和塑像，因此城中的居民經常沿河過橋散步.漸漸地，愛動腦筋的人們提出了一個問題：一個散步者能否一次走遍7座橋，而且每座橋只許通過一次，最后仍回到起始地點？這就是哥尼斯堡七橋問題，一個著名的圖論問題.

這個問題看起來似乎并不難，但人們始終沒有能找到答案.最后，問題被提到了大數學家歐拉那里.歐拉以深邃的洞察力很快證明了這樣的走法是不存在的.歐拉是這樣解決問題的：既然陸地是橋梁的連接點，不妨把圖中被河隔開的陸地看成4個點，將7座橋看成7條連接這4個點的線，如圖4所示.

于是“七橋問題”就等同于圖5中所畫圖形的一筆畫問題了.歐拉注意到，如果一個圖能一筆畫成，那么一定是由一個起點開始畫，也有一個終點.圖上其它的點是“過路點”——畫的時候要經過它.現在看“過路點”具有什么性質.它應該是“有進有出”的點，有一條邊進這點，那么就要有一條邊出這點.不可能是有進無出，如果有進無出，它就是終點；也不可能有出無進，如果有出無進，它就是起點.因此，在“過路點”進出的邊的總數應該是偶數，即“過路點”是偶點.

于是，我們把一個圖形中與偶數條線相連接的點叫做偶點.相應地，把與奇數條線相連接的點叫做奇點.一個圖形能否一筆畫成就有了一個判別準則： （1）能一筆畫出的圖形必須是連通的圖形；（2）凡是只由偶點組成的連通圖形，一定可以一筆畫出.畫時可以由任一偶點為起點.最后仍回到這點；（3）凡是只有兩個奇點的連通圖形一定可以一筆畫出，畫時必須以一個奇點為起點，以另一個奇點為終點；（4）奇點個數超過兩個的圖形，一定不能一筆畫出.

現在對照七橋問題的圖，所有的頂點都是奇點，共有四個，所以這個圖肯定不能一筆畫成.歐拉對“七橋問題”的研究是圖論研究的開始，同時也為拓撲學的研究提供了一個初級例子.

【例題賞析】

例1 下圖6不能一筆畫成，請你在下圖中添加最少的線段，將其改成一筆畫的圖形，并畫出路線圖.

解析：不能一筆畫出，因為圖中有E H G F四個奇點，連接EH就可以將圖形一筆畫出.

例2 上圖7中的線段表示小路，請你仔細觀察，認真思考，能夠不重復爬遍小路的是甲螞蟻還是乙螞蟻？該怎樣爬？

解析：要想不重復爬，需要能將圖形一筆畫出.由于圖中有兩個奇點，所以應該從奇點出發才能一筆畫出圖形，所以甲螞蟻能夠.

例3 如圖8郵遞員叔叔向11個地點送信，如不想走重復路，怎樣走最合適？

解析：不走重復路，一筆能畫出路線圖，圖中有2個奇點，應該從奇點處出發.下面有一種參考路線：4-1-2-5-8-9-6-10-11-7-4-3.

【智力比拼】

1.下面的圖形都不能一筆畫成，你能否在圖中添上一條線段，使它能一筆畫成.

2.下圖是兒童樂園的道路平面圖，要使游客走遍每條路并且不重復路線，那么出、入口應設在哪里？

3.下圖是國際奧林匹克運動會的會標，能一筆畫成嗎？如果能，請你把它畫出來.