七橋問題與一筆畫

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

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

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

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

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

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

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

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

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

②若奇點(diǎn)個(gè)數(shù)為2，可選其中一個(gè)奇點(diǎn)做起點(diǎn)，而終點(diǎn)一定是另一個(gè)奇點(diǎn)，即一筆畫后不可以回到出發(fā)點(diǎn)。總結(jié)規(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)。

③凡是圖形中有2個(gè)以上奇點(diǎn)的，不能完成一筆畫。

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

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

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

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

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