有趣的一筆畫問題

1、有趣的一筆畫問題一筆畫問題的提出：一筆畫是一個大問題，為了更好的解決這個問題，我們從生活提出一筆畫問題。我們先看一個公路檢查員的問題：他為了檢查幾個城市之間的若干公路，希望在這些城市和公路組成的公路系統(tǒng)中找出一條路線，使他能不重復(fù)地恰好通過每條公路一次，而經(jīng)過每個城市的次數(shù)不限。這就是拓?fù)鋵W(xué)中的數(shù)學(xué)問題。一筆畫的含義如果用筆在紙上連續(xù)不斷又不重復(fù)，一筆畫成某種圖形，這種圖形就叫一筆畫。下面的畫能一筆畫成，你也試著描一描，畫一畫吧！那么是不是所有的圖形都能一筆畫成呢？那我們就要一起學(xué)習(xí)一筆畫的規(guī)律。其實一筆畫是一個幾何問題，一個圖形由一筆構(gòu)成叫一筆畫。傳統(tǒng)意義上的幾何學(xué)是研究圖形的形狀大小等性質(zhì)

2、，而對于平面圖形的一筆畫與多筆畫問題，通常的幾何方法是無能為力的，因為一個圖形能否一筆畫，與圖形的大小、形狀和線段的長短等幾何概念都沒有關(guān)系，而是與圖形中線段的數(shù)目及連接關(guān)系有關(guān)，我們可以隨意地將圖形拉伸、壓縮或彎曲，甚至在保持端點不動的前提下，還可以將某些線段“搬家”，只要圖形的整體結(jié)構(gòu)不變，能否一筆畫的性質(zhì)也就不會改變。一筆畫問題是一個簡單的數(shù)學(xué)游戲，即平面上由曲線段構(gòu)成的一個圖形能不能一筆畫成，使得在每條線段上都不重復(fù)？例如漢字日和中字都可以一筆畫的，而田和目則不能。(在日本動畫片一休中，是采用對折紙張的方法畫出田和目的一筆畫）也是可取之處。一筆畫圖形的規(guī)律和判別：著名的哥尼斯堡七橋問題

3、實質(zhì)上就是一個一筆畫問題。歐拉最終證明了這個圖形是不能一筆畫成的，并在關(guān)于七橋問題的報告中得到了任一網(wǎng)絡(luò)圖能否一筆畫的判別法則。歐拉認(rèn)為，能一筆畫的圖形必須是連通圖。連通圖就是指一個圖形各部分總是有邊相連的但是，不是所有的連通圖都可以一筆畫的。能否一筆畫是由圖的奇、偶點的數(shù)目來決定的。數(shù)學(xué)家歐拉找到一筆畫的規(guī)律是：1凡是由偶點組成的連通圖，一定可以一筆畫成。畫時可以把任一偶點為起點，最后一定能以這個點為終點畫完此圖。2凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫成。畫時必須把一個奇點為起點，另一個奇點終點。3其他情況的圖都不能一筆畫出。（有偶數(shù)個奇點除以二便可算出此圖需幾筆畫成）比

4、如附圖：（a）為（1）情況，因此可以一筆畫成；（b）（c）（d）則沒有符合以上兩種情況，所以不能一筆畫成。補充：相關(guān)名詞的含義頂點與指數(shù)：設(shè)一個平面圖形是由有限個點及有限條弧組成的，這些點稱為圖形的頂點，從任一頂點引出的該圖形的弧的條數(shù)，稱為這個頂點的指數(shù)。奇頂點：指數(shù)為奇數(shù)的頂點。偶頂點：指數(shù)為偶數(shù)的頂點七橋問題與歐拉定理：這是一段與數(shù)學(xué)有關(guān)的故事。在十八世紀(jì)的時候，普魯士的哥尼斯堡有一個公園，公園里有一條河勒格爾河穿過，河有兩條支流，河上有兩個小島，將整個城市分割成四塊，當(dāng)?shù)氐娜藶榱私煌ǚ奖?，就建了七座橋作連接把兩個島與河岸聯(lián)系起來(見下圖)。當(dāng)?shù)氐氖忻窠?jīng)常從事一項非常有趣的消遣活動。就是

