關於奧數專題之一筆畫問題

歐拉的一筆畫原理是：

(1)一筆畫必須是連通的(圖形的各部分之間連接在一起)；

(2)沒有奇點的連通圖形是一筆畫，畫時可以以任一偶點為起點，最後仍回到這點；

(3)只有兩個奇點的連通圖形是一筆畫，畫時必須以一個奇點為起點，以另一個奇點為終點；

(4)奇點個數超過兩個的.圖形不是一筆畫。

利用一筆畫原理，七橋問題很容易解決。因為圖中A，B，C，D都是奇點，有四個奇點的圖形不是一筆畫，所以一個散步者不可能不重複地一次走遍這七座橋。

順便補充兩點：

(1)一個圖形的奇點數目一定是偶數。

因為圖形中的每條線都有兩個端點，所以圖形中所有端點的總數必然是偶數。如果一個圖形中奇點的數目是奇數，那麼這個圖形中與奇點相連接的端點數之和是奇數(奇數個奇數之和是奇數)，與偶點相連的線的端點數之和是偶數(任意個偶數之和是偶數)，於是得到所有端點的總數是奇數，這與前面的結論矛盾。所以一個圖形的奇點數目一定是偶數。

(2)有K個奇點的圖形要K÷2筆才能畫成。

例如：下頁左上圖中的房子共有B，E，F，G，I，J六個奇點，所以不是一筆畫。如果我們將其中的兩個奇點間的連線去掉一條，那麼這兩個奇點都變成了偶點，如果能去掉兩條這樣的連線，使圖中的六個奇點變成兩個，那麼新圖形就是一筆畫了。將線段GF和BJ去掉，剩下I和E兩個奇點(見右下圖)，這個圖形是一筆畫，再添上線段GF和BJ，共需三筆，即(6÷2)筆畫成。

一個K(K＞1)筆畫最少要添加幾條連線才能變成一筆畫呢？我們知道K筆畫有2K個奇點，如果在任意兩個奇點之間添加一條連線，那麼這兩個奇點同時變成了偶點。如左下圖中的B，C兩個奇點在右下圖中都變成了偶點。所以只要在K筆畫的2K個奇點間添加(K-1)筆就可以使奇點數目減少為2個，從而變成一筆畫。

到現在為止，我們已經學會了如何判斷一筆畫和多筆畫，以及怎樣添加連線將多筆畫變成一筆畫。

1.下列圖形分別是幾筆畫？怎樣畫？

2.能否用剪刀從左下圖中一次連續剪下三個正方形和兩個三角形？

3.從A點出發，走遍右上圖中所有的線段，再回到A點，怎樣走才能使重複走的路程最短？

4.如下圖所示，兩條河流的交匯處有兩個島，有七座橋連接這兩個島及河岸。問：一個散步者能否一次不重複地走遍這七座橋？