[背景]

18世紀(jì)始于東普魯士首都——科尼斯堡(現(xiàn)在是俄羅斯的加里寧格勒)的筆畫問題。

在當(dāng)?shù)?，有一條河叫做普雷格河，這條河與它的兩條支流，將這座歷史名城分為了4個(gè)區(qū)域。我們通過簡化圖可以觀察到一共有7座橋橫跨在河上，其中5座橋連接河中心島A。

七橋問題

當(dāng)時(shí)的居民便提出這樣的一個(gè)問題：能否在不重復(fù)、只走一遍的前提下，經(jīng)過所有的橋？許多人都進(jìn)行了嘗試，但終究還是以失敗結(jié)束。

后來有人找到了歐拉，想請歐拉幫忙解決。在1736年，歐拉通過自己的研究，將其轉(zhuǎn)化為“一筆畫問題”，并將自己的研究，總結(jié)歸納出“一筆畫定理”，從而證實(shí)七橋問題的走法根本不存在。

通過此事件，歐拉的研究也開創(chuàng)了數(shù)學(xué)上的新分支――圖論。

【概念解釋】

奇點(diǎn)：如果該點(diǎn)處的分支數(shù)為奇數(shù)，就叫做奇點(diǎn)

偶點(diǎn)：如果該點(diǎn)處的分支數(shù)為偶數(shù)，就叫做偶點(diǎn)

七橋問題簡化圖

圖中的點(diǎn)A，C，D有三個(gè)分支，點(diǎn)B有5個(gè)分支，都是奇數(shù)，所以它們都是奇點(diǎn)。

【一筆畫定理】

一個(gè)圖形要能一筆畫完成必須符合兩個(gè)條件:

1.圖形是連通的;

2.圖形中的奇點(diǎn)（與奇數(shù)條邊相連的點(diǎn)）個(gè)數(shù)為0或2；

（1）情況一：奇點(diǎn)的個(gè)數(shù)為0

這時(shí)所有的點(diǎn)都是偶點(diǎn)，通過每個(gè)點(diǎn)的分支線都是有進(jìn)有出，并且進(jìn)出的次數(shù)相等。并且發(fā)現(xiàn)起筆點(diǎn)也就是停筆點(diǎn)。

圖中的每個(gè)點(diǎn)都是偶點(diǎn)，我選擇從A出發(fā)，最后的停筆的點(diǎn)也是點(diǎn)A。

（2）情況二：奇點(diǎn)的個(gè)數(shù)是2

起筆點(diǎn)與停筆點(diǎn)并不是同一個(gè)點(diǎn)，而且必須以一個(gè)奇點(diǎn)為起筆點(diǎn)，而另一個(gè)奇點(diǎn)就會是停筆點(diǎn)。

圖中的點(diǎn)A，B都是奇點(diǎn)，我們可以從A出發(fā)試試，看看最后的停筆點(diǎn)是不是B？

【延伸】當(dāng)奇點(diǎn)數(shù)大于2時(shí)，是不能一筆畫出來的，如果含有2n個(gè)奇點(diǎn)的圖形，需要n筆畫出。

七橋問題

我們前面分析，七橋問題中的四個(gè)點(diǎn)都是奇點(diǎn)，所以需要4÷2=2（筆）畫出。

【練習(xí)】

練習(xí)1

練習(xí)2

練習(xí)3

練習(xí)4