有趣的一筆畫問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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