七橋問題及其證明

《七橋問題及其證明》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、七橋問題及其證明七橋問題對很多人來說并不是陌生的名詞，尤其當它已經被寫進了小學數(shù)學課本……不過，此處還是再來啰嗦地介紹一下七橋問題到底是怎樣的一個命題。??傳說在18世紀普魯士的哥尼斯堡城，有一條叫做普雷格爾的河，河中間有兩個島，有七座橋把這兩個島與河岸相連，就像下面這個示意圖里左圖給出的一樣。市民們飯后茶余就在討論，能不能不重復的經過每一座橋而回到出發(fā)點呢。這個問題也可以被簡化成右圖是否能夠被一筆畫的問題。??大數(shù)學家歐拉思考過后認為，市民們一直在找尋的那條路徑是不存在的，把每座橋看成圖的一個邊（右圖），想要不重復的經過每一條邊而回到原點，則每個頂點必須有偶數(shù)條邊

2、與之相連，才能滿足從一條邊來從另一條邊出。用圖論的語言來說，一個非空連通圖是Euler圖當且僅當它沒有奇度頂點。??這里Euler圖指的是有Euler閉跡的圖，而Euler閉跡是，經過圖G的每條邊恰好一次的閉跡。有了這樣的定義，上面的“七橋問題一筆畫是不可能的”論證過程可以這樣表述：設圖G是Euler圖，C是G中一個Euler閉跡。對G中任一個頂點v，v必在C上出現(xiàn)。因C每經過v一次，就有兩條與V關聯(lián)的邊被使用。設C經過v共k次，則C經過了2k條與v關聯(lián)的邊，故v的度為2k（節(jié)點v的度指圖G中與v相連的邊的數(shù)量）?????細心而學究的人會發(fā)現(xiàn)，上面僅僅是對命題的必要

3、性證明，那么，充分性的證明呢？當一個非空連通圖G的每個頂點都是偶度頂點，那圖G就有Euler閉跡嗎？直接證明這個比較困難，可以用反證法來證明：??無妨設圖Ｇ的頂點個數(shù)n>1。因G連通，故至少有一條邊。假設圖G無奇度頂點，但它不是Euler圖。令S={G

4、G是至少有一條邊的n階連通圖，無奇度頂點，且不是Euler圖}，則S非空。取S中邊數(shù)最少的一個，記為G0。因G0無奇度頂點，故G0中頂點的度至少為2，因此G0含有圈，從而含有閉跡。設C是中一條最長的閉跡。由假設，C不是G0的Euler閉跡。因此G0中將C的邊去掉后必有一個連通分支至少含有一條邊。記這個連通分支為G1。

5、由于C是閉跡，故G1中沒有奇度頂點，且G1的邊少于G0的邊。由G0的選擇可知，G1必有Euler閉跡，記為C1。因此C＋C1是的一條閉跡，且它比C更長，這與C的選取矛盾。證畢。?????是不是看的稀里糊涂呢？其實仔細想想不難理解，考慮所有節(jié)點度之和為偶數(shù)，則除去一個Euler閉跡后，剩下的節(jié)點度之和還是偶數(shù)，說明還有閉跡……最后可知整個圖便只有整個一個最大的閉跡就是Euler閉跡了~