-
一筆畫問題
鎖定
- 中文名
- 一筆畫問題
- 別 名
- 圖論
- 提出者
- 歐拉
- 適用領域
- 幾何畫圖領域
- 應用學科
- 數學
一筆畫問題定義
也就是“一筆畫”。一筆畫圖形的必要條件是:奇點數目是0或者2。概述圖⑴的“七橋問題”A,B,C,D都是奇節點,數目是4,所以不能夠“一筆畫”。 我們把節點轉換回來,成為“節面”(區域),來考慮“一筆畫”。
[1]
一筆畫問題例子
在平面中,4個或者4個以下的區域可以構成兩兩相連的區域,可以一筆畫。概述圖⑵。每個區域必須是單連通的,就是一個區域不能夠是分成2塊或者2塊以上。概述圖⑶就不是單連通的。這是著名的四色猜想。大家知道,平面上不可能有兩兩相通的5個區域。緊緻封閉平面,在一個輪胎狀的表面,7個或者7個以下的區域可以構成兩兩相連的區域。可以“一筆劃”。把圖(A)上下對摺以後,再左右對摺,形成一個輪胎狀,7個區域兩兩相連。
兩兩相連的區域可以不經過其它區域到達任何一個區域。P。J希伍德以畢生精力研究四色定理,並且證明了5色定理,稀伍德考察了一般曲面着色問題提出一個推測:在有P>1個洞的封閉曲面上,足以為任何地圖着色的最小數等於(左圖上下對摺再左右對摺就是一個輪胎,7個區域兩兩相連,可以一筆畫)。
一筆畫問題一筆畫的規律
數學家歐拉找到一筆畫的規律是:
⒉凡是隻有兩個奇點的連通圖(其餘都為偶點),一定可以一筆畫成。畫時必須把一個奇點為起點,另一個奇點終點。
⒊其他情況的圖都不能一筆畫出。(有偶數個奇點除以二可以算出此圖至少需幾筆畫成。)
比如附圖:(a)為⑴情況,因此可以一筆畫成;(b)(c)(d)則沒有符合以上兩種情況,所以不能一筆畫成。
一筆畫問題相關名詞含義
◎奇頂點:指數為奇數的頂點。
◎偶頂點:指數為偶數的頂點
一筆畫問題歐拉圖
先定義能一筆畫出並回到起點的圖為歐拉圖,連通就是説任意兩個節點之間可以找到一條連接它們的線。這個要求看來很重要,直觀方法中與這一點對應的是説原圖本身不能是分成多個的。
設G為一歐拉圖,那麼G顯然是連通的。另一方面,由於G本身為一閉路徑,它每經過一個頂點一次,便給這一頂點增加度數2,因而各頂點的度均為該路徑經歷此頂點的次數的兩倍,從而均為偶數。反之,設G連通,且每個頂點的度均為偶數,欲證G為一歐拉圖。為此,對G的邊數歸納。當m = 1時,G必定為單結點的環,顯然這時G為歐拉圖。設邊數少於m的連通圖,在頂點度均為偶數時必為歐拉圖,現考慮有m條邊的圖G。設想從G的任一點出發,沿着邊構畫,使筆不離開
圖且不在構畫過的邊上重新構畫。由於每個頂點都是偶數度,筆在進入一個結點後總能離開那個結點,除非筆回到了起點。在筆回到起點時,它構畫出一條閉路徑,記為H。從圖G中刪去H的所有邊,所得圖記為G’,G’未必連通,但其各頂點的度數仍均為偶數.考慮G的各連通分支,由於它們都連通,頂點度數均為偶數,而邊數均小於m,因此據歸納假設,它們都是歐拉圖。此外,由於G連通,它們都與H共有一個或若干個公共頂點,因此,它們與H一起構成一個閉路徑。這就是説,G是一個歐拉圖。
一筆畫問題一筆畫定理
1736年,歐拉證實:七橋問題的走法根本不存在。同時,他發表了“一筆畫定理”:一個圖形要能一筆畫完成必須符合兩個條件:
- 圖形是聯通的;
- 圖形中的奇點(與奇數條邊相連的點)個數為0或2;
歐拉的研究開創了數學上的新分支――圖形與幾何拓撲。