第九講一筆畫(huà)

1、例例1: 下圖是一個(gè)公園的平面圖，要使游客通過(guò)每條路且下圖是一個(gè)公園的平面圖，要使游客通過(guò)每條路且不重復(fù)，問(wèn)出入口應(yīng)設(shè)在哪里？不重復(fù)，問(wèn)出入口應(yīng)設(shè)在哪里？點(diǎn)撥點(diǎn)撥 這個(gè)問(wèn)題實(shí)質(zhì)上是一筆畫(huà)問(wèn)題，數(shù)一數(shù)奇點(diǎn)與偶點(diǎn)各多少。這個(gè)問(wèn)題實(shí)質(zhì)上是一筆畫(huà)問(wèn)題，數(shù)一數(shù)奇點(diǎn)與偶點(diǎn)各多少。解答解答 因?yàn)閳D中只有因?yàn)閳D中只有B和和J處兩個(gè)奇點(diǎn)，因此只要把出入口分別處兩個(gè)奇點(diǎn)，因此只要把出入口分別設(shè)在這兩個(gè)奇點(diǎn)處，游客就能從入口處進(jìn)入公園，不重復(fù)地設(shè)在這兩個(gè)奇點(diǎn)處，游客就能從入口處進(jìn)入公園，不重復(fù)地走遍所有的路后從出口處離開(kāi)公園，圖所示是其中的一種走遍所有的路后從出口處離開(kāi)公園，圖所示是其中的一種走法。走法。 JB入口

2、出口圖EABCDFGIJ圖例例2:18世紀(jì)的歐洲有個(gè)哥尼斯堡城，瑞格爾河穿過(guò)這個(gè)城市，世紀(jì)的歐洲有個(gè)哥尼斯堡城，瑞格爾河穿過(guò)這個(gè)城市，河上有兩個(gè)島，在島與島之間及陸地河上有兩個(gè)島，在島與島之間及陸地B、C與島之間有與島之間有7座橋，座橋，不少人熱衷于一個(gè)有趣的數(shù)學(xué)游戲不少人熱衷于一個(gè)有趣的數(shù)學(xué)游戲:一個(gè)游人怎樣才能走遍七座一個(gè)游人怎樣才能走遍七座橋，每座橋只能經(jīng)過(guò)一次，最后又回到出發(fā)點(diǎn)？橋，每座橋只能經(jīng)過(guò)一次，最后又回到出發(fā)點(diǎn)？點(diǎn)撥點(diǎn)撥 考慮一筆畫(huà)問(wèn)題，若奇點(diǎn)超過(guò)考慮一筆畫(huà)問(wèn)題，若奇點(diǎn)超過(guò)2個(gè)就不行。個(gè)就不行。解答解答 把兩個(gè)島把兩個(gè)島A，D和陸地和陸地B，C縮小為縮小為4個(gè)點(diǎn)，把個(gè)點(diǎn)，把7座

3、橋變成連接座橋變成連接A、B、C、D的的7條線，如右圖所示。條線，如右圖所示。顯然顯然A、B、C、D都是奇點(diǎn)，不能將圖一筆畫(huà)成，都是奇點(diǎn)，不能將圖一筆畫(huà)成，也就是說(shuō)不能沒(méi)有重復(fù)地一次走遍七座橋。也就是說(shuō)不能沒(méi)有重復(fù)地一次走遍七座橋。 遷移遷移1 公園有公園有9塊花園，水源在塊花園，水源在A處（如圖所示），現(xiàn)在要處（如圖所示），現(xiàn)在要修渠引水澆地，修的水渠不許交叉，路線要最簡(jiǎn)捷，還要澆修渠引水澆地，修的水渠不許交叉，路線要最簡(jiǎn)捷，還要澆遍遍9塊地，你說(shuō)這條水渠怎樣修？塊地，你說(shuō)這條水渠怎樣修？AA遷移遷移2 下圖中有下圖中有A、B、C、D、E、F六個(gè)小島，各六個(gè)小島，各島之間共有島之間共有15座

4、橋，現(xiàn)在要從座橋，現(xiàn)在要從A島出發(fā)，不重復(fù)地走島出發(fā)，不重復(fù)地走遍十五座橋，能走嗎？若能則該怎么走？遍十五座橋，能走嗎？若能則該怎么走？A B C B D B E D E F D A D C A F熱身熱身1 能否一筆畫(huà)出一條線路，使它和下圖中的八條線段能否一筆畫(huà)出一條線路，使它和下圖中的八條線段都相交一次，且不準(zhǔn)在端點(diǎn)相交？都相交一次，且不準(zhǔn)在端點(diǎn)相交？不能，因?yàn)閳D中有四個(gè)奇點(diǎn)。不能，因?yàn)閳D中有四個(gè)奇點(diǎn)。熱身熱身2 在六面體的頂點(diǎn)在六面體的頂點(diǎn)B上有一只螞蟻，它與頂點(diǎn)上有一只螞蟻，它與頂點(diǎn)E上的另一只螞蟻約定，在爬速相同時(shí)爬過(guò)所有的棱上的另一只螞蟻約定，在爬速相同時(shí)爬過(guò)所有的棱線之后，最后到

5、終點(diǎn)線之后，最后到終點(diǎn)D，問(wèn)哪知螞蟻獲勝？，問(wèn)哪知螞蟻獲勝？E螞蟻先到達(dá)D，因?yàn)閳D中只有D與E是奇點(diǎn)，B螞蟻是從偶點(diǎn)出發(fā)必走重復(fù)路。ABCDE拓展拓展1 農(nóng)技試驗(yàn)田里用縱橫的田埂劃分成農(nóng)技試驗(yàn)田里用縱橫的田埂劃分成9個(gè)作物對(duì)比區(qū)（見(jiàn)個(gè)作物對(duì)比區(qū)（見(jiàn)圖所示）。農(nóng)技員過(guò)橋后，能不能不走重復(fù)的路，把試驗(yàn)田的圖所示）。農(nóng)技員過(guò)橋后，能不能不走重復(fù)的路，把試驗(yàn)田的田埂走一遍？若不能，請(qǐng)找出一條走重復(fù)路線最少的捷徑來(lái)。田埂走一遍？若不能，請(qǐng)找出一條走重復(fù)路線最少的捷徑來(lái)。橋不能。因?yàn)橛胁荒堋Ｒ驗(yàn)橛?個(gè)奇點(diǎn)。捷徑設(shè)計(jì)如圖（虛線表示重復(fù)路）個(gè)奇點(diǎn)。捷徑設(shè)計(jì)如圖（虛線表示重復(fù)路）橋拓展拓展2一位郵遞員每天騎自行車(chē)去送信，他投送信件的一位郵遞員每天騎自行車(chē)去送信，他投送信件的街道如下圖所示，圖上數(shù)字表示街道的千米數(shù)，他街道如下圖所示，圖上數(shù)字表示街道的千米數(shù)，他從郵局出發(fā)，走遍街道后回到郵局，問(wèn)走什么樣的從郵局出發(fā)，走遍街道后回到郵局，問(wèn)走什么樣的路線最合理？最少走的是千米？路線最合理？最少走的是千米？最短路線設(shè)