一筆畫和多筆畫

1、第九講 一筆畫和多筆畫問題1 你能一筆畫出一個“田”字嗎？所謂一筆畫出的意思就是在一張紙上（不允許折疊）筆不離紙，而且每一筆劃（或稱線段）只能畫一次，不準重復(fù)。對于“串”字或“品”字呢？結(jié)果會怎樣？（參看圖81）通過各種嘗試發(fā)現(xiàn)，“田”字總也不能一筆畫成，而“串”字卻可以一筆畫成。由于“品”字中的三個“口”字不連在一起，顯然也不能一筆畫成。我們把那些能一筆畫成的圖形叫一筆畫。一筆畫問題主要討論什么樣的圖形可以一筆畫成。例1 下列圖形哪些能一筆畫成？哪些不能一筆畫成？經(jīng)過嘗試，你會發(fā)現(xiàn)，圖82（a）、（c）、（e）是可以一筆畫成的。而且圖（c）、（e）可從任意一點出發(fā)，一筆畫成回到出發(fā)點，而圖（

2、a）只能從A（或D）點出發(fā)，一筆畫成到D（或A）點結(jié)束。如果圖形非常復(fù)雜，用這種逐一嘗試的方法，則所花的時間較多，且有時還無法下結(jié)論。有沒有一種簡便的判斷方法呢？下面就來研究這個問題。上面研究的圖形都是由點和線段（或?。┙M成的，在數(shù)學(xué)中叫做圖。圖形中的點叫圖的結(jié)點，線段（或?。┙凶鰣D的邊。作為一個圖，其圖形還必須滿足以下條件：（1）每條邊都有兩個端點（可以重合）作為結(jié)點；（2）各條邊之間互不相交。一個圖完全由它的結(jié)點和邊的個數(shù)以及它們相互連結(jié)的情況來確定，而與邊的曲直長短無關(guān)。圖中與一個結(jié)點相連結(jié)的邊的條數(shù)稱為這個結(jié)點的度數(shù)。度數(shù)為偶數(shù)的結(jié)點叫做偶結(jié)點。例如，圖83中結(jié)點C、D、E都是偶結(jié)點。

3、度數(shù)為奇數(shù)的結(jié)點叫做奇結(jié)點。例如，圖83中結(jié)點A、B、F、G都是奇結(jié)點。任何兩點間都有線連接的圖稱作連通圖。（如圖83中D與G可通過DB、BA、AG連接）觀察例1中的五個圖，其結(jié)點的奇偶性可列成下表：從表中可以發(fā)現(xiàn)，一個圖能否一筆畫成，與圖的奇結(jié)點的個數(shù)有密切聯(lián)系，人們總結(jié)出如下規(guī)律：一個圖若是一筆畫必定是個連通圖。一個連通圖，若沒有奇結(jié)點（即全是偶結(jié)點），那么這個圖一定可以一筆畫成，而且可以從任一偶結(jié)點出發(fā)，一筆畫成回到出發(fā)點。一個連通圖，若只有兩個奇結(jié)點，那么這個圖也可以一筆畫成。而且只能從某一奇結(jié)點出發(fā)一筆畫成，到另一奇結(jié)點結(jié)束。一個圖，若奇結(jié)點個數(shù)多于兩個，那么這個圖就不能一筆畫成。例

4、2 判斷下列各圖是否能一筆畫出來。解：其中（b）、（d）、（e）三個圖無奇結(jié)點，所以可從任一點出發(fā)，一筆畫成，并且回到出發(fā)點；（a）、（f）兩圖各有兩個奇結(jié)點，所以可從其中一個奇結(jié)點出發(fā)，一筆畫成，到另一個奇結(jié)點結(jié)束；而圖（C）的八個結(jié)點都是奇結(jié)點，所以不能一筆畫出來。當(dāng)作練習(xí)，請把例2中能夠一筆畫的圖一筆畫出來。二、七橋問題和歐拉定理問題2 七橋問題。關(guān)于一筆畫，曾有一個頗為著名的哥尼斯堡七橋問題。事情發(fā)生在18世紀的哥尼斯堡，有一條河流從這個城市穿過，河中有兩個小島A、B，河上有七座橋連結(jié)兩個小島及河的兩岸（參看圖85），那里的居民在星期日有散步的習(xí)慣。有的人想，能不能一次走遍七座橋，每座