5、在星期六作一次走過所有七座橋的散步，每座橋只能經(jīng)過一次而且起點與終點必須是同一地點。（一個人能否一次走遍所有的七座橋，而每座橋只通過一次？）這就是著名的七橋問題。很多人對此很感興趣，紛紛進行試驗，哥尼斯堡的居民苦思多時，在相當(dāng)長的時間里，無法解決這條問題。利用普通數(shù)學(xué)知識，每座橋均走一次，那這七座橋所有的走法一共有7×6×5×4×3×2×1=5040種，而這么多情況，要一一試驗，這將會是很大的工作量。但怎么才能找到成功走過每座橋而不重復(fù)的路線呢？因而形成了著名的“哥尼斯堡七橋問題”。1735年，哥尼斯堡的幾名大學(xué)生寫信給當(dāng)時正在俄羅斯

6、的彼得斯堡科學(xué)院任職的天才數(shù)學(xué)家歐拉，請他幫忙解決這一問題。歐拉在親自觀察了哥尼斯堡七橋后，認(rèn)真思考走法，但始終沒能成功，于是他懷疑七橋問題是不是原本就無解呢？歐拉以深邃的洞察力很快證明了這樣的走法不存在。歐拉是這樣解決問題的：既然陸地是橋梁的連接地點，不妨把圖中被河隔開的陸地和小島看成a、b、c、d 4個點，7座橋表示成7條連接這4個點的線，如圖2所示。證明圖二能否一筆畫及怎么畫的問題即可解決哥尼斯堡城七橋問題。1736年29歲的歐拉向圣彼得堡科學(xué)院遞交了哥尼斯堡的七座橋的論文，在解答問題的同時，開創(chuàng)了數(shù)學(xué)的一個新的分支圖論與幾何拓?fù)洹Ｒ灿纱苏归_了數(shù)學(xué)史上的新歷程。歐拉通過對七橋問題的研究，

7、不僅圓滿地回答了哥尼斯堡居民提出的問題，而且得到并證明了更為廣泛的有關(guān)一筆畫的三條結(jié)論，人們通常稱之為“歐拉定理”。對于一個連通圖，通常把從某結(jié)點出發(fā)一筆畫成所經(jīng)過的路線叫做歐拉路。人們又通常把一筆畫成回到出發(fā)點的歐拉路叫做歐拉回路。具有歐拉回路的圖叫做歐拉圖。一筆畫問題探討：先說明幾個定義：奇結(jié)點：有奇數(shù)（單數(shù)）條邊的點稱為奇結(jié)點。偶結(jié)點：有偶數(shù)（雙數(shù)）條邊的點稱為偶結(jié)點。例如圖三中：圖 三：A有3條邊，是奇結(jié)點；B有3條邊，是奇結(jié)點；C有2條邊，是偶結(jié)點；D有2條邊，是偶結(jié)點；E有3條邊，是奇結(jié)點；F有3條邊，是奇結(jié)點；G有4條邊，是偶結(jié)點；這個圖有4個奇結(jié)點，3個偶結(jié)點。凡是能一筆畫的圖

8、，我們稱之為歐拉圖。歐拉圖有以下3個特點：1、歐拉圖必須是連通圖。連通就是說任意兩個點之間可以找到一條直接連接或經(jīng)由其它點連接它們的線。例如圖三就是個聯(lián)通圖，以下圖四，由ABC和DEF構(gòu)成的一個圖就不是聯(lián)通圖。圖 三： 2、都由偶結(jié)點組成的連通圖，是歐拉圖。3、無論是否有幾個偶結(jié)點（也可以沒有偶結(jié)點），只有兩個奇結(jié)點的連通圖，是歐拉圖。對于1.很好理解，圖不聯(lián)通，肯定也就不能一筆畫了。例如圖四是怎么都無法一筆畫的（2個三角形之間沒有連接線，當(dāng)然不聯(lián)通啦，也就不能一筆畫啦）。對于2.和3.我們通過以下幾個圖來理解：我們來看圖五圖 五： 圖五是個歐拉圖，圖中僅有一個點A，A既是圖的起點又是圖的終點

