習題解答

　　1.解：見下圖

　　過橋問題：

　　可否一次通過所有的橋

　　(每座橋只能走一次)

　　一筆畫問題：

　　可否一筆畫成圖形(筆不能抬起，不能重復)

　　2.解：見下兩圖，可知不能一次不重復地走遍所有的小橋，因為下右圖有4個奇點.

　　3.解：由于通過兩島之中任何一個島的橋的數目都是偶數，而通過兩岸的任一個岸的橋的數目都是奇數，這就表示由任一個岸出發，都存在一條路，使人們將所有的橋都只走一次而到達另外一個岸.畫出圖來就能一目了然了.見下圖.

　　因為圖中共有兩個奇點，且奇點均為岸，是一筆畫.

　　所以人們可以一次通過所有的橋，每座橋只走一次，由一岸到另一岸.

　　4.解：從入口進入售貨廳后，也就是從1號房間開始不能一次不重復地走遍各個門，因為雖然整個圖形(見下圖)只有2個奇點，但點1是偶點.

　　當出口在4號房間時，如再在1號和3號房間之間開一個門，則從1號房間開始后就能一次不重復地走遍各個門.因為點1變成了奇點，點4仍為奇點，而整個圖形只有2個奇點，因此可以從1號房間進，4號房間出.見下圖(進入售貨廳后先從1號房間進入3號房間即可).