四級奧數(shù)第一講-一筆畫問題

1、第十二講一筆畫問題那么，什么叫一筆畫？什么樣的囹可以一筆畫出？歐扌立又是如何徹底證明 十橋問題的不可能性呢？下面，我們就來介紹這一方面的簡單知識。數(shù)學中，我們把由有限個點和連接這些點的線線段或弧所組成的圖形 叫做圏如圏 G ?圖中的點叫做圖的結(jié)點；連按兩結(jié)點的線叫做圏的邊. 如圖心中|有三個結(jié)點.；氐F. G,四條邊；線股阪卩G以及連按氐F的兩 段驅(qū)從圏 3 、00中可以看岀，任意兩點之間都有一條通路即可以從其中一點出發(fā)，沿著圖的邊走到另一點，如人到的通瞎為或H I-,這樣的圖，我們稱為連通圖i而下列圖中G的一些結(jié)點之間卻不存在 通略如M與N,像這樣的圏就不是連通圖*所謂圖的一筆畫，指的就是；

2、從圖的一點出發(fā)，筆不離纟氏，遍歷每條邊恰 好一次，即每條邊都只畫一次不推重復從上圖中容曷看出；能一筆畫出的圖 首左必須退連逋圖-但量否所有的連逋圖都可以一筆畫出呢？下面.我們就來探 求醉決這個問題的方法。為了表達的方使我們把與奇數(shù)條邊相連的結(jié)點叫做奇點，把與偶數(shù)條邊 相連的點稱為偶點如上圖 中的八個結(jié)點全是奇點，上圖b中氐F為奇 點* 富點*容易知道，上圖b可以一筆畫出，即從奇點E出發(fā)，沿箭頭所指方向. 經(jīng)過F； G. E,最后到達奇點葉同理.從奇點F出發(fā)也可以一筆回出，最后刮達 奇點反而從偶點G岀發(fā)，卻不能一筆畫岀這是為什么呢守G事實上 這并不是偶然現(xiàn)象假定某個圖可以一筆畫說 且它的結(jié)點嚴不

3、 是起點，也不是終點，而是中間點，那么X定是一個偶點這是因為無論何 時通過一條邊到達工，由于不能重復，蘑須從列一條邊離開X.遠樣與X連結(jié)的邊 一定成對出現(xiàn)，所以X必為偶點也就是說】奇點在一筆園中只能作為起或終 點由此可以看出，在一個可以一筆畫出的圖中，奇點的個數(shù)最多只有兩個。在七橋問題的圈中有四個奇點，固此，歐拉斷言這個圈無法一筆畫岀， 也即游人不可能不重復地一決走遍七座橋更進一歩地歐拉在解決七橋問題的 同時徹底地解決了一筆畫的問題，給出了下面的歐拉定理匸 但凡由偶點組成的連通圏，一定可以一筆畫成學畫時可以任一偶戌為起 點，最后1定籠灰這個點対終點團完此圖。 但凡只有兩個奇點其余均為偶點)的連

