七橋問題
歐拉是這樣解決問題的:既然陸地是橋梁的連接地點,不妨把圖中被河隔開的陸地看成4個點,7座橋表示成7條連接這4個點的線,如圖所示。于是“七橋問題”就等價于下圖中所畫圖形的一筆畫問題了。
首先,它必須是連在一起的,也就是說,圖中的任何兩個點都由圖中的線連接,我們稱之為連通的。
其次,如果一個圖能一筆畫成,那么一定有一個起點開始畫,也有一個終點。圖上其它的點是“過路點”——畫的時候要經(jīng)過它。
現(xiàn)在看“過路點”具有什么性質(zhì)。它應(yīng)該是“有進(jìn)有出”的點,有一條邊進(jìn)這點,那么就要有一條邊出這點,不可能是有進(jìn)無出,如果有進(jìn)無出,它就是終點,也不可能有出無進(jìn),如果有出無進(jìn),它就是起點。因此,在“過路點”進(jìn)出的邊總數(shù)應(yīng)該是偶數(shù)。
因此一筆畫問題與經(jīng)過點的線的條數(shù)有關(guān)系,為方便起見,若與一點相連的線的條數(shù)為偶數(shù),則稱此點為偶點。
由上可知,“過路點”是偶點。同理,如果起點和終點是同一點,那么它也是屬于“有進(jìn)有出”的點,因此必須是偶點,這樣圖上全體點都是偶點。如果起點和終點不是同一點,那么它們必須是奇點,因此這個圖最多只能有二個奇點。
最后我們可以確定,圖能一筆畫的兩個條件:1、圖是連通的,2、圖中的奇點數(shù)為0或2。
事實上,中國民間很早就流傳著這種一筆畫的游戲,從長期實踐的經(jīng)驗,人們知道如果圖的點全部是偶點,可以任意選擇一個點做起點,一筆畫成。如果是有二個奇點的圖形,那么就選一個奇點做起點以順利的一筆畫完??上У氖牵艜r候沒有人對它重視,沒有數(shù)學(xué)家對它進(jìn)行經(jīng)驗總結(jié),以及加以研究。
現(xiàn)在對照七橋問題的圖,所有的頂點都是奇點,共有四個,所以這個圖肯定不能一筆畫成。后來,在普萊格爾河上又架起了一座鐵路橋。這座橋建成后,人們又想起了那個有趣的問題:如今八座橋可一次不重復(fù)地走過八座橋?如今七座橋只剩下三座——密橋、高橋和木橋。一座新的跨河大橋已建成,它完全跨國內(nèi)福夫島,但導(dǎo)游們?nèi)韵蛴慰椭v述七橋的故事,甚至有些導(dǎo)游聲稱問題仍未解決,以留給游客去遐想
|