哥尼斯堡七橋問題與圖論

蔡思明

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

一、哥尼斯堡七橋問題

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

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

二、歐拉的解法

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

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

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

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

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

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

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

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

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

四、圖論的形成

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

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

1.無向圖的情況

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

證明：必要性.

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

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

證明：充分性.

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

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

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

2.有向圖的情況

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

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

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

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

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

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

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