哥尼斯堡七橋問(wèn)題

刁品泉

請(qǐng)你做下面的游戲：一筆畫(huà)出如圖1的圖形來(lái).規(guī)則：筆不離開(kāi)紙面，每根線都只能畫(huà)一次.這就是古老的民間游戲——一筆畫(huà).

你能畫(huà)出來(lái)嗎？如果你畫(huà)出來(lái)了，那么請(qǐng)你再看圖2能不能一筆畫(huà)出來(lái)？

雖然你動(dòng)了腦筋，但我相信你肯定不能一筆畫(huà)出來(lái)！

為什么我的語(yǔ)氣這么肯定？我們來(lái)分析一下圖2.我們把圖2看成是由點(diǎn)和線組成的一種集合.圖里直線的交點(diǎn)叫作頂點(diǎn)，聯(lián)結(jié)頂點(diǎn)的線叫作邊.這個(gè)圖是連通的，即任何兩個(gè)頂點(diǎn)之間都有邊.很顯然，圖中的頂點(diǎn)有兩類：一類是有偶數(shù)條邊連它的，另一類是有奇數(shù)條邊連它的.一個(gè)頂點(diǎn)如果有偶數(shù)條邊連它，這點(diǎn)就稱為偶點(diǎn)；如果有奇數(shù)條邊連它，就稱它為奇點(diǎn).我們知道，能一筆畫(huà)的圖形只有兩類：一類是所有的點(diǎn)都是偶點(diǎn).另一類是只有二個(gè)奇點(diǎn)的圖形.圖2有六個(gè)奇點(diǎn)，四個(gè)偶點(diǎn)，當(dāng)然不能一筆畫(huà)出來(lái)了.

為什么能一筆畫(huà)的圖形只有上述兩類呢？有關(guān)這個(gè)問(wèn)題的討論，要追溯到二百年前的一個(gè)著名問(wèn)題：哥尼斯堡七橋問(wèn)題.

18世紀(jì)東普魯士哥尼斯堡城（今俄羅斯加里寧格勒）的普萊格爾河，它有兩個(gè)支流，在城市中心匯成大河，中間是島區(qū)，河上有7座橋，將河中的兩個(gè)島和河岸聯(lián)結(jié)，如圖3所示.由于島上有古老的哥尼斯堡大學(xué)，有教堂，還有哲學(xué)家康德的墓地和塑像，因此城中的居民，尤其是大學(xué)生們經(jīng)常沿河過(guò)橋散步.漸漸地，愛(ài)動(dòng)腦筋的人們提出了一個(gè)問(wèn)題：一個(gè)散步者能否一次走遍7座橋，而且每座橋只許通過(guò)一次，最后仍回到起始地點(diǎn).這就是七橋問(wèn)題，一個(gè)著名的圖論問(wèn)題.

這個(gè)問(wèn)題看起來(lái)似乎很簡(jiǎn)單，然而許多人作過(guò)嘗試始終沒(méi)有能找到答案.因此，一群大學(xué)生就寫(xiě)信給當(dāng)時(shí)年僅20歲的大數(shù)學(xué)家歐拉.歐拉從千百人次的失敗，以深邃的洞察力猜想，也許根本不可能不重復(fù)地一次走遍這七座橋，并很快證明了這樣的猜想是正確的.歐拉是這樣解決問(wèn)題的：既然陸地是橋梁的連接地點(diǎn)，不妨把圖中被河隔開(kāi)的陸地看成4個(gè)點(diǎn)，7座橋表示成7條連接這4個(gè)點(diǎn)的線，如圖4所示.

于是“七橋問(wèn)題”就等價(jià)于圖5中所畫(huà)圖形的一筆畫(huà)問(wèn)題了.歐拉注意到，如果一個(gè)圖能一筆畫(huà)成，那么一定有一個(gè)起點(diǎn)開(kāi)始畫(huà)，也有一個(gè)終點(diǎn).圖上其他的點(diǎn)是“過(guò)路點(diǎn)”——畫(huà)的時(shí)候要經(jīng)過(guò)它.

現(xiàn)在看“過(guò)路點(diǎn)”具有什么性質(zhì).它應(yīng)該是“有進(jìn)有出”的點(diǎn)，有一條邊進(jìn)這點(diǎn)，那么就要有一條邊出這點(diǎn)，不可能是有進(jìn)無(wú)出，如果有進(jìn)無(wú)出，它就是終點(diǎn)，也不可能有出無(wú)進(jìn)，如果有出無(wú)進(jìn)，它就是起點(diǎn).因此，在“過(guò)路點(diǎn)”進(jìn)出的邊總數(shù)應(yīng)該是偶數(shù)，即“過(guò)路點(diǎn)”是偶點(diǎn).

如果起點(diǎn)和終點(diǎn)是同一點(diǎn)，那么它也是屬于“有進(jìn)有出”的點(diǎn)，因此必須是偶點(diǎn)，這樣圖上全體點(diǎn)都是偶點(diǎn).

如果起點(diǎn)和終點(diǎn)不是同一點(diǎn)，那么它們必須是奇點(diǎn)，因此，這個(gè)圖最多只能有兩個(gè)奇點(diǎn).

現(xiàn)在對(duì)照七橋問(wèn)題的圖，所有的頂點(diǎn)都是奇點(diǎn)，共有四個(gè)，所以這個(gè)圖肯定不能一筆畫(huà)成.

歐拉對(duì)“七橋問(wèn)題”的研究是圖論研究的開(kāi)始，同時(shí)也為拓?fù)鋵W(xué)的研究提供了一個(gè)初等的例子.

事實(shí)上，中國(guó)民間很早就流傳著這種一筆畫(huà)的游戲，從長(zhǎng)期實(shí)踐的經(jīng)驗(yàn)，人們知道如果圖的點(diǎn)全部是偶點(diǎn)，可以任意選擇一個(gè)點(diǎn)做起點(diǎn)，一筆畫(huà)成.如果是有兩個(gè)奇點(diǎn)的圖形，那么就選一個(gè)奇點(diǎn)做起點(diǎn)以順利地一筆畫(huà)完.可惜的是，古時(shí)候沒(méi)有人對(duì)它重視，沒(méi)有數(shù)學(xué)家對(duì)它進(jìn)行經(jīng)驗(yàn)總結(jié)，以及加以研究.

今天學(xué)習(xí)歐拉的成果不應(yīng)是單純把它作為數(shù)學(xué)游戲，重要的是應(yīng)該知道他怎樣把一個(gè)實(shí)際問(wèn)題抽象成數(shù)學(xué)問(wèn)題.研究數(shù)學(xué)問(wèn)題不應(yīng)該“為抽象而抽象”，抽象的目的是為了更好地、更有效地解決實(shí)際產(chǎn)生的問(wèn)題，歐拉對(duì)“七橋問(wèn)題”的研究就是值得我們學(xué)習(xí)的一個(gè)樣板.

（作者單位：江蘇省南師附中江寧分校）