七橋問題SevenBridgesProblem
英文檢索:
1、EulerandHamiltonCircuits&Paths
AnEulercircuitinagraphisasimplecircuitcontainingeveryedgeofG.AnEulerpathcontainingeveryedgeofG.
2、SevenBridgesProblem:
TheSevenBridgesofKonigsbergΜltigraphModelofthetownofKonigsberg
3、NecessaryandsufficientconditionsforEulerCircuitsandPath:
TherearesimplecriteriafordeterminingwhetheramultigraphhasanEulerpath.AconnectedmultigraphhasanEulercircuitifandonlyifeachofitsverticeshasevendegree.AconnectedmultigraphhasanEulerpathifandonlyifeachofithasexactlytwoverticesofodddegree.
4、Graycode
5、GraphColoring
在哥尼斯堡的一個公園裡，有七座橋将普雷格爾河中兩個島及島與河岸連接起來。問是否可能從這四塊陸地中任一塊出發，恰好通過每座橋一次，再回到起點?歐拉于1736年研究并解決了此問題，他把問題歸結為如下右圖的“一筆畫”問題，證明上述走法是不可能的。
1736年29歲的歐拉想聖彼得堡科學院遞交了《哥尼斯堡的七座橋》的論文，在解答問題的同時，開創了數學的一個新的分支-----圖論與幾何拓撲。也由此展開了數學史上的新進程。
（哥尼斯堡七橋問題的抽象問題，由此我們可以讨論得出此橋無解）
七橋問題及其解決SevenBridgesProblem
18世紀，沿着俄國和波蘭的邊界，有一條長長的布格河。這條河流經俄國的古城康尼斯堡——它就是今天俄羅斯西北邊界城市
。
布格河橫貫康尼斯堡城區，它有兩條支流，一條稱新河，另一條叫舊河，兩河在城中心會合後，成為一條主流，叫做大河。在新舊兩河與大河之間，夾着一塊島形地帶，這裡是城市的繁華地區。全城分為北、東、南、島四個區，各區之間共有七座橋梁聯系着。
人們長期生活在河畔、島上，來往于七橋之間。有人提出這樣一個問題：能不能一次走遍所有的七座橋，而每座橋隻準經過一次？
問題提出後，很多人對此很感興趣，紛紛進行試驗，但在相當長的時間裡，始終未能解決。而利用普通數學知識，每座橋均走一次，那這七座橋所有的走法一共有7！=5040種，而這麼多情況，要一一試驗，這将會是很大的工作量。但怎麼才能找到成功走過每座橋而不重複的路線呢？因而形成了著名的“哥尼斯堡七橋問題”。
1935年，有幾名大學生寫信給當時正在俄羅斯的彼得斯堡科學院任職的天才數學家歐拉，請他幫忙解決這一問題。歐拉在親自觀察了哥尼斯堡七橋後，認真思考走法，但始終沒能成功，于是他懷疑七橋問題是不是原本就無解呢？
1736年，在經過一年的研究之後，29歲的歐拉提交了《哥尼斯堡七橋》的論文，圓滿解決了這一問題，同時開創了數學新一分支---圖論。
在論文中，歐拉将七橋問題抽象出來，把每一塊陸地考慮成一個點，連接兩塊陸地的橋以線表示。并由此得到了如圖一樣的幾何圖形。
若我們分别用A、B、C、D四個點表示為哥尼斯堡的四個區域。這樣著名的“七橋問題”便轉化為是否能夠用一筆不重複的畫出過此七條線的問題了。若可以畫出來，則圖形中必有終點和起點，并且起點和終點應該是同一點，由于對稱性可知由A或C為起點得到的效果是一樣的，若假設以A為起點和終點，則必有一離開線和對應的進入線，若我們定義進入A的線的條數為入度，離開線的條數為出度，與A有關的線的條數為A的度，則A的出度和入度是相等的，即A的度應該為偶數。即要使得從A出發有解則A的度數應該為偶數，而實際上A的度數是3為奇數，于是可知從A出發是無解的。同時若從B或D出發，由于B、D的度數分别是5、3，都是奇數，即以之為起點都是無解的。
有上述理由可知，對于所抽象出的數學問題是無解的，即“七橋問題”也是無解的。
由此我們得到:歐拉回路關系
由此我們可知要使得一個圖形可以一筆畫，必須滿足如下兩個條件：
1.圖形必須是連通的。
2.途中的“奇點”個數是0或2.
我們也可以依此來檢驗圖形是不是可一筆畫出。回頭也可以由此來判斷“七橋問題”，4個點全是奇點，可知圖不能“一筆畫出”，也就是不存在不重複地通過所有七橋。
歐拉的這個考慮非常重要，也非常巧妙，它正表明了數學家處理實際問題的獨特之處——把一個實際問題抽象成合适的“數學模型”。這種研究方法就是“數學模型方法”。這并不需要運用多麼深奧的理論，但想到這一點，卻是解決難題的關鍵。
1736年，歐拉交給彼得堡科學院的《哥尼斯堡7座橋》的論文為後來的數學新分支——圖論與拓撲學的建立奠定了基礎。這使得歐拉成為圖論〔及拓撲學〕的創始人。
七橋問題和歐拉定理。歐拉通過對七橋問題的研究，不僅圓滿地回答了哥尼斯堡居民提出的問題，而且得到并證明了更為廣泛的有關一筆畫的三條結論，人們通常稱之為歐拉定理。對于一個連通圖，通常把從某結點出發一筆畫成所經過的路線叫做歐拉路。人們又通常把一筆畫成能回到出發點的歐拉路叫做歐拉回路。具有歐拉回路的圖叫做歐拉圖。
此題被人教版小學數學第十二冊書收錄.在95頁.
此題也被人教版初中第一冊收錄．在一百二十一頁．
