[科普中國]-一筆畫問題

傳統(tǒng)意義上的幾何學(xué)是研究圖形的形狀大小等性質(zhì)，而存在一些幾何問題，它們所研究的對象與圖形的形狀和線段的長短沒關(guān)系，而只和線段的數(shù)目和它們之間的連接關(guān)系有關(guān)，比如一筆畫問題就是如此。即平面上由曲線段構(gòu)成的一個圖形能不能一筆畫成，使得在每條線段上都不重復(fù)。例如漢字“日”和“中”字都可一筆畫，而“田”和“目”則不能。兩兩相連區(qū)域可一筆畫，例如，平面4個區(qū)域兩兩相連區(qū)域可一筆劃；輪胎狀上7個兩兩相連區(qū)域可一筆畫；我們可以構(gòu)造一個多維空間的無窮個兩兩相連區(qū)域一筆劃。

定義眾所周知的“哥尼斯堡城‘七橋問題’”被大數(shù)學(xué)家歐拉開創(chuàng)了數(shù)學(xué)新分支-----圖論。也就是“一筆畫”1。一筆畫圖形的必要條件是：奇點數(shù)目是0或者2。圖⑴的“七橋問題”A,B,C,D都是奇節(jié)點，數(shù)目是4，所以不能夠“一筆畫”。 我們把節(jié)點轉(zhuǎn)換回來，成為“節(jié)面”（區(qū)域），來考慮“一筆畫”。

例子在平面中，4個或者4個以下的區(qū)域可以構(gòu)成兩兩相連的區(qū)域，可以一筆畫。圖⑵。每個區(qū)域必須是單連通的，就是一個區(qū)域不能夠是分成2塊或者2塊以上。圖⑶就不是單連通的。這是著名的四色猜想。大家知道，平面上不可能有兩兩相同的5個區(qū)域。緊致封閉平面，在一個輪胎狀的表面，7個或者7個以下的區(qū)域可以構(gòu)成兩兩相連的區(qū)域?？梢浴耙还P劃”。把圖（A）上下對折以后，再左右對折，形成一個輪胎狀，7個區(qū)域兩兩相連。

兩兩相連的區(qū)域可以不經(jīng)過其它區(qū)域到達(dá)任何一個區(qū)域。P。J希伍德以畢生精力研究四色定理，并且證明了5色定理，稀伍德考察了一般曲面著色問題提出一個推測：在有P>1個洞的封閉曲面上，足以為任何地圖著色的最小數(shù)等于（左圖上下對折再左右對折就是一個輪胎，7個區(qū)域兩兩相連，可以一筆畫）。

一筆畫的規(guī)律數(shù)學(xué)家歐拉找到一筆畫的規(guī)律是：

⒈凡是由偶點組成的連通圖，一定可以一筆畫成。畫時可以把任一偶點為起點，最后一定能以這個點為終點畫完此圖。

⒉凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫成。畫時必須把一個奇點為起點，另一個奇點終點。

⒊其他情況的圖都不能一筆畫出。（有偶數(shù)個奇點除以二便可算出此圖需幾筆畫成。）

比如附圖：（a）為⑴情況，因此可以一筆畫成；（b）（c）（d）則沒有符合以上兩種情況，所以不能一筆畫成。

相關(guān)名詞含義◎頂點與指數(shù)：設(shè)一個平面圖形是由有限個點及有限條弧組成的，這些點稱為圖形的頂點，從任一頂點引出的該圖形的弧的條數(shù)，稱為這個頂點的指數(shù)。

◎奇頂點：指數(shù)為奇數(shù)的頂點。

◎偶頂點：指數(shù)為偶數(shù)的頂點

歐拉圖先定義能一筆畫出并回到起點的圖為歐拉圖，連通就是說任意兩個節(jié)點之間可以找到一條連接它們的線。這個要求看來很重要，直觀方法中與這一點對應(yīng)的是說原圖本身不能是分成多個的。

設(shè)G為一歐拉圖，那么G顯然是連通的。另一方面，由于G本身為一閉路徑，它每經(jīng)過一個頂點一次，便給這一頂點增加度數(shù)2，因而各頂點的度均為該路徑經(jīng)歷此頂點的次數(shù)的兩倍，從而均為偶數(shù)。反之，設(shè)G連通，且每個頂點的度均為偶數(shù)，欲證G為一歐拉圖。為此，對G的邊數(shù)歸納。當(dāng)m = 1時，G必定為單結(jié)點的環(huán)，顯然這時G為歐拉圖。設(shè)邊數(shù)少于m的連通圖，在頂點度均為偶數(shù)時必為歐拉圖，現(xiàn)考慮有m條邊的圖G。設(shè)想從G的任一點出發(fā)，沿著邊構(gòu)畫，使筆不離開

圖且不在構(gòu)畫過的邊上重新構(gòu)畫。由于每個頂點都是偶數(shù)度，筆在進(jìn)入一個結(jié)點后總能離開那個結(jié)點，除非筆回到了起點。在筆回到起點時，它構(gòu)畫出一條閉路徑，記為H。從圖G中刪去H的所有邊，所得圖記為G’，G’未必連通，但其各頂點的度數(shù)仍均為偶數(shù)．考慮G的各連通分支，由于它們都連通，頂點度數(shù)均為偶數(shù)，而邊數(shù)均小于m，因此據(jù)歸納假設(shè)，它們都是歐拉圖。此外，由于G連通，它們都與H共有一個或若干個公共頂點，因此，它們與H一起構(gòu)成一個閉路徑。這就是說，G是一個歐拉圖。

一筆畫定理1736年，歐拉證實：七橋問題的走法根本不存在。同時，他發(fā)表了“一筆畫定理”：一個圖形要能一筆畫完成必須符合兩個條件，即圖形是封閉聯(lián)通的和圖形中的奇點（與奇數(shù)條邊相連的點）個數(shù)為0或2。歐拉的研究開創(chuàng)了數(shù)學(xué)上的新分支――拓?fù)鋵W(xué)的先聲。

本詞條內(nèi)容貢獻(xiàn)者為:

劉軍 - 副研究員 - 中國科學(xué)院工程熱物理研究所