高中印

(承德民族師專 數(shù)學(xué)與計算機系，河北 承德 067000)

用數(shù)學(xué)建模方法解決哥尼斯堡七橋問題

高中印

(承德民族師專 數(shù)學(xué)與計算機系，河北 承德 067000)

作者介紹了七橋問題的由來，以及用數(shù)學(xué)建模方法來解決七橋問題。這為我們中學(xué)數(shù)學(xué)建模提供了又一經(jīng)典范例。

七橋問題；問題解決；經(jīng)典范例

數(shù)學(xué)建模方法是把實際問題抽象成數(shù)學(xué)模型，也就是把實際問題轉(zhuǎn)化成數(shù)學(xué)問題，然后再用數(shù)學(xué)的方法加以解決。哥尼斯堡七橋問題的研究就是數(shù)學(xué)建模中的一個經(jīng)典。

一、哥尼斯堡七橋問題的由來

哥尼斯堡就是現(xiàn)在的俄羅斯的加里寧格勒。哥尼斯堡在第二次世界大戰(zhàn)前屬于德國，是東普魯士的首府，在歷史上，哥尼斯堡的歸屬曾發(fā)生過幾次變化。二戰(zhàn)結(jié)束后，根據(jù)雅爾塔和波斯坦協(xié)議，東普魯士部分領(lǐng)土劃歸蘇聯(lián)，是蘇聯(lián)作為戰(zhàn)勝國享受的戰(zhàn)利品。蘇聯(lián)把哥尼斯堡更名為加里寧格勒。斯大林沒有把加里寧格勒劃入剛剛并如蘇聯(lián)的立陶宛，而是劃入俄羅斯聯(lián)邦。加里寧格勒風(fēng)景秀麗，氣候宜人。這里有著豐富的自然資源，是重要的軍事基地，也是重要的海運港口。1991年蘇聯(lián)解體，波羅的海周邊三國的立陶宛、拉脫維亞和愛沙尼亞獨立，加里寧格勒就變成了俄羅斯的一塊飛地。

普萊格爾河（Pregel）穿過美麗的哥尼斯堡城。普萊格爾河有兩個支流，在城市中心匯成大河，中間是島區(qū)，人們在河上建起了七座橋，使這里成為風(fēng)景優(yōu)美的人間仙境，如圖1所示。

由于島上有古老的哥尼斯堡大學(xué)，有知名的教堂，有大哲學(xué)家康德的墓地和塑像，因此城中的居民，尤其是大學(xué)生們經(jīng)常到河岸和上橋散步。在十八世紀(jì)初，有一天，有人突發(fā)奇想：如何才能走過七座橋，而每座橋都只能經(jīng)過一次，最后又回到原來的出發(fā)點？當(dāng)?shù)氐娜藗冮_始沉迷于這個問題，在橋上來來回回不知走了多少次，然而卻始終不得其解，這就是著名的哥尼斯堡七橋問題的由來。

二、大數(shù)學(xué)家歐拉的數(shù)學(xué)建模

哥尼斯堡七橋問題看起來似乎很簡單，其實很多人經(jīng)過多次嘗試，卻始終沒有找到答案。這個問題很快傳到了歐洲，成了著名的數(shù)學(xué)難題。

大數(shù)學(xué)家歐拉（Euler）此時受俄國之邀，正在圣彼得堡科學(xué)院做研究。他的德國朋友告訴了他七橋問題，引起了歐拉的極大興趣。他想：經(jīng)過這么多人的努力都找不到不重復(fù)的一次走完七座橋的路徑，會不會是這樣的走法根本不存在？但是這只是個猜想，還需要證明。

歐拉首先想到的是用窮舉法，就是把所有的走法都一一列出來，然后再一個一個的驗證是否可行。但是他馬上發(fā)現(xiàn)這樣做太麻煩了，因為對七座橋的不同走法就有7！=5040種，逐一檢驗太耗時費力了，況且這樣的方法沒有通用性。如果橋的位置或橋的數(shù)量發(fā)生變化，豈不又得重新檢驗？看來此法不可行。

