與壹筆畫問題相對應的壹個圖論問題是哈密頓問題。
目錄 [隱藏]
1 問題的提出
2 壹筆畫定理
2.1 定理壹
2.2 定理二
3 例子
3.1 七橋問題
3.2 壹個可以壹筆畫的例子
4 壹筆畫問題與哈密頓問題
5 參見
6 參考來源
[編輯] 問題的提出
壹筆畫問題是柯尼斯堡問題經抽象化後的推廣，是圖遍歷問題的壹種。在柯尼斯堡問題中，如果將橋所連接的地區視為點，將每座橋視為壹條邊，那麽問題將變成：對於壹個有著四個頂點和七條邊的連通圖 G(S,E)，能否找到壹個恰好包含了所有的邊，並且沒有重復的路徑。歐拉將這個問題推廣為：對於壹個給定的連通圖，怎樣判斷是否存在著壹個恰好包含了所有的邊，並且沒有重復的路徑？這就是壹筆畫問題。用圖論的術語來說，就是判斷這個圖是否是壹個能夠遍歷完所有的邊而沒有重復。這樣的圖現稱為歐拉圖。這時遍歷的路徑稱作歐拉路徑（壹個圈或者壹條鏈），如果路徑閉合（壹個圈），則稱為歐拉回路[1]。
壹筆畫問題的推廣是多筆畫問題，即對於不能壹筆畫的圖，探討最少能用多少筆來畫成。
[編輯] 壹筆畫定理
對於壹筆畫問題，有兩個判斷的準則，它們都由歐拉提出並證明[1]。
[編輯] 定理壹
有限圖 G 是鏈或圈的充要條件是：G為連通圖，且其中奇頂點的數目等於0或者2。有限連通圖 G 是圈當且僅當它沒有奇頂點[2]。
證明[2][3]：
必要性：如果壹個圖能壹筆畫成，那麽對每壹個頂點，要麽路徑中“進入”這個點的邊數等於“離開”這個點的邊數：這時點的度為偶數。要麽兩者相差壹：這時這個點必然是起點或終點之壹。註意到有起點就必然有終點，因此奇頂點的數目要麽是0，要麽是2。
充分性：
如果圖中沒有奇頂點，那麽隨便選壹個點出發，連壹個圈 C1。如果這個圈就是原圖，那麽結束。如果不是，那麽由於原圖是連通的，C1 和原圖的其它部分必然有公***頂點 s1。從這壹點出發，在原圖的剩余部分中重復上述步驟。由於原圖是有限圖，經過若幹步後，全圖被分為壹些圈。由於兩個相連的圈就是壹個圈，原來的圖也就是壹個圈了。
如果圖中有兩個奇頂點 u 和 v，那麽加多壹條邊將它們連上後得到壹個無奇頂點的有限連通圖。由上知這個圖是壹個圈，因此去掉新加的邊後成為壹條鏈，起點和終點是 u 和 v。
[編輯] 定理二
如果有限連通圖 G 有 2k 個奇頂點，那麽它可以用 k 筆畫成，並且至少要用 k 筆畫成[2]。
證明[2][3]：將這 2k 個奇頂點分成 k 對後分別連起，則得到壹個無奇頂點的有限連通圖。由上知這個圖是壹個圈，因此去掉新加的邊後至多成為 k 條鏈，因此必然可以用 k 筆畫成。但是假設全圖可以分為 q 條鏈，則由定理壹知，每條鏈中只有兩個奇頂點，於是 。因此必定要 k 筆畫成。
[編輯] 例子
圖壹：無法壹筆畫
圖二：盡管按照中文書寫習慣“串”字不止壹筆，但它可以壹筆寫成。[編輯] 七橋問題
右圖壹是七橋問題抽象化後得到的模型，由四個頂點和七條邊組成。註意到四個頂點全是奇頂點，由定理壹可知無法壹筆畫成。
[編輯] 壹個可以壹筆畫的例子
圖二是中文“串”字抽象化後得到的模型。由於只有最上方和最下方的頂點是奇頂點，由定理壹知它可以壹筆畫成。
[編輯] 壹筆畫問題與哈密頓問題
壹筆畫問題討論的是能否不重復地遍歷壹個圖的所有邊，至於其中有否頂點的遍歷或重復經過則沒有要求。哈密頓問題討論的則是頂點的遍歷：能否不重復地遍歷壹個圖的所有頂點？[4]哈密頓問題由哈密頓在1856年首次提出，至今尚未完全解決[2]。
[編輯] 參見
柯尼斯堡七橋問題
哈密爾頓問題
樹 (圖論)
中國郵遞員問題
[編輯] 參考來源
^ 1.0 1.1 1.2 Janet Heine Barnett, Early Writings on Graph Theory: Euler Circuits and The K?onigsberg Bridge Problem
^ 2.0 2.1 2.2 2.3 2.4 熊斌，鄭仲義，《圖論》，第四章，38-46，華東師範大學出版社。
^ 3.0 3.1 詳細的證明
^ 歐拉圖和哈密頓圖