一筆畫問題

一筆畫問題

傳統意義上的幾何學是研究圖形的形狀大小等性質,而存在一些幾何問題,它們所研究的對象與圖形的形狀和線段的長短沒關係,而只和線段的數目和它們之間的連線關係有關,比如一筆畫問題就是如此。即平面上由曲線段構成的一個圖形能不能一筆畫成,使得在每條線段上都不重複。例如漢字“日”和“中”字都可一筆畫,而“田”和“目”則不能。兩兩相連區域可一筆畫,例如,平面4個區域兩兩相連區域可一筆劃;輪胎狀上7個兩兩相連區域可一筆畫;我們可以構造一個多維空間的無窮個兩兩相連區域一筆劃。

基本介紹

  • 中文名:一筆畫問題
  • 別稱:圖論
  • 提出者:歐拉
  • 套用學科:數學
  • 適用領域範圍:幾何畫圖領域
定義,例子,一筆畫的規律,相關名詞含義,歐拉圖,一筆畫定理,

定義

眾所周知的“哥尼斯堡城‘七橋問題’”被大數學家歐拉開創了數學新分支-----圖論。也就是“一筆畫”。一筆畫圖形的必要條件是:奇點數目是0或者2。圖⑴的“七橋問題”A,B,C,D都是奇節點,數目是4,所以不能夠“一筆畫”。 我們把節點轉換回來,成為“節面”(區域),來考慮“一筆畫”。
一筆畫問題
一筆畫問題

例子

在平面中,4個或者4個以下的區域可以構成兩兩相連的區域,可以一筆畫。圖⑵。每個區域必須是單連通的,就是一個區域不能夠是分成2塊或者2塊以上。圖⑶就不是單連通的。這是著名的四色猜想。大家知道,平面上不可能有兩兩相同的5個區域。緊緻封閉平面,在一個輪胎狀的表面,7個或者7個以下的區域可以構成兩兩相連的區域。可以“一筆劃”。把圖(A)上下對摺以後,再左右對摺,形成一個輪胎狀,7個區域兩兩相連。
兩兩相連的區域可以不經過其它區域到達任何一個區域。P。J希伍德以畢生精力研究四色定理,並且證明了5色定理,稀伍德考察了一般曲面著色問題提出一個推測:在有P>1個洞的封閉曲面上,足以為任何地圖著色的最小數等於(左圖上下對摺再左右對摺就是一個輪胎,7個區域兩兩相連,可以一筆畫)。
上下對摺再左右對摺成輪胎形狀圖A上下對摺再左右對摺成輪胎形狀圖A

一筆畫的規律

數學家歐拉找到一筆畫的規律是:
⒈凡是由偶點組成的連通圖,一定可以一筆畫成。畫時可以把任一偶點為起點,最後一定能以這個點為終點畫完此圖。
⒉凡是只有兩個奇點的連通圖(其餘都為偶點),一定可以一筆畫成。畫時必須把一個奇點為起點,另一個奇點終點。
⒊其他情況的圖都不能一筆畫出。(有偶數個奇點除以二便可算出此圖需幾筆畫成。)
比如附圖:(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。歐拉的研究開創了數學上的新分支――拓撲學的先聲。

相關詞條

熱門詞條

聯絡我們