七橋問題與一筆畫

18世紀時哥尼斯堡是位于普累格河上的一座風景秀麗的城市. 它今天屬于俄羅斯加里寧格勒，以前是東普魯士的土地. 哥尼斯堡有兩個島嶼，河的兩岸與兩島之間共建有七座橋（如圖1），島上有古老的哥尼斯堡大學，有教堂，還有哲學家康德的墓地和塑像. 因此，城中的居民，尤其是大學生們經常沿河過橋散步. 有一天，一個好奇的人提出了一個問題：一個散步者能否一次走遍7座橋，而且每座橋只許通過一次，最后仍回到起始地點. 問題提出后，很多人對此很感興趣，紛紛進行試驗，但在相當長的時間里，始終未能解決. 利用普通數學知識就可以知道，每座橋都走一次，那這七座橋所有的走法一共有5 040種，而這么多情況要一一試驗，將會是很大的工作量. 但是怎么才能找到成功走過每座橋而不重復的路線呢？這就是著名的“哥尼斯堡七橋問題”.

1735年，有幾名大學生寫信給當時正在俄羅斯彼得堡科學院任職的天才數學家歐拉，請他幫忙解決這一問題. 歐拉在親自觀察了哥尼斯堡七橋后，認真思考走法，但始終沒能成功，于是他懷疑七橋問題是不是原本就無解呢？

1736年，在經過一年的研究之后，29歲的歐拉提交了《哥尼斯堡七橋》的論文，圓滿解決了這一問題. 在論文中，歐拉將七橋問題抽象出來，把每一塊陸地考慮成一個點，連接兩塊陸地的橋以線表示，并由此得到了如圖2（a）這樣的幾何圖形. 若我們分別用A、B、C、D四個點表示哥尼斯堡的四個區域（如圖2（b）），這樣著名的“七橋問題”便轉化為是否能夠用一筆不重復地畫出此七條線的問題了. 歐拉的這個考慮非常重要，也非常巧妙，它正表明了數學家處理實際問題的獨特之處——把一個實際問題抽象成合適的“數學模型”. 這種研究方法就是“數學模型方法”. 這并不需要運用多么深奧的理論，但想到這一點，卻是解決難題的關鍵. 經歐拉研究發現，圖2不能一筆畫出. 也就是說找不到不重復地經過七座橋的路線. 多少年來，人們費腦費力尋找的那種不重復地路線，根本就不存在. 一個曾難住了那么多人的問題，竟是這么一個出人意料的答案！這是為什么呢？讓我們來看幾個一筆畫的問題.

先讓我們來了解三個新概念.

①有奇數條線相連的點叫奇點.（如圖3）

②有偶數條線相連的點叫偶點.（如圖4）

③一筆畫：下筆后筆尖不能離開紙，每條線都只能畫一次而不能重復.

圖5-圖8四個圖形中，你能找出圖5-圖8的每個圖形中奇點和偶點的個數嗎？請你試一試其中哪些可以一筆畫出？

【分析】圖5中有6個偶點：A、B、C、D、E、F，0個奇點，可以一筆畫成. 圖6中有4個偶點：A、B、D、F，2個奇點：C、E，可以一筆畫成. 圖7中有2個偶點：A、C，2個奇點：B、D，可以一筆畫成. 圖8中有1個偶點：O，4個奇點：A、B、C、D，不能一筆畫成. 再找幾個圖形試一試，你能發現什么規律嗎？

【規律】

①可以一筆畫成的圖形，與偶點個數無關，與奇點個數有關. 也就是說，凡是圖形中沒有奇點的（奇點個數為0），可選任一個點做起點，且一筆畫后可以回到出發點.

②若奇點個數為2，可選其中一個奇點做起點，而終點一定是另一個奇點，即一筆畫后不可以回到出發點.

在表示七橋問題的圖2（b）中，現在我們來數一數，奇點的個數有幾個？由此你明白七橋問題無解的道理了嗎？

由于七橋問題中的四個點都是奇點，因此可以判斷它是無法一筆畫出來的 ，也就是說根本不存在能不重復走遍七座橋的路線！

如果在七橋問題中，允許你再架一座橋，能否不重復地走遍這八座橋？這座橋應該架在哪里？請你試一試！

1. 一輛灑水車要給某城市的街道灑水，街道地圖如圖9，你能否設計一條灑水車灑水的路線，使灑水車不重復地走過所有的街道，再回到出發點？

2. 如圖10是一個公園的平面圖，能不能使游人走遍每一條路不重復？入口和出口又應設在哪兒？

3. 甲乙兩個郵遞員去送信，兩人同時出發以同樣的速度走遍所有的街道，甲從A點出發，乙從B點出發，最后都回到郵局（C點），如圖11. 如果要選擇最短的線路，誰先回到郵局？