9、，對A來說它有兩條邊，A是個偶結(jié)點。看圖六圖 六： 圖六是個歐拉圖，圖中有兩個點，A和B，其中一個是起點，則另一個必是終點。A和B都是奇結(jié)點?？磮D七圖 七： 圖七是個歐拉圖。我們現(xiàn)在只看C點，C有2條邊，被途經(jīng)1次。因為連線途經(jīng)C點，對C點來說，有一進線則必有一出線（否則也就不是途經(jīng)了），點C是個偶結(jié)點。在一筆畫問題中，我們對于線段的長短以及線段是彎是直或是弧線并不關(guān)心，我們關(guān)注的是點與點之間是否有連線以及圖形的連接構(gòu)造。因此可以說，就一筆畫問題，所有的圖都是由最基本的圖五、圖六、圖七所組合而成的。我們接著看圖八圖八也是一個歐拉圖。還看C點，C不是起點也不是終點，C有4條邊，被途經(jīng)2次。在歐拉

10、圖中，只要不是起點或終點的點永遠(yuǎn)是有一進線則必有一出線，這個點無論被線路途經(jīng)過多少次，它都是個偶結(jié)點，B點、C點、D點都不是起點或終點，且都是偶結(jié)點。接著看圖九圖九是個歐拉圖。這次我們重點看B點，點B是起點（或者是終點），它有3條邊，被途經(jīng)1次，它是個奇結(jié)點。在歐拉圖中，起點和終點不是同一個點的話，起點或終點無論是否另有線路途經(jīng)，無論被途經(jīng)過多少次，它都是個奇結(jié)點。接著看圖十圖十是個歐拉圖。圖中的點都是偶結(jié)點，如果我們把A作為起點，則A也是終點，其它點都被途經(jīng)，其中D被途經(jīng)2次。我們也可以把D點作為起點，則D點也是終點，被途經(jīng)1次。對于全是偶結(jié)點的聯(lián)通圖，它肯定是個歐拉圖，而且任何一點都可以作

11、為起點一筆畫?？磮D十一圖十一不是一個歐拉圖，該圖共有4個奇結(jié)點。對于一個歐拉圖來說，如果起點和終點不是同一個點的話，那么起點必然是個奇結(jié)點，終點也必然是個奇結(jié)點。一個圖要想一筆畫，不可能有一個起點和多個終點，也不可能有多個起點和一個終點，更不可能有多個起點和多個終點。所以，只含有兩個奇結(jié)點，無論有無偶結(jié)點的聯(lián)通圖都是歐拉圖，這個圖的一筆畫只能從奇結(jié)點開始。另外還有一個推論：因為如果起點和終點不是同一個點的話，則有一起點就必有另一終點，起點和終點成對出現(xiàn)，且只能是奇結(jié)點（即使這個起點或終點又被其它線路途經(jīng)，途經(jīng)過程不能改變該點的奇偶性，不明白可回頭看看圖九的B點），所以無論能否一筆畫，聯(lián)通圖中的

12、奇結(jié)點總是成對出現(xiàn)，即聯(lián)通圖中只可能有偶數(shù)個奇結(jié)點。不信你畫個含3個奇結(jié)點的聯(lián)通圖試試？總結(jié)結(jié)論：1、能一筆畫的圖必須是聯(lián)通圖；2、全是偶結(jié)點的聯(lián)通圖能一筆畫，而且可以從任何一個點畫起；3、聯(lián)通圖中只含有2個奇結(jié)點的話，無論該圖有無偶結(jié)點都可以一筆畫，但只能從任一奇結(jié)點開始畫起；4、聯(lián)通圖中奇結(jié)點有2個以上的話，不能一筆畫；5、無論能否一筆畫，聯(lián)通圖中只可能有偶數(shù)個奇結(jié)點?，F(xiàn)在一筆畫的概念都講完了，下面做一下，“日”、“田”、“串”、“目”這幾個字形能不能一筆畫，能一筆畫的話該怎么畫？哥尼斯堡城七橋問題答案是什么？(二)請把七橋問題的圖繪畫下來(用表示小島和河的左右兩岸，分別是A及B和C及D，

13、而連接各地的七條橋則用線表示。)奇數(shù)點的總數(shù)：_偶數(shù)點的總數(shù)：_(三)想一想：究竟哥尼斯堡的居民能否不重復(fù)走完七條橋？我認(rèn)為哥尼斯堡是可以/不可以一次過走完而不重復(fù)，因為_。一筆畫問題的練習(xí)：1、下面這些圖形，哪個能一筆畫？哪個不能筆畫？（1） （2） （3） （4）（）（）（）（）2、下面的圖能一筆畫成嗎？如果能，應(yīng)怎樣畫？描一描。3、下面的圖能一筆畫成嗎？如果能，應(yīng)怎樣畫？描一描。4、下圖是一個公園的道路平面圖，要使游客走遍每條路而又不重復(fù)，出、人口應(yīng)該設(shè)在哪里？有趣的一筆畫下面的這些簡筆畫都是一筆畫成的，你也來試試吧！描一描畫一畫象獅子桃子兔西瓜鯨鵝蝸牛櫻桃香蕉描一描畫一畫一筆畫問題的實

