請問:一筆畫問題的原理是什麼?

同上

請問:一筆畫問題的原理是什麼?

到底是什麼哩?

已更新項目:

應該是說規律啦~

1 個解答

評分
  • 9 年前
    最佳解答

    一筆畫定理對於一筆畫問題,有兩個判斷的準則,它們都由歐拉提出並證明[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 條鏈,則由定理一知,每條鏈中只有兩個奇頂點,於是

    圖片參考:http://bits.wikimedia.org/skins-1.18/common/images...

    圖二:儘管按照中文書寫習慣「串」字不止一筆,但它可以一筆寫成。[編輯]七橋問題右圖一是七橋問題抽象化後得到的模型,由四個頂點和七條邊組成。注意到四個頂點全是奇頂點,由定理一可知無法一筆畫成。[編輯]一個可以一筆畫的例子圖二是中文「串」字抽象化後得到的模型。由於只有最上方和最下方的頂點是奇頂點,由定理一知它可以一筆畫成。

還有問題?馬上發問,尋求解答。