18世紀著名古典數學問題之一。在哥尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島及島與河岸連接起來(如圖)。問是否可能從這四塊陸地中任一塊出發，恰好通過每座橋一次，再回到起點？歐拉于1736年研究并解決了此問題，他把問題歸結為如右圖的“一筆畫”問題，證明上述走法是不可能的。
有關圖論研究的熱點問題。18世紀初普魯士的哥尼斯堡，有一條河穿過，河上有兩個小島，有七座橋把兩個島與河岸聯系起來（如右上圖）。有個人提出一個問題：一個步行者怎樣才能不重復、不遺漏地一次走完七座橋，最后回到出發點。后來大數學家歐拉把它轉化成一個幾何問題（如左圖下）——一筆畫問題。他不僅解決了此問題，且給出了連通圖可以一筆畫的充要條件是：奇點的數目不是0 個就是2 個（連到一點的數目如是奇數條，就稱為奇點，如果是偶數條就稱為偶點，要想一筆畫成，必須中間點均是偶點，也就是有來路必有另一條去路，奇點只可能在兩端，因此任何圖能一筆畫成，奇點要么沒有要么在兩端） [1]? 。
推斷方法
當Euler在1736年訪問Konigsberg, Prussia(now Kaliningrad Russia)時，他發現當地的市民正從事一項非常有趣的消遣活動。Konigsberg城中有一條名叫Pregel的河流橫經其中，這項有趣的消遣活動是在星期六作一次走過所有七座橋的散步，每座橋只能經過一次而且起點與終點必須是同一地點。
Euler把每一塊陸地考慮成一個點，連接兩塊陸地的橋以線表示。
后來推論出此種走法是不可能的。他的論點是這樣的，除了起點以外，每一次當一個人由一座橋進入一塊陸地（或點）時，他（或她）同時也由另一座橋離開此點。所以每行經一點時，計算兩座橋（或線），從起點離開的線與最后回到始點的線亦計算兩座橋，因此每一個陸地與其他陸地連接的橋數必為偶數。
存在問題
七橋所成之圖形中，沒有一點含有偶數條數，因此上述的任務無法完成。
著名數學家歐拉的畫像
著名數學家歐拉的畫像
歐拉的這個考慮非常重要，也非常巧妙，它正表明了數學家處理實際問題的獨特之處——把一個實際問題抽象成合適的“數學模型”。這種研究方法就是“數學模型方法”。這并不需要運用多么深奧的理論，但想到這一點，卻是解決難題的關鍵。
接下來，歐拉運用圖中的一筆畫定理為判斷準則，很快地就判斷出要一次不重復走遍哥尼斯堡的7座橋是不可能的。也就是說，多少年來，人們費腦費力尋找的那種不重復的路線，根本就不存在。一個曾難住了那么多人的問題，竟是這么一個出人意料的答案！ void euler(int u){if(G[u][v] && !vis[u][v])for(int v=0;v<n;v++){vis[u][v]=vis[v][u]=1;euler(v);printf("%d %d\n",u,v);} }

總結

以上是生活随笔為你收集整理的七桥问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。