七橋，七橋怎么過

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

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

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