5、橋只走過一次，最后回到出發(fā)點？這個問題似乎不難，誰都想試一試，但誰也沒有找到答案。后來有人寫信請教著名的瑞士數(shù)學(xué)家歐拉。歐拉的頭腦比較冷靜，千百人的失敗使他猜想：也許那樣的走法根本就不存在。1936年他證明了自己的猜想。歐拉解決七橋問題的方法獨特，思想新穎，非常富有啟發(fā)性。他用點表示小島和兩岸，用連結(jié)兩點的線段表示連結(jié)相應(yīng)兩地的橋，得到由七條線段連結(jié)四個點而成的圖形（參看圖85（b）。這樣七橋問題就變成了一個一筆畫問題：能不能一筆畫出這個圖形，并且最后返回起點？前面我們雖然通過對例1的分析歸納出了一個連通圖是否能一筆畫出來的三條結(jié)論，但并沒有證明，沒有說明這是為什么。下面我們簡要說明其中的道理

6、。一個連通圖能否一筆畫成主要是與結(jié)點的邊數(shù)（也稱度數(shù)）有關(guān)。假定某個圖能一筆畫成，如果結(jié)點P不是起點或終點，而是中間點，那么P一定是個偶結(jié)點。因為無論何時通過一條邊進入P，由于不能重復(fù)，必須從另一條邊離開P，因此與P連結(jié)的邊一定成對出現(xiàn)，所以P是偶結(jié)點。如果一個結(jié)點Q是奇結(jié)點，那么在一筆畫中只能是起點或終點。由此可以看出，在一個一筆畫中，奇結(jié)點個數(shù)至多只能有兩個。由于哥尼斯堡七橋問題相應(yīng)的圖中有四個奇結(jié)點，所以不能一筆畫成。也就是說，七橋問題無解，證實了歐拉的猜想。歐拉通過對七橋問題的研究，不僅圓滿地回答了哥尼斯堡居民提出的問題，而且得到并證明了更為廣泛的上述有關(guān)一筆畫的三條結(jié)論，人們通常稱之

7、為歐拉定理。1736年，歐拉在圣彼得堡科學(xué)院作了一次報告，公布了他關(guān)于七橋問題的研究成果。歐拉在研究中提出了一種新穎的數(shù)學(xué)問題及思想方法，它標志著一門嶄新的數(shù)學(xué)學(xué)科圖論的誕生。對于一個連通圖，通常把從某結(jié)點出發(fā)一筆畫成所經(jīng)過的路線叫做歐拉路。例如，圖86（a）中的圖無奇結(jié)點，可以從A點出發(fā)，一筆畫成回到A點，其路線為ADEHDGHIFEBFCBA。圖86（b）中的圖有兩個奇結(jié)點C和E，可以從E出發(fā)一筆畫成，到C結(jié)束。其路線為EDCBAC。這兩條路線都是歐拉路。應(yīng)當(dāng)注意：一個圖如果存在歐拉路，那么不一定是唯一的。人們又通常把一筆畫成回到出發(fā)點的歐拉路叫做歐拉回路。具有歐拉回路的圖叫做歐拉圖。例如

8、，圖86（a）所表示的路線就是一條歐拉回路，因此相應(yīng)的圖就是一個歐拉圖。例3 圖87是一公園的平面圖，線段表示路徑，要使游客走遍每條路且不重復(fù)，問出入口應(yīng)設(shè)在哪里？分析與解：這個問題實質(zhì)上是一個一筆畫問題。圖中只有兩個奇結(jié)點C和E，因此，只要把出入口分別設(shè)在這兩個奇結(jié)點處，游客就能由入口進入公園，不重復(fù)地走遍每條路，然后從出口處離開公園。例4 能否一筆畫出一條曲線，使它和圖88中的八條線段都只相交一次（不準在端點處相交）？分析與解：嘗試幾次后，會感到很難下結(jié)論。事實上，直接尋找答案并不容易。我們可從七橋問題得到啟示。原圖形把平面分成了五個部分，分別用A、B、C、D、E五個點表示。兩個點之間的連

9、線正好用來表示與相應(yīng)的線段相交一次，如圖88（b）。于是，問題就變成了圖88（b）中所表示的圖能否一筆畫成。因為圖中A、B、C、D都是奇結(jié)點，因此，它不能一筆畫成，即不存在符合題目要求的曲線。例5 圖89表示一個展覽館的平面圖，其中共有五個展覽室，每個展覽室都有一個門通向室外。能否設(shè)計一條參觀路線，一次不重復(fù)地穿過每一個門并能回到原地。分析與解：如果用A、B、C、D、E表示展覽室，用F表示室外，用連線表示相應(yīng)的門，那么圖89（a）就變成了圖89（b）于是問題就轉(zhuǎn)化為判斷圖89（b）是否為歐拉圖。由圖中可以看出，點C、D、E、F都是奇給點，因而圖89（b）不具有歐拉回路。所以不是歐拉圖。也就是說

