一筆畫問題,最少幾筆畫一筆畫問題要圖和解釋

2021-03-10 07:20:32 字數 3726 閱讀 8346

1樓:邴丹郭衣

第一個圖有6個奇點,不能一筆畫,最少要畫6÷2=3筆;

第二個圖全是偶點,可以一筆畫;

第三個圖只有內2個奇點可以一筆畫;

第四個圖不是連通圖,不能一筆畫出.它共9部分,每部分都可一筆畫出,至少需要9筆;

第五個圖是連通圖,有2個奇點可以一筆畫;

第六個圖只有4個奇點,不能一筆畫,最少要畫4÷2=2筆;

能一筆畫的圖形:第

二、三、五個圖形.

不能一筆畫的圖形:第一個圖形,至少需3筆;第容四個圖形,需9筆;第六個圖形,至少需要2筆.

2樓:第二把刷子

1。凡是來由偶點

組成的連通圖,一自定可以一筆畫成。畫時可以把任一偶點為起點,最後一定能以這個點為終點畫完此圖。

2。凡是隻有兩個奇點的連通圖(其餘都為偶點),一定可以一筆畫成。畫時必須把一個奇點為起點,另一個奇點終點。

3。其他情況的圖都不能一筆畫出。奇點數除以二便可算出此圖需幾筆畫成。

3樓:匿名使用者

一筆畫當然是一筆。圖形或漢字求同或求異時用到一筆畫來解題。

一筆畫問題 要圖和解釋

4樓:洪範周

一筆畫問題是圖論中一個著名的問題。一筆畫問題起源於柯尼斯堡七橋問題。數學家尤拉在他2023年發表的**《柯尼斯堡的七橋》中不僅解決了七橋問題,也提出了一筆畫定理,順帶解決了一筆畫問題[1]。

一般認為,尤拉的研究是圖論的開端。

與一筆畫問題相對應的一個圖論問題是哈密頓問題。

目錄 [隱藏]

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]哈密頓問題由哈密頓在2023年首次提出,至今尚未完全解決[2]。

[編輯] 參見

柯尼斯堡七橋問題

哈密爾頓問題

樹 (圖論)

中國郵遞員問題

[編輯] 參考**

^ 1.0 1.1 1.

2 ja*** heine bar***t, 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 詳細的證明

^ 尤拉圖和哈密頓圖

5樓:劉兵

2023年,尤拉在交給彼得堡科學院的《哥尼斯堡7座橋》的**報告中,闡述了他的解題方法。他的巧解,為後來的數學新分支——拓撲學的建立奠定了基礎。 七橋問題和尤拉定理。

尤拉通過對七橋問題的研究,不僅圓滿地回答了哥尼斯堡居民提出的問題,而且得到並證明了更為廣泛的有關一筆畫的三條結論,人們通常稱之為尤拉定理。對於一個連通圖,通常把從某結點出發一筆畫成所經過的路線叫做尤拉路。人們又通常把一筆畫成回到出發點的尤拉路叫做尤拉回路。

具有尤拉回路的圖叫做尤拉圖。 此題被人教版小學數學第十二冊書收錄.在95頁。

此題也被人教版初中第一冊收錄.在121頁. 一筆劃:■⒈凡是由偶點組成的連通圖,一定可以一筆畫成。畫時可以把任一偶點為起點,最後一定能以這個點為終點畫完此圖。

■⒉凡是隻有兩個奇點的連通圖(其餘都為偶點),一定可以一筆畫成。畫時必須把一個奇點為起點,另一個奇點終點。 ■⒊其他情況的圖都不能一筆畫出。

(奇點數除以二便可算出此圖需幾筆畫成。)

圖中哪些圖形可以一筆畫出,哪些不能?不能一筆畫出的圖形最少需要畫幾筆

6樓:夏戀時光

第一個圖有6個奇點,不能一筆畫,最少要畫6÷2=3筆;

第二個圖全是偶點,可以一筆畫;

第三個圖只有2個奇點可以一筆畫;

第四個圖不是連通圖,不能一筆畫出.它共9部分,每部分都可一筆畫出,至少需要9筆;

第五個圖是連通圖,有2個奇點可以一筆畫;

第六個圖只有4個奇點,不能一筆畫,最少要畫4÷2=2筆;

能一筆畫的圖形:第

二、三、五個圖形.

不能一筆畫的圖形:第一個圖形,至少需3筆;第四個圖形,需9筆;第六個圖形,至少需要2筆.

這個圖形怎麼一筆畫完,線不能重複

要判斷一個圖形是否能夠一筆畫,其方法如下 首先,檢查圖形是否連續,有無與其它部分斷開的圖形。其次逐個檢查所有圖形的中的交叉點,看每一個交叉點有幾條出去的線,如果是偶數條,稱為 偶點 如果是奇數條,則稱為 奇點 最後,如果全部交叉點均為偶點,則從任意一個點出發均可一筆畫出全部圖形。如果只有兩個奇點,則...

請問能否一筆畫出個六角形,一筆畫六邊形怎麼畫?

六角星是一筆畫不出來的,已經證明了。六角形肯定能。不知道這樣行不行 我把介面部分間距放大了 可以的 我估計你是問六角星的 不行.可以.先畫外面一圈,再畫裡面一圈 從兩個三角形的任何一個交點起筆就可以了,先畫一個三角形回到交點,在畫另外一個 從一個凹的地方起筆,畫外面的6個角,中間不畫,一圈畫完後,回...

怎麼才能一筆畫完這個圖形?從任何一處開始畫都行

這個圖形有四個奇點,所以不能一筆畫 要一筆畫則奇點數是0或2 畫不出。這是數學分支 拓撲學中很有名的哥德堡7橋問題。因為頂點個數為4是偶數,邊是為7是奇數,因此不能畫出,這個結論德國數學家尤拉在幾百年前已經證明。怎麼樣可以知道一個圖形可以一筆畫出來?判斷一個圖形可以一筆畫出來 判斷奇點的個數即可,要...