七橋問題與一筆畫

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

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

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

先讓我們來了解三個(gè)新概念.

①有奇數(shù)條線相連的點(diǎn)叫奇點(diǎn).（如圖3）

②有偶數(shù)條線相連的點(diǎn)叫偶點(diǎn).（如圖4）

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

圖5-圖8四個(gè)圖形中，你能找出圖5-圖8的每個(gè)圖形中奇點(diǎn)和偶點(diǎn)的個(gè)數(shù)嗎？請你試一試其中哪些可以一筆畫出？

【分析】圖5中有6個(gè)偶點(diǎn)：A、B、C、D、E、F，0個(gè)奇點(diǎn)，可以一筆畫成. 圖6中有4個(gè)偶點(diǎn)：A、B、D、F，2個(gè)奇點(diǎn)：C、E，可以一筆畫成. 圖7中有2個(gè)偶點(diǎn)：A、C，2個(gè)奇點(diǎn)：B、D，可以一筆畫成. 圖8中有1個(gè)偶點(diǎn)：O，4個(gè)奇點(diǎn)：A、B、C、D，不能一筆畫成. 再找?guī)讉€(gè)圖形試一試，你能發(fā)現(xiàn)什么規(guī)律嗎？

【規(guī)律】

①可以一筆畫成的圖形，與偶點(diǎn)個(gè)數(shù)無關(guān)，與奇點(diǎn)個(gè)數(shù)有關(guān). 也就是說，凡是圖形中沒有奇點(diǎn)的（奇點(diǎn)個(gè)數(shù)為0），可選任一個(gè)點(diǎn)做起點(diǎn)，且一筆畫后可以回到出發(fā)點(diǎn).

②若奇點(diǎn)個(gè)數(shù)為2，可選其中一個(gè)奇點(diǎn)做起點(diǎn)，而終點(diǎn)一定是另一個(gè)奇點(diǎn)，即一筆畫后不可以回到出發(fā)點(diǎn).

在表示七橋問題的圖2（b）中，現(xiàn)在我們來數(shù)一數(shù)，奇點(diǎn)的個(gè)數(shù)有幾個(gè)？由此你明白七橋問題無解的道理了嗎？

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

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

1. 一輛灑水車要給某城市的街道灑水，街道地圖如圖9，你能否設(shè)計(jì)一條灑水車灑水的路線，使灑水車不重復(fù)地走過所有的街道，再回到出發(fā)點(diǎn)？

2. 如圖10是一個(gè)公園的平面圖，能不能使游人走遍每一條路不重復(fù)？入口和出口又應(yīng)設(shè)在哪兒？

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