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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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