14、際應(yīng)用：一筆畫問題的應(yīng)用1.一輛灑水車要給某城市的街道灑水，街道地圖如下：你能否設(shè)計一條灑水車灑水的路線，使灑水車不重復(fù)地走過所有的街道，再回到出發(fā)點2、下圖是一個公園的平面圖，能不能使游人走遍每一條路不重復(fù)？入口和出口，又應(yīng)設(shè)在哪兒？3、甲乙兩個郵遞員去送信，兩人同時出發(fā)以同樣的速度走遍所有的街道，甲從A點出發(fā)，乙從B點出發(fā)，最后都回到郵局（C點）。如果要選擇最短的線路，誰先回到郵局？4、 郵遞員最短線路問題郵遞員投遞信件的街道如圖十二所示，圖上數(shù)字表示各街道長度（單位：千米）。他從郵局出發(fā)，走遍整個街道，最后回到郵局，怎樣走路程最短？要走多少千米？（郵局在Y點）一筆畫問題揭示的意義：一筆畫

15、問題的成功解決，其中蘊含的數(shù)學(xué)思想和策略，仍有著重要而現(xiàn)實的教育意義。品味一筆畫問題鼓勵學(xué)生大膽猜想，提高抽象分析能力，重視符號處理技巧，培養(yǎng)數(shù)學(xué)建模能力，樹立正確數(shù)學(xué)觀念。解決“ 七橋問題”的困難之處何在呢？顯然最困難之處在于把它簡化成網(wǎng)絡(luò)圖。在歐拉之前解這道題的人之所以未能成功，主要在于他們或者沒有想到要簡化問題，或者作不出歐拉的網(wǎng)絡(luò)圖。不難看出，如果網(wǎng)絡(luò)圖已經(jīng)有了，再來研究它能否一筆畫，難度就小多了，相信在那批首先研究這個問題的人中，肯定有人能解決它。而現(xiàn)實的數(shù)學(xué)問題當(dāng)然是類似“ 七橋問題”這種形式，而不是類似網(wǎng)絡(luò)圖這種形式。這就是說，解決現(xiàn)實的數(shù)學(xué)問題的第一步，通常也是最困難的一步，也

16、就是如何將問題用數(shù)學(xué)語言和符號表示出來。這就是著名數(shù)學(xué)教育家弗賴登塔爾所強調(diào)的“ 數(shù)學(xué)化”。 這就是一筆畫問題解決所揭示的意義。（數(shù)學(xué)化:把一筆畫問題數(shù)學(xué)化，以點表示城市，以弧表示公路，構(gòu)成的網(wǎng)絡(luò)圖就表示某個簡單公路系統(tǒng)。）一筆畫問題規(guī)律的證明：先定義能一筆畫出并回到起點的圖為歐拉圖，連通就是說任意兩個節(jié)點之間可以找到一條連接它們的線。這個要求看來很重要，直觀方法中與這一點對應(yīng)的是說原圖本身不能是分成多個的。證明：設(shè)G為一歐拉圖，那么G顯然是連通的。另一方面，由于G本身為一閉路徑，它每經(jīng)過一個頂點一次，便給這一頂點增加度數(shù)2，因而各頂點的度均為該路徑經(jīng)歷此頂點的次數(shù)的兩倍，從而均為偶數(shù)。反之，設(shè)G連通，且每個頂點的度均為偶數(shù)，欲證G為一歐拉圖。為此，對G的邊數(shù)歸納。當(dāng)m = 1時，G必定為單結(jié)點的環(huán)，顯然這時G為歐拉圖。設(shè)邊數(shù)少于m的連通圖，在頂點度均為偶數(shù)時必為歐拉