蔡思明

1736年29歲的歐拉向圣彼得堡科學院遞交了《哥尼斯堡的七座橋》的論文，在解答問題的同時，開創(chuàng)了數學的一個新的分支——圖論.

一、哥尼斯堡七橋問題

哥尼斯堡在俄羅斯境內，曾是東普魯士的首府，現(xiàn)稱為加里寧格勒.哥尼斯堡是一座歷史名城，這里誕生和培養(yǎng)過許多偉大人物.哥尼斯堡城中有一條布勒格爾河，橫貫城中，如圖1所示.布勒格爾河有兩條支流，一條稱為新河，另一條叫做舊河，在城中心匯合成一條主流，在合流的地方有座河心島，這是城中繁華的商業(yè)中心.布勒格爾河將全城分成為四個地區(qū)：島區(qū)、北區(qū)、東區(qū)和南區(qū).人們在布勒格爾河上架了七座橋，其中五座將河島與河岸連接起來，另有兩座架在兩支流上.這一別致的橋群，吸引了眾多的哥尼斯堡居民和游人來此河邊散步或去島上買東西.

1735年，有幾名大學生寫信給當時正在俄國彼得堡科學院任職的天才數學家歐拉，請他幫助解決這個問題.歐拉并未輕視這個生活小問題，他似乎看到其中隱藏著某種新的數學方法.經過一年的研究，29歲的歐拉圓滿地解決了這一問題，并于1736年向彼得堡科學院遞交了一篇題為《哥尼斯堡的七座橋》的論文.

二、歐拉的解法

歐拉的答案是：想一次不重復地走過這七座橋是不可能的.那么歐拉是如何解決這個問題的呢？他用點A、B、C、D表示哥尼斯堡城的四個地區(qū)C（島區(qū)）、B（北區(qū)）、D（東區(qū)）、A（南區(qū)）;七座橋看成這四個點的連線，用1、2、3、4、5、6、7七個數字表示，如圖3所示.這樣“七橋問題”就轉化為“一筆畫”問題：否能一筆不重復地畫出過此七點的圖形.

假設可以畫出來，則圖形中必有一個起點和一個終點，如果這兩個點不重合，則與起點或終點相交的線都必須是奇數條（稱奇點），如果起點與終點重合，則與之相交的線必是偶數條（稱偶點），而除了起點與終點外的點也必是“偶點”.由對稱性可知由B或C為起點得到的結果是一樣的，若假設以A為起點和終點，則必有一離開線和對應的進入線，若我們定義進入A的線的條數為人度，離開線的條數為出度，與A有關的線的條數為4的度，則4的出度和入度是相等的，即4的度應該為偶數.即要使得從4出發(fā)問題有解，則4的度數應該為偶數，而實際上4的度數是5，為奇數，于是可知從4出發(fā)，問題是無解的.同時若從B或D出發(fā)，由于B、D的度數分別是3、3，都是奇數，即以之為起點，問題都是無解的.

由上述分析可知，如果一個圖形可以一筆畫出來，須滿足如下兩個條件：

（1）圖形必須是連通的，即圖中的任一點通過一些線一定能到達其他任意一點.

（2）圖中的“奇點”數只能是0或2.

我們也可依此來檢驗圖形是否可一筆畫出.回頭來看看“七橋問題”，圖3中的4個點全都是“奇點”，可知該圖不能“一筆畫出”，也就是不可能不重復地通過七座橋.歐拉發(fā)表的這一結果，震驚了當時的數學界，人們無不贊嘆這位數學天才的能力！

三、對“七橋問題”的引申推廣

1.過了許多年，河上又架起了第八座橋——鐵路橋，如圖4所示.這座橋的建成，使人們又想起了那個有趣的“七橋問題”.那么，可一次不重復走過八座橋嗎？從圖5的簡化模型可知“奇點”只有兩個（D點和C點），所以可以一次不重復地走過八座橋.

2.若有一條河，河中心有兩個河心島，有十五座橋把這兩個島和兩岸連接起來，如圖6所示，問能否不重復地通過這十五座橋？按歐拉的方法，把圖抽象成如圖7所示的簡化模型，由于圖中只有A、B兩個“奇點”，故該圖可以一筆（不重復）畫成，即可以不重復地通過15座橋.

四、圖論的形成