4、通圖.一定可以一筆畫完！畫 時必須以一個奇點為起點，另一個奇點為終點 其他情況的圖，都不能一筆畫出。下面我們就來研究1筆畫問題的具體應(yīng)用：例L觀察下面的圖昭 說明哪些圖可以一筆畫完，哪些不能，為什么亍對于可 以一筆畫的圖形，扌旨明畫往.分析與解答(Q圖；可以一筆畫，因為只有兩個奇點扎B,畫祛為A頭部翅睛 犀韶r期瞎f噹.(b)圖；不能一筆畫，因為此圖不是連通圖。圖，不能一筆畫，因圖中有四個奇臥A. Br J幾(d)圏*可段一筆畫，因為只有兩個奇點；圓法為=A*C*D*A B*-E圖；可以一筆畫，因為役有奇點亍畫法可以是；LBY-LLFf GTI-J-BfEifFTJ入(Q圖：不能一筆畫出，因為

5、圖中有八個奇點注意在上面能夠一筆畫出的圖中，畫法并不是惟一的事實上，對于有兩個奇點的圖來說，任一個奇點都可以件為起點，以另一個奇點作為終點i對于沒有奇點的圖來說*任一個偶點都可以作為起點窮最后仍以這點作為點。例2以下列圖是國際奧委會的會標，你能一筆把它畫出來嗎?分析與解答一個圖能否一筆畫出，關(guān)鍵取決于這個圖中奇點的個數(shù)通過觀察可以發(fā)現(xiàn)，上圖中所有的結(jié)點都是偶點，因此，這個圖可以一筆畫出畫時可以任一結(jié)點作為起點。例3以下列圖是某地區(qū)所有街道的平面圖.甲、乙二人同時分別從 A、B出發(fā)，以相同的速度 走遍所有的街道，最后到達 C.如果允許兩人在遵守規(guī)那么的條件下可以選擇最短路徑的話， 問兩人誰能最先

6、到達C？分析與解答此題要求二人都必須走遍所有的街道最后到達 C,而且兩人的速度相同.因此，誰走的 路程少，誰便可以先到達 G容易知道，在題目的要求下，每個人所走路程都至少是所有街 道路程的總和。仔細觀察上圖，可以發(fā)現(xiàn)圖中有兩個奇點：A和C.這就是說，此圖可以以A、 C兩點分別作為起點和終點而一筆畫成.也就是說，甲可以從A出發(fā)，不重復地走遍所有的 街道，最后到達C;而從B出發(fā)的乙那么不行.因此，甲所走的路程正好等于所有街道路程的 總和，而乙所走的路程那么必定大于這個總和，這樣甲先到達Co例4 1能否用剪刀從左以下列圖中一次連續(xù)剪下三個正方形和兩個三角形?2能否用剪刀一次連續(xù)剪下右以下列圖中六個三

7、角形?【解析】：上面兩個圖形都只有兩個奇點紅色交點，都是一筆畫圖形，但用筆畫和用剪刀剪，這兩種操作是有區(qū)別的。第一、用筆畫，筆要經(jīng)過圖中的每一條線段，用剪刀剪只能剪圖形內(nèi)部線段，四周的邊框是不 能剪的；第二，用筆畫一條經(jīng)過某個點的直線后，圖形還是完整的，用剪刀沿直線經(jīng)過某個點剪一刀后， 這個圖形會被剪成兩段。因此在剪的過程中要注意技巧，可以分別準備好這樣的兩張紙片，在紙片 上畫出對應(yīng)的線段，讓孩子在剪紙的操作中慢慢體驗這一點。這兩個圖形都可以按題目要求一次連續(xù)剪下。上面左邊圖形在剪的時候注意：可以從圖形左邊 奇點開始先向右剪，遇到第一個交點后拐彎向上，再向右下，再向左剪，最后向下到第二個奇點結(jié)

8、束。例5以下列圖是某展覽廳的平面圖，它由五個展室組成，任兩展室之間都有門相通，整個展覽廳還 有一個進口和一個出口，問游人能否一次不重復地穿過所有的門，并且從入口進，從出口出？分析與解答這種應(yīng)用題，外表看起來不易解決，事實上，只要認真分析，就可以發(fā)現(xiàn)：我們并不關(guān)心展 室的大小以及路程的遠近，關(guān)心的只是能否一次不重復地走遍所有的門，與七橋問題較為類 似.因此，仿照七橋問題的解法，我們可以把每個展室看作一個結(jié)點，整個展廳的外部也看 作一個點，兩室之間有門相通，可以看作兩點之間有邊相連 這樣，展廳的平面圖就轉(zhuǎn)化成 了我們數(shù)學中的圖，一個實際問題也就轉(zhuǎn)化為這個圖如以下列圖能否一筆畫成的問題了， 即能否從

9、A出發(fā)，一筆畫完此圖，最后再回到 A。學習文檔僅供參考上圖b中，所有的結(jié)點都是偶點，因此，一定可以以 A作為起點和終點而一筆畫完此圖 也即游人可以從入口進， 一次不重復地穿過所有的門，最后從出口出來.F面僅給出一種參觀路線:Af Ef Bf C Ef Ff C D Ff A注意：此題中，必須以A分別作為起點和終點.這就要求圖中必須沒有奇點，否那么，假設(shè)有 兩個奇點，雖能一筆畫出，但與從入口入、出口出即游人的出發(fā)和終止點都在展廳外有 矛盾，其他有多個奇點的情況那么根本不可能一筆畫出。另外，通過前面的學習，大家已經(jīng)知道：一個圖如果能夠一筆畫出，那么畫的方法不止一種，但各種方法大同小異.因此，本書中, 一筆畫的問題，一般我們只給出一種畫法。練習題1.下面的圖形可以一筆畫成嗎？如果可以，請你用一筆畫成。2.判斷以下各圖能否一筆畫出，并說明理由。3一只螞蟻由A點出發(fā)，到達B點，必須不重復地經(jīng)過每一條線，你能想出好方法嗎?4.游人在林間小路上見圖散步，問能否一次不重復地走遍所有的路線后回到出發(fā)點?5 以下列圖是某個花房的平面圖，它由六間展室組成，每相鄰兩室有一門相同，請你設(shè)