哥尼斯堡的七座橋

七橋.gif (10323 個位元組)

德國有一座小城名叫歌尼斯堡(Konigsberg),布勒格爾河橫貫整個城區,這河有兩分支,一名新河,一名舊河,他們在城中匯成一大河,河上建有七座橋。一個人是否能一次走遍這七座橋,而不重複,也不遺漏呢?
這個問題可以理解成,可否用一筆畫過這七座橋,而不重複路徑。
我們可以假設這路徑如下:

wpe11.jpg (5646 個位元組)

A、B、C、D四端點代表四塊陸地,端點之間的線段表示橋樑。尤拉研究過這個問題,他稱這些線段的匯合處之點為頂點。如果在一頂點上匯合的線段數目是偶數,稱為偶頂點。在一頂點上匯合的線段數目是奇數,稱為奇頂點。他證明了:如果整個線網不含有任何奇頂點或只含有兩個奇頂點的話,便可一筆畫出一個完整而不重複的路徑。也就是說,如果線網含有多於兩個奇頂點時,便不可能畫出一筆畫。
現在,你再想想看,一個人是否能一次走遍這七座橋,而不重複,也不遺漏呢?


Copyright © 1999昌爸工作坊 all rights reserved