10、，不存在題中所要求的那種參觀路線?？梢赃M一步考慮，關(guān)閉了哪兩個門之后，就能設(shè)計出符合題中要求的參觀路線了？為此，只要使圖89（b）變?yōu)闅W拉圖，即使它的奇結(jié)點個數(shù)為O即可。例如抹去線段CD和EF后的圖就沒有奇結(jié)點了。也就是說，如果關(guān)閉C、D之間和E、F之間的兩個門，就能設(shè)計出一條參觀路線，一次不重復(fù)的穿過每一個門，并能回到原地。請你試一試，同時想一想，是否還存在其它的答案，一共有幾種？三、多筆畫在第一冊第八講例1中，我們討論了下列圖形的一筆畫問題。通過觀察列出了下表：由此表我們發(fā)現(xiàn)，一個圖能否一筆畫成與圖的奇結(jié)點的個數(shù)有關(guān)系。如果我們再進一步觀察，還可發(fā)現(xiàn)，這些圖中的奇結(jié)點的數(shù)目都是偶數(shù)。這是一

11、種偶然的巧合還是一種普遍的規(guī)律呢？如果我們再觀察一些其它的圖，結(jié)果也是沒有出現(xiàn)奇結(jié)點數(shù)目是奇數(shù)的現(xiàn)象。于是我們可以作如下猜想：在任何一個圖中，奇結(jié)點的個數(shù)一定是偶數(shù)。這是因為一個圖的每條邊都與兩個結(jié)點相連結(jié)，所以，如果把一個圖的所有結(jié)點的度數(shù)相加，由于每條邊都計算了兩次，其度數(shù)和是邊數(shù)的2倍，它是偶數(shù)，可設(shè)為2n。又因為每個偶結(jié)點的度數(shù)都是偶數(shù)，它們的度數(shù)和當(dāng)然是偶數(shù)，可設(shè)為2m。由此可知，所有奇結(jié)點的度數(shù)和為2n2m2（nm）（n、m為自然數(shù)）也是一個偶數(shù)，但每個奇結(jié)點的度數(shù)都是奇數(shù)，所以奇結(jié)點的個數(shù)一定是偶數(shù)。否則，如果奇結(jié)點的個數(shù)是奇數(shù)，那么，因為奇數(shù)個奇數(shù)的和是奇數(shù)，就得到所有奇結(jié)點度

12、數(shù)的和是奇數(shù)。這與上述結(jié)論相矛盾。這就說明，在任何一個圖中，奇結(jié)點的個數(shù)一定是偶數(shù)。例1 先數(shù)一數(shù)下列各圖形中奇結(jié)點的個數(shù)。如果有的圖形不能一筆畫成，那么，至少幾筆才能畫成？分析與解 ：圖82（a）中只有兩個奇結(jié)點，根據(jù)歐拉定理，可從A點出發(fā)一筆畫出到B點結(jié)束，圖（b）中有四個奇結(jié)點，不能一筆畫成。圖82（b）與圖（a）比較，多出了折線CEFD。如果先一筆畫出圖（a），再添一筆畫出折線CEFD，就可得到圖（b）。因此，圖（b）至少兩筆才能畫成。圖82（c）中共有六個奇結(jié)點，也不能一筆畫成。圖（c）與圖（b）比較又多出了一面旗子。它也含有兩個奇結(jié)點，于是在兩筆畫出圖（b）的基礎(chǔ)上，再添一筆畫上旗

13、子，就成了圖（c）。因此，圖（c）至少三筆才能畫成。例2 圖83（a）表示一所房子，問至少幾筆才能畫成？分析與解：1圖83（a）所示的圖中共有B、E、F、G、I、J六個奇結(jié)點，所以不能一筆畫成。如果我們將兩個奇結(jié)點間的連線去掉一條，那么這兩個奇結(jié)點就成為偶結(jié)點了。當(dāng)我們把圖中奇結(jié)點的個數(shù)減少到2個時，（想一想，奇結(jié)點個數(shù)為何不需減少到零個？）新的圖就可以一筆畫成了。在圖（a）中，第一筆畫BJ，第二筆畫GF。這樣剩下I、E兩個奇結(jié)點，如圖（b）所示，這個圖是可以一筆畫成的。所以這所房子至少要三筆才能畫成。由上述兩個例題看到，如果圖中有兩個奇結(jié)點，一筆就能畫出；有四個奇結(jié)點，至少兩筆才能畫出；有六