歐拉在解決“哥尼斯堡七橋問題”的過程中，開創(chuàng)了一個新的數學分支——圖論.他所使用的方法是圖論中常用的方法.歐拉的這個結論標志著圖論的誕生，即研究由線連接的點組成的網絡.用現(xiàn)在圖論的術語來說，哥尼斯堡七橋問題屬于一筆畫問題：如何判斷這個圖是否是一個能夠遍歷完所有的邊而沒有重復的圖.如果存在這樣的方法，該圖則稱為歐拉圖.這時遍歷的路徑稱作歐拉路徑（一個環(huán)或者一條鏈），如果路徑閉合（一個圈），則稱為歐拉回路.

圖論中的歐拉定理（一筆畫定理）要分有向圖（邊有特定方向的圖）與無向圖（邊沒有特定方向的圖）兩種情況進行討論.

1.無向圖的情況

定理：連通無向圖G有歐拉路徑的充要條件為：G中奇度頂點（即與其相連的邊數目為奇數的頂點）有0個或者2個.

證明：必要性.

如果圖能夠被一筆畫成，那么對每個頂點，考慮路徑中“進入”它的邊數與“離開”它的邊數（注意前提是無向圖，所以我們不能稱其為“人邊”和“出邊”）.很顯然這兩個值要么相同（說明該頂點度數為偶），要么相差1（說明該頂點度數為奇）.

也就是說，如果歐拉路徑不是回路，奇度頂點就有2個，即路徑的起點和終點;如果是歐拉回路，起點與終點重合，則不存在奇度頂點.必要性得證.

證明：充分性.

如果圖中沒有奇度頂點，那么在G中隨機取一個頂點v₀出發(fā)，嘗試構造一條回路c₀.如果c₀就是原路，則結束;如果不是，那么由于圖是連通的，c₀和圖的剩余部分必然存在某公共頂點v₁，從v₂出發(fā)重復嘗試構造回路，最終可將整張圖分割為多個回路.由于兩條相連的回路可以視為一條回路，所以該圖必存在歐拉回路.

如果圖中有2個奇度頂點u和v，那么若是加一條邊將u和v連接起來的話，就得到一個沒有奇度頂點的連通圖，由上文可知該圖必存在歐拉回路，去掉這條新加的邊，就是一條以u和v為起終點的歐拉路徑.充分性得證.

可知，哥尼斯堡七橋問題中的圖有4個奇度頂點（1個度數為5，3個度數為3），所以不存在歐拉路徑.

2.有向圖的情況

定理：底圖連通的有向圖G有歐拉路徑的充要條件為：G的所有頂點入度和出度都相等;或者只有兩個頂點的入度和出度不相等，且其中一個頂點的出度與入度之差為1，另一個頂點的入度與出度之差為1.

顯然，可以通過與無向圖情況相似的思路來證明，過程略.

當時的數學界起初并未對歐拉解決七橋問題的意義有足夠的認識，甚至有些人僅僅當其為一個數學游戲.圖論這一數學分支誕生后并未得到很好的發(fā)展，直到200年后的1936年，匈牙利數學家科尼希出版了《有限圖與無限圖理論》，此為圖論的第一部專著，其總結了進200年來有關圖論的成果，這是圖論發(fā)展的第一座里程碑.此后，圖論進入發(fā)展與突破的階段，又經過了半個多世紀的發(fā)展，現(xiàn)已成為數學科學的一個獨立的重要分支.

圖論原是組合數學中的一個重要課題.我們用點表示事物，用連接點的邊表示事物間的聯(lián)系，便可得到圖論中的圖.圖論為研究任何一類離散事物的關系結構提供了一種框架.圖論中的理論已應用于經濟學、心理學、社會學、遺傳學、運籌學、邏輯學、語言學計算機科學等諸多領域.

由于現(xiàn)代科學尤其是大型計算機的迅猛發(fā)展，使得圖論大有用武之地，無論是數學、物理、化學、地理、生物等基礎科學，還是信息、交通、戰(zhàn)爭、經濟乃至社會科學的眾多問題，都可以運用圖論方法予以解決.當然，圖論也是計算機科學的基礎學科之一.

值得一提的是，歐拉對七橋問題的研究，后演變成多面體理論，得到了著名的歐拉公式V+F=E+2，歐拉公式是拓撲學的第一個定理.

哥尼斯堡的七座橋如今只剩下三座，一條新的跨河大橋已經建成，它完全跨過河心島——內福夫島，導游們仍向游客講述哥尼斯堡橋的故事，有的導游甚至仍稱“七橋問題”沒有被解決，留給游客以遐想.雖然七座哥尼斯堡橋成了歷史，但是“七橋問題”留下的“遺產”不像這些橋那樣容易破壞，歐拉卓越的解答方式被永載史冊.