七橋問題與一筆畫

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

這個問題初看起來似乎不太難，所以很多人都想試一試，尋找這種走法，但誰出找不出問題的答案，均以失敗告終。

當(dāng)時大數(shù)學(xué)家毆拉從眾多人的失敗中想到，這樣的走法可能就根本不存在，隨后他用數(shù)學(xué)的方法證實了自己的猜想是正確的，并于1736年發(fā)表了圖論（組合數(shù)學(xué)的一個分支）的第一篇論文“哥尼斯堡的七座橋”。哥尼斯堡七橋問題故事發(fā)生在18世紀(jì)歐洲東普魯士（現(xiàn)為俄羅斯的加里寧格勒）有個名叫哥尼斯堡的城市近郊。這里的普雷蓋爾河穿城而過，河中有兩個島，兩岸與兩島之間架有七座橋（如圖）。當(dāng)時城中居民熱烈地討論著這樣一個問題：一個散步者怎樣走才能不重復(fù)地走遍所有的七座橋而回到原出發(fā)點？

歐拉首先考慮到，由于關(guān)心的是能否不重復(fù)地走完七座橋而對于橋的長短，島的大小等因素都不重要，因此可進(jìn)行簡化假設(shè)，不考慮陸地的地形，不考慮橋的形狀及長短，把四塊陸地用4個點A、B、C、D來表示，七座橋用相應(yīng)的點之間的連線（曲線段或直線段）表示。問題轉(zhuǎn)換成從某個點出發(fā)能否不重復(fù)地把圖形一筆畫出來。這樣便簡化了原問題而突出了問題實質(zhì)。七橋問題就抽象成通常所說的一筆畫問題，即下筆后再不能離開紙，每一條不能重復(fù)，只畫一次，畫時任兩條線允許交叉而過。十八世紀(jì)，東普魯士的首府哥尼斯堡是一座景色迷人的城市，普萊格爾河橫貫城區(qū)，使這座城市錦上添花，顯得更加風(fēng)光旖旋。這條河有兩條支流，在城中心匯成大河，在河的中央有一座美麗的小島。河上有七座各具特色的橋把島和河岸連接起來。18世紀(jì)時風(fēng)景秀麗的小城哥尼斯堡中有一條河，河的中間有兩個小島，河的兩岸與兩島之間共建有七座橋（如圖），當(dāng)時小城的居民中流傳著一道難題：一個人怎樣才能不重復(fù)地走過所有七座橋，再回到出發(fā)點？問題情景這就是數(shù)學(xué)史上著名的七橋問題，你愿意試一試嗎？每一個到此游玩或散心的人都想試一試，可是，對于這一看似簡單的問題，沒有一個人能符合要求地從七座橋上走一遍。這個問題后來竟變得神乎其神，說是有一支隊伍，奉命要炸毀這七座橋，并且命令要他們按照七橋問題的要求去炸。七橋問題也困擾著哥尼斯堡大學(xué)的學(xué)生們，在屢遭失敗之后，他們給當(dāng)時著名數(shù)學(xué)家歐拉寫了一封信，請他幫助解決這個問題。

歐拉在數(shù)學(xué)上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。用多種方法證明了費馬小定理。以歐拉的名字命名的數(shù)學(xué)公式、定理等在數(shù)學(xué)書籍中隨處可見，與此同時，他還在物理、天文、建筑以至音樂、哲學(xué)方面取得了輝煌的成就。歐拉還創(chuàng)設(shè)了許多數(shù)學(xué)符號，例如π（1736年），e（1748年），sin和cos（1748年），△x（1755年），f（x）（1734年）等等。

數(shù)學(xué)家歐拉知道了七橋問題他用四個點A、B、C、D分別表示小島和岸，用七條線段表示七座橋（如圖）于是問題就成為如何“一筆畫”出圖中的圖形？

●點A、B表示島點C。D表示岸▎線表示橋問題分析ACDB①有奇數(shù)條邊相連的點叫奇點。如：

③一筆畫指：1、下筆后筆尖不能離開紙。2、每條線都只能畫一次而不能重復(fù)。

問題分析問題的答案如何呢？讓我們先來了解三個新概念?！瘛瘛瘼谟信紨?shù)條邊相連的點叫偶點。如：●●●活動探究下列圖形中。請找出每個圖的奇點個數(shù)，偶點個數(shù)。試一試哪些可以一筆畫出，請?zhí)畋?，從中你能發(fā)現(xiàn)什么規(guī)律？●●ABABCDE●●●●●●A●

②若奇點個數(shù)為2，可選其中一個奇點做起點，而終點一定是另一個奇點，即一筆畫后不可以回到出發(fā)點?？偨Y(jié)規(guī)律

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

③凡是圖形中有2個以上奇點的，不能完成一筆畫。

用你發(fā)現(xiàn)的規(guī)律，說一說七橋問題的答案？由于七橋問題中的四個點都是奇點，因此可以判斷它是無法一筆畫出來的，也就是說根本不存在能不重復(fù)走遍七座橋的路線！課堂練習(xí)

1、一輛灑水車要給某城市的街道灑水，街道地圖如下：你能否設(shè)計一條灑水車灑水的路線，使灑水車不重復(fù)地走過所有的街道，再回到出發(fā)點？菜市場小廣場文具店超市電器城服裝城2、下圖是一個公園的平面圖，能不能使游人走遍每一條路不重復(fù)？入口和出口又應(yīng)設(shè)在哪兒？課堂練習(xí)

BACDEFG●●●●●●●課堂練習(xí)

3、甲乙兩個郵遞員去送信，兩人同時出發(fā)以同樣的速度走遍所有的街道，甲從A點出發(fā)，乙從B點出發(fā)，最后都回到郵局（C點）。如果要選擇最短的線路，誰先回到郵局？操作體驗下列圖形能不能用一筆畫出來？

對于圖形的結(jié)構(gòu)作些分析可以看出，除去起點或終點外，凡途徑的點都應(yīng)有進(jìn)有出，即連接點的曲線必須是偶數(shù)條，我們可以把這類型的點叫偶點，因為只有起點或終點才可能有進(jìn)無出或有出無進(jìn)，這時可能有奇數(shù)條曲線與這樣的點連接，這樣的點叫做奇點，這說明，要想一筆不重復(fù)地畫出圖形，奇點的個數(shù)要么0個，要么2個，而在圖中4個點都是奇點，因而圖形不可能一筆畫出，歐拉就是用“一筆畫”作為七橋問題的一個模型，而解決了這個難題。1、在探究七橋問題中，我們運用了