14、個奇結(jié)點，至少三筆才能畫出；如果圖中有八個奇結(jié)點，利用同樣的道理分析，至少四筆才能畫成。一般地，一個連通圖如果有2n（n為自然數(shù)）個奇結(jié)點，那么至少畫n筆才能畫成。我們把這類問題稱作多筆畫問題。四、郵遞路線問題 一個郵遞員每次送信，要走遍他負責(zé)投遞的范圍內(nèi)的街道，完成任務(wù)后回到郵局。問他按怎樣的路線走，所走的路程最短？這個問題叫做最短郵遞路線問題，是一個即有趣又實用的問題。例3 圖84（a）、（b）都表示街道圖。圖中A是郵局的位置，問郵遞員應(yīng)如何設(shè)計他的郵遞路線，才能使他所走的路程最短？分析與解：由于（a）所表示的圖無奇結(jié)點，所以是一個歐拉圖。他可以從郵局出發(fā)，不重復(fù)地走遍每條街道，回到郵局，

15、這就是投遞員的最短路線。而（b）所表示的圖有六個奇結(jié)點，它不是一筆畫，要不重復(fù)地走遍街道是不可能的。為了走遍所有的街道，必須重復(fù)走某些街道。重復(fù)走哪些街道才能使總路程最短呢？由于任何一個圖中奇結(jié)點的個數(shù)都是偶數(shù)，所以可把奇結(jié)點兩兩配對。如果在一對奇結(jié)點之間連一條虛線當(dāng)作增添的重復(fù)邊，奇結(jié)點就變成了偶結(jié)點，用這種方法可使原來的圖變成沒有奇結(jié)點的歐拉圖（增添了重復(fù)邊）。現(xiàn)在的問題是如何去連這些虛線，才能保證總路程最短。其原則是：（1）連線（虛線）不能有重疊線段；（2）在每一個圈上，連線長度之和不能超過圈長的一半。例如，圖85（a）中，連虛線時在KG一段上發(fā)生重疊。根據(jù)原則（1），應(yīng)去掉重疊部分改成

16、圖85（b）。但在（b）中，對于BKJCB這個圈來說，增添的虛線長超過圈長的一半。根據(jù)原則（2），可以繼續(xù)改進成（c）中增添虛線的情形，這是一種最好的增添虛線的方法。因此，最好的投遞路線是ABCDEFIFJCBKGFGHNA（參看圖86）例4 圖87表示某城市的街道圖，九個區(qū)都是邊長為1公里的正方形，現(xiàn)需設(shè)一牛奶站，希望找一最佳地址，要能使送奶車以最短路程跑遍城市的所有街道，然后返回奶站。如果小明把奶站選在P點，試問他選的地方對嗎？送一遍奶所走的最短路程比該城市全部街道的總長長多少？分析與解：由于圖87中有8個奇結(jié)點，所以必須重復(fù)走某些街道，才能送遍全城回到奶站。根據(jù)例3中的兩條原則，重復(fù)路線

17、可添設(shè)如圖88。這樣圖中的結(jié)點全部為偶結(jié)點，說明奶站設(shè)在街道任何一處都一樣。因此，小明選在P點沒有錯。一次送遍全城回到奶站的最短路程應(yīng)是24428（公里）比城市全部街道總長多4公里，多走城市街道總長的16.7%。習(xí)題十六1判斷下列各圖能否一筆畫成。若不是一筆畫，則至少幾筆才能畫成？2各單位在圖中用數(shù)字標出，彼此間有路相通。一郵遞員從郵局出發(fā)，向各單位傳遞郵件，他能否不走重復(fù)路線，也不經(jīng)重復(fù)單位，又回到郵局？3一個郵遞員投遞信件的街道如圖所示。圖上數(shù)字表示各段街道的公里數(shù)。他從郵局出發(fā)，要走遍各街道，最后回到郵局，請為他設(shè)計一條最合理的路線，全程要走多少公里？4一個投遞員投遞的街區(qū)如圖所示。圖上數(shù)字表示各街道的長度。他從郵局出發(fā)，