圖論中七橋問題的算法與思考

王偉業 路宇 李曉寒

摘要：圖論誕生于七橋問題。數學家歐拉提出并解決了七橋問題。七橋問題運用到的數學思想和解決問題的方法值得學習和借鑒。

關鍵詞：圖論 七橋問題 歐拉

一、問題描述

18世紀的東普魯士有一座哥尼斯堡城（現在叫加里寧格勒，在波羅的海南岸），城中有一座島，普雷格爾河的兩條支流環繞其旁，并將整個城市分為北區、東區、南區和島區四個區域，全城共有七座橋將四個城區連接起來。于是，有一個有趣的問題：一個人能否在一次步行中經過全部的七座橋后回到起點，且每座橋只經過一次。

二、問題求解

首先，把實際問題轉化為數學模型，如下圖，ABCD分別為城區和島區，每條線代表一座橋，問題就轉化為：求一條回路，每條邊經過一次且僅此一次。

首先定義“度”的概念。假設有一條路線由A到B，則A的出度為1，B的入度為1。度為入度+出度。于是對于這個問題，求一條回路，每條邊經過一次且僅此一次，則說明ABCD四個點，每個點的度都為偶數，且各點的入度和出度相等。而對于上圖，各點的邊數都為奇數次，而由各邊僅經過一次可得各點的度都為奇數，故七橋問題無解。

三、問題思考

在18世紀初，科學發展水平還不高的時期，人們看到這個問題都會想要通過窮舉法來找出一條符合要求的回路，而回路一共有成千上萬條，通過窮舉法找到回路或者說明這個問題無解顯然不現實。歐拉作為一名數學家，看到這個問題之后，首先想到把島看為一個點，把橋看成是一條線，這樣就把實際的七橋問題抽象轉化成了一張圖，這種建模的思想十分值得我們學習。七橋問題也為后來圖論這門學科的誕生奠定了基礎。

在處理很多實際問題的時候，我們要養成建模的思維，把實際問題抽象成數學模型，然后運用理論知識，解決問題。在解決一個問題的時候，擁有一個創造性的思維，可以把問題大大簡化，事半功倍。

牛頓說：“如果我看得更遠一點的話，是因為我站在巨人的肩膀上。”在過去科學技術不發達的時代，沒有很多文獻資料可以參考，歐拉等人做出的貢獻是開創性的，正是這些開創性的成就，才使得我們有機會站在巨人的肩膀上，做出更多的研究。現在圖論這門學科已經發展出了拓撲圖論、結構圖論、幾何圖論、代數圖論等各個分支，而這些高深的研究都起源于歐拉開創性的思想。放到現在，我們遇到問題，肯定會想到建模，但是當時，沒有人能想到，而歐拉想到了，并解決了他，為后世圖論研究奠定了基礎。而現在科學技術的重大進步，缺少的可能就是那創造性的思維。所以說，遇到問題，不拘泥于一成不變的方法，換一種思想，更科學地思考，問題可能就迎刃而解了。