經(jīng)過反復(fù)思考，歐拉想到：島的形狀、大小、以及橋的長短、寬窄并不影響結(jié)果，位置才是最重要的。于是他聯(lián)想到了萊布尼茲(Leibniz)的位置幾何學(xué)，既然陸地是橋梁的連接地點，不妨把圖中被河隔開的4塊陸地看成4個點，7座橋看成7條連接這4個點的線，這樣將圖形簡化，于是就畫了如圖2的圖形。

七橋問題就相當(dāng)于一筆畫出此圖形的問題。這是把陸地（平面）用點來表示，把橋用線來表示。多么美妙的構(gòu)思?。∵@就是數(shù)學(xué)大師歐拉對七座橋問題建立起來的數(shù)學(xué)模型。

三、七橋問題的最終解決

通過數(shù)學(xué)建模，已經(jīng)把實際問題轉(zhuǎn)化成了數(shù)學(xué)問題。這時歐拉注意到，如果一個圖形能一筆畫成，那么除去起點和終點外，其他的點都是經(jīng)過點。而經(jīng)過點是有進(jìn)有出的點，即有一條線進(jìn)這個點，就一定有一條線出這個點。不可能有進(jìn)無出，如果有進(jìn)無出，它就是終點；也不可能有出無進(jìn)，如果有出無進(jìn)，它就是起點。因此，在經(jīng)過點進(jìn)出的線總數(shù)應(yīng)該是偶數(shù)。我們稱在一個點進(jìn)出線的總數(shù)是偶數(shù)的點為偶點；總數(shù)為奇數(shù)的點稱為奇點。如果起點和終點是同一個點，那么它也屬于有進(jìn)有出的點，它也是偶點，這樣圖上的點全是偶點。如果起點和終點不是同一個點，那么它們必定是奇點。因此，能夠一筆畫的圖形最多只有兩個奇點。

1736年，歐拉證明了自己的猜想，一次不重復(fù)走完七座橋是根本不可能的。隨即他發(fā)表了“一筆畫定理”：

一個圖形要能一筆畫完，必須符合以下兩個條件：

（1）圖形是封閉連通的；

（2）圖形中的奇點個數(shù)為0或2；

七橋問題中的四個點全是奇點，當(dāng)然不能一筆畫，即不可能一次無重復(fù)地走完七座橋。一般地說，如果圖中的點全是偶點，那么可以任意選擇一個點作為起點，當(dāng)然終點與起點重合，能一筆畫成；如果圖中有兩個奇點，那么可以任意選一個奇點作為起點，另一個奇點為終點，可以一筆畫成。

歐拉的這個研究成果，開創(chuàng)了圖論和拓?fù)鋵W(xué)這兩門新的學(xué)科。這兩門學(xué)科在計算機科學(xué)中有著廣泛的應(yīng)用。由此可見，只要善于用數(shù)學(xué)的眼光、數(shù)學(xué)的方法去觀察事物，分析問題，就能把生活中的一些實際問題轉(zhuǎn)化為數(shù)學(xué)問題，并用數(shù)學(xué)的方法來處理和解決。歐拉用數(shù)學(xué)建模的方法來解決七橋問題，可以說為我們中學(xué)數(shù)學(xué)建模提供了又一經(jīng)典范例。

[1]姜啟源.數(shù)學(xué)建模[M].北京：高等教育出版社，1993.

[2]唐越橋.中學(xué)數(shù)學(xué)創(chuàng)新實驗[M].南寧：廣西教育出版社，2006.

[3]李文林.數(shù)學(xué)史[M].北京：高等教育出版社，2004.

O12

A

1005-1554（2010）02-0014-02

2010-02-05

高中?。?956-），男，河北承德人，承德民族師專數(shù)學(xué)與計算機系教授。