圖論中七橋問(wèn)題的算法與思考

王偉業(yè) 路宇 李曉寒

摘要：圖論誕生于七橋問(wèn)題。數(shù)學(xué)家歐拉提出并解決了七橋問(wèn)題。七橋問(wèn)題運(yùn)用到的數(shù)學(xué)思想和解決問(wèn)題的方法值得學(xué)習(xí)和借鑒。

關(guān)鍵詞：圖論 七橋問(wèn)題 歐拉

一、問(wèn)題描述

18世紀(jì)的東普魯士有一座哥尼斯堡城（現(xiàn)在叫加里寧格勒，在波羅的海南岸），城中有一座島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個(gè)城市分為北區(qū)、東區(qū)、南區(qū)和島區(qū)四個(gè)區(qū)域，全城共有七座橋?qū)⑺膫€(gè)城區(qū)連接起來(lái)。于是，有一個(gè)有趣的問(wèn)題：一個(gè)人能否在一次步行中經(jīng)過(guò)全部的七座橋后回到起點(diǎn)，且每座橋只經(jīng)過(guò)一次。

二、問(wèn)題求解

首先，把實(shí)際問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型，如下圖，ABCD分別為城區(qū)和島區(qū)，每條線代表一座橋，問(wèn)題就轉(zhuǎn)化為：求一條回路，每條邊經(jīng)過(guò)一次且僅此一次。

首先定義“度”的概念。假設(shè)有一條路線由A到B，則A的出度為1，B的入度為1。度為入度+出度。于是對(duì)于這個(gè)問(wèn)題，求一條回路，每條邊經(jīng)過(guò)一次且僅此一次，則說(shuō)明ABCD四個(gè)點(diǎn)，每個(gè)點(diǎn)的度都為偶數(shù)，且各點(diǎn)的入度和出度相等。而對(duì)于上圖，各點(diǎn)的邊數(shù)都為奇數(shù)次，而由各邊僅經(jīng)過(guò)一次可得各點(diǎn)的度都為奇數(shù)，故七橋問(wèn)題無(wú)解。

三、問(wèn)題思考

在18世紀(jì)初，科學(xué)發(fā)展水平還不高的時(shí)期，人們看到這個(gè)問(wèn)題都會(huì)想要通過(guò)窮舉法來(lái)找出一條符合要求的回路，而回路一共有成千上萬(wàn)條，通過(guò)窮舉法找到回路或者說(shuō)明這個(gè)問(wèn)題無(wú)解顯然不現(xiàn)實(shí)。歐拉作為一名數(shù)學(xué)家，看到這個(gè)問(wèn)題之后，首先想到把島看為一個(gè)點(diǎn)，把橋看成是一條線，這樣就把實(shí)際的七橋問(wèn)題抽象轉(zhuǎn)化成了一張圖，這種建模的思想十分值得我們學(xué)習(xí)。七橋問(wèn)題也為后來(lái)圖論這門(mén)學(xué)科的誕生奠定了基礎(chǔ)。

在處理很多實(shí)際問(wèn)題的時(shí)候，我們要養(yǎng)成建模的思維，把實(shí)際問(wèn)題抽象成數(shù)學(xué)模型，然后運(yùn)用理論知識(shí)，解決問(wèn)題。在解決一個(gè)問(wèn)題的時(shí)候，擁有一個(gè)創(chuàng)造性的思維，可以把問(wèn)題大大簡(jiǎn)化，事半功倍。

牛頓說(shuō)：“如果我看得更遠(yuǎn)一點(diǎn)的話，是因?yàn)槲艺驹诰奕说募绨蛏??！痹谶^(guò)去科學(xué)技術(shù)不發(fā)達(dá)的時(shí)代，沒(méi)有很多文獻(xiàn)資料可以參考，歐拉等人做出的貢獻(xiàn)是開(kāi)創(chuàng)性的，正是這些開(kāi)創(chuàng)性的成就，才使得我們有機(jī)會(huì)站在巨人的肩膀上，做出更多的研究?，F(xiàn)在圖論這門(mén)學(xué)科已經(jīng)發(fā)展出了拓?fù)鋱D論、結(jié)構(gòu)圖論、幾何圖論、代數(shù)圖論等各個(gè)分支，而這些高深的研究都起源于歐拉開(kāi)創(chuàng)性的思想。放到現(xiàn)在，我們遇到問(wèn)題，肯定會(huì)想到建模，但是當(dāng)時(shí)，沒(méi)有人能想到，而歐拉想到了，并解決了他，為后世圖論研究奠定了基礎(chǔ)。而現(xiàn)在科學(xué)技術(shù)的重大進(jìn)步，缺少的可能就是那創(chuàng)造性的思維。所以說(shuō)，遇到問(wèn)題，不拘泥于一成不變的方法，換一種思想，更科學(xué)地思考，問(wèn)題可能就迎刃而解了。