一筆畫問題（Eulerian graph）是圖論中一個著名的問題。一筆畫問題起源于哥尼斯堡七橋問題。數(shù)學(xué)家歐拉在他1736年發(fā)表的論文《哥尼斯堡的七橋》中不僅解決了七橋問題，也提出了一筆畫定理，并解決了一筆畫問題。
一筆畫問題的規(guī)律是凡是由偶點組成的連通圖，一定可以一筆畫成，畫時可以把任一偶點為起點，最后一定能以這個點為終點一筆畫完此圖，還有凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫成，畫時必須把一個奇點為起點，另一個奇點為終點。
一筆畫在生活中也有著重要的應(yīng)用，比如灑水車進行清洗馬路的工作，會設(shè)計一種科學(xué)的走法，使它既能完成灑水任務(wù)，又可以不重復(fù)地走過每條街道。
定義
眾所周知的“哥尼斯堡城‘七橋問題’”被大數(shù)學(xué)家長城歐拉開創(chuàng)了數(shù)學(xué)新分支-----圖論。也就是“一筆畫”。一筆畫圖形的必要條件是：奇點數(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ū)域。可以“一筆劃”。把圖（A）上下對折以后，再左右對折，形成一個輪胎狀，7個區(qū)域兩兩相連。
兩兩相連的區(qū)域可以不經(jīng)過其它區(qū)域到達任何一個區(qū)域。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ù)歸納。當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ù)度，筆在進入一個結(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ā)表了“一筆畫定理”：一個圖形要能一筆畫完成必須符合兩個條件，即圖形是連通的和圖形中的奇點（與奇數(shù)條邊相連的點）個數(shù)為0或2。歐拉的研究開創(chuàng)了數(shù)學(xué)上的新分支――圖形與幾何拓撲。
參考資料 >
數(shù)學(xué)趣覽| 圖論的誕生:哥尼斯堡七橋問題與一筆畫[轉(zhuǎn)自數(shù)學(xué)經(jīng)緯].湖南交通工程學(xué)院.2024-02-23
一筆畫問題 這幾張圖你能一筆連起來嗎?.科普中國網(wǎng).2024-02-22
【智閱數(shù)學(xué)】“歷史中的數(shù)學(xué)”系列故事(第17期).微信公眾平臺.2024-02-22