七橋問題及其證明

七橋問題對很多人來說並不是陌生的名詞，尤其當它已經被寫進了小學數學課本……不過，此處還是再來囉嗦地介紹一下七橋問題到底是怎樣的乙個命題。

傳說在18世紀普魯士的哥尼斯堡城，有一條叫做普雷格爾的河，河中間有兩個島，有七座橋把這兩個島與河岸相連，就像下面這個示意圖裡左圖給出的一樣。市民們飯後茶餘就在討論，能不能不重複的經過每一座橋而回到出發點呢。這個問題也可以被簡化成右圖是否能夠被一筆畫的問題。

大數學家尤拉思考過後認為，市民們一直在找尋的那條路徑是不存在的，把每座橋看成圖的乙個邊（右圖），想要不重複的經過每一條邊而回到原點，則每個頂點必須有偶數條邊與之相連，才能滿足從一條邊來從另一條邊出。用圖論的語言來說，乙個非空連通圖是euler圖當且僅當它沒有奇度頂點。

這裡euler圖指的是有euler閉跡的圖，而euler閉跡是，經過圖g的每條邊恰好一次的閉跡。有了這樣的定義，上面的「七橋問題一筆畫是不可能的」論證過程可以這樣表述：設圖g是euler圖，c是g中乙個euler閉跡。

對g中任乙個頂點v，v必在c上出現。因c每經過v一次，就有兩條與v關聯的邊被使用。設c經過v共k次，則c經過了2k條與v關聯的邊，故v的度為2k（節點v的度指圖g中與v相連的邊的數量）

細心而學究的人會發現，上面僅僅是對命題的必要性證明，那麼，充分性的證明呢？當乙個非空連通圖g的每個頂點都是偶度頂點，那圖g就有euler閉跡嗎？直接證明這個比較困難，可以用反證法來證明：

無妨設圖ｇ的頂點個數n >1。因g連通，故至少有一條邊。假設圖g無奇度頂點，但它不是euler圖。

令s = ，則s非空。取s中邊數最少的乙個，記為g0。因g0無奇度頂點，故g0中頂點的度至少為2，因此g0含有圈，從而含有閉跡。

設c是中一條最長的閉跡。由假設，c不是g0的euler閉跡。因此g0中將c的邊去掉後必有乙個連通分支至少含有一條邊。

記這個連通分支為g1。由於c是閉跡，故g1中沒有奇度頂點，且g1的邊少於g0的邊。由g0的選擇可知，g1必有euler閉跡，記為c1。

因此c＋c1是的一條閉跡，且它比c更長，這與c的選取矛盾。證畢。

是不是看的稀里糊塗呢？其實仔細想想不難理解，考慮所有節點度之和為偶數，則除去乙個euler閉跡後，剩下的節點度之和還是偶數，說明還有閉跡……最後可知整個圖便只有整個乙個最大的閉跡就是euler閉跡了~