【背景】
一筆畫問題,最早起源于18世紀時,東普魯士的首府 —— 哥尼斯堡(也就是現在俄羅斯的加裡甯格勒)。在當地,有一條河叫做普雷格河,這條河與它的兩條支流,将這座曆史名城分為了4個區域。我們通過簡化圖可以觀察到一共有7座橋橫跨在河上,其中5座橋連接河中心島A。
七橋問題
當時的居民便提出這樣的一個問題:能否在不重複、隻走一遍的前提下,經過所有的橋?許多人都進行了嘗試,但終究還是以失敗結束。
後來有人找到了歐拉,想請歐拉幫忙解決。在1736年,歐拉通過自己的研究,将其轉化為“一筆畫問題”,并将自己的研究,總結歸納出“一筆畫定理”,從而證實七橋問題的走法根本不存在。
通過此事件,歐拉的研究也開創了數學上的新分支――圖論。
【概念解釋】
奇點:如果該點處的分支數為奇數,就叫做奇點
偶點:如果該點處的分支數為偶數,就叫做偶點
七橋問題簡化圖
圖中的點A,C,D有三個分支,點B有5個分支,都是奇數,所以它們都是奇點。
【一筆畫定理】
一個圖形要能一筆畫完成必須符合兩個條件:
1.圖形是連通的;
2.圖形中的奇點(與奇數條邊相連的點)個數為0或2;
(1)情況一:奇點的個數為0
這時所有的點都是偶點,通過每個點的分支線都是有進有出,并且進出的次數相等。并且發現起筆點也就是停筆點。
圖中的每個點都是偶點,我選擇從A出發,最後的停筆的點也是點A。
(2)情況二:奇點的個數是2
起筆點與停筆點并不是同一個點,而且必須以一個奇點為起筆點,而另一個奇點就會是停筆點。
圖中的點A,B都是奇點,我們可以從A出發試試,看看最後的停筆點是不是B?
【延伸】當奇點數大于2時,是不能一筆畫出來的,如果含有2n個奇點的圖形,需要n筆畫出。
七橋問題
我們前面分析,七橋問題中的四個點都是奇點,所以需要4÷2=2(筆)畫出。
【練習】
練習1
練習2
練習3
練習4
,
更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!