蔡思明

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

一、哥尼斯堡七橋問題

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

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

二、歐拉的解法

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

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

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

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

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

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

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

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

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

四、圖論的形成

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

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

1.無向圖的情況

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

證明：必要性.

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

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

證明：充分性.

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

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

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

2.有向圖的情況

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

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

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

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

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

值得一提的是，歐拉對七橋問題的研究，后演變成多面體理論，得到了著名的歐拉公式V+F=E+2，歐拉公式是拓?fù)鋵W(xué)的第一個(gè)定理.

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