七橋，七橋怎么過

在論文中，歐拉將七橋問題抽象出來，把每一塊陸地考慮成一個點，連接兩塊陸地的橋以線表示。并由此得到了如圖一樣的幾何圖形。 若我們分別用A、B、C、D四個點表示為哥尼斯堡的四個區(qū)域。這樣著名的“七橋問題”便轉化為是否能夠用一筆不重復的畫出過此七條線的問題了。若可以畫出來，則圖形中必有終點和起點，并且起點和終點應該是同一點，由于對稱性可知由A或C為起點得到的效果是一樣的，若假設以A為起點和終點，則必有一離開線和對應的進入線，若我們定義進入A的線的條數(shù)為入度，離開線的條數(shù)為出度，與A有關的線的條數(shù)為A的度，則A的出度和入度是相等的，即A的度應該為偶數(shù)。即要使得從A出發(fā)有解則A的度數(shù)應該為偶數(shù)，而實際上A的度數(shù)是3為奇數(shù)，于是可知從A出發(fā)是無解的。同時若從B或D出發(fā)，由于B、D的度數(shù)分別是5、3，都是奇數(shù)，即以之為起點都是無解的。 　　有上述理由可知，對于所抽象出的數(shù)學問題是無解的，即“七橋問題”也是無解的

18世紀時，歐洲有一個風景秀麗的小城哥尼斯堡，那里有七座橋。如圖1所示：河中的小島A與河的左岸B、右岸C各有兩座橋相連結，河中兩支流間的陸地D與A、B、C各有一座橋相連結。當時哥尼斯堡的居民中流傳著一道難題：一個人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點？大家都試圖找出問題的答案，但是誰也解決不了這個問題。 　　七橋問題引起了著名數(shù)學家歐拉（1707—1783）的關注。他把具體七橋布局化歸為圖2所示的簡單圖形，于是，七橋問題就變成一個一筆畫問題：怎樣才能從A、B、C、D中的某一點出發(fā)，一筆畫出這個簡單圖形（即筆不離開紙，而且a、b、c、d、e、f、g各條線只畫一次不準重復），并且最后返回起點？歐拉經(jīng)過研究得出的結論是：圖2是不能一筆畫出的圖形。這就是說，七橋問題是無解的。這個結論是如何產生呢？請看下面的分析。 　　如果我們從某點出發(fā)，一筆畫出了某個圖形，到某一點終止，那么除起點和終點外，畫筆每經(jīng)過一個點一次，總有畫進該點的一條線和畫出該點的一條線，因此就有兩條線與該點相連結。如果畫筆經(jīng)過一個n次，那么就有2n條線與該點相連結。因此，這個圖形中除起點與終點外的各點，都與偶數(shù)條線相連。如果起點和終點重合，那么這個點也與偶數(shù)條線相連；如果起點和終點是不同的兩個點，那么這兩個點部是與奇數(shù)條線相連的點。綜上所述，一筆畫出的圖形中的各點或者都是與偶數(shù)條線相連的點，或者其中只有兩個點與奇數(shù)條線相連。 　　圖2中的A點與5條線相連結，B、C、D各點各與3條線相連結，圖中有4個與奇數(shù)條線相連的點，所以不論是否要求起點與終點重合，都不能一筆畫出這個圖形。 　　1736年，歐拉在圣彼得堡科學院作了一次學術報告。在報告中，他證明了上述結論。后來他又給出了鑒別任一圖形能否一筆畫出的準則，即歐拉定理。為了介紹這個定理，我們先來看下面的預備知識： 　　由有限條線組成的圖形叫做網(wǎng)絡，其中每條線都要求有兩個不同的端點。這些線叫做網(wǎng)絡的弧，弧的端點叫做網(wǎng)絡的頂點。例如，圖2是一個網(wǎng)絡，a、b、c、d、e、f、g是它的7條弧，A、B、C、D是它的四個頂點。 　　網(wǎng)絡中互相銜結的一串弧叫做一條路。如果網(wǎng)絡中任意兩個頂點都可以用一條路連結起來，那么就稱這個網(wǎng)絡為連通的；否則稱為不連通的。例如，圖2是連通的網(wǎng)絡；圖3是不連通的網(wǎng)絡，其中有的頂點（例如A與D）之間沒有路線連結。

當Euler在1736年訪問Konigsberg, Prussia(now Kaliningrad Russia)時，他發(fā)現(xiàn)當?shù)氐氖忻裾龔氖乱豁椃浅Ｓ腥さ南不顒?。Konigsberg城中有一條名叫Pregel的河流橫經(jīng)其中，在河上建有七座橋如圖所示: 這項有趣的消遣活動是在星期六作一次走過所有七座橋的散步，每座橋只能經(jīng)過一次而且起點與終點必須是同一地點。 Euler把每一塊陸地考慮成一個點，連接兩塊陸地的橋以線表示，便得如下的圖后來推論出此種走法是不可能的。他的論點是這樣的，除了起點以外，每一次當一個人由一座橋進入一塊陸地（或點）時，他（或她）同時也由另一座橋離開此點。所以每行經(jīng)一點時，計算兩座橋（或線），從起點離開的線與最后回到始點的線亦計算兩座橋，因此每一個陸地與其他陸地連接的橋數(shù)必為偶數(shù)。 七橋所成之圖形中，沒有一點含有偶數(shù)條數(shù)，因此上述的任務是不可能實現(xiàn)的。