七橋問題及其證明

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

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

3、必要性證明， 那么， 充分性的證明呢？當(dāng)一個(gè)非空連通圖 G 的每個(gè)頂點(diǎn)都是偶度頂點(diǎn)， 那圖 G 就有 Euler 閉跡嗎？直接證明這個(gè)比較困難， 可以用反證法來 證明：無妨設(shè)圖G的頂點(diǎn)個(gè)數(shù)n 1。因G連通，故至少有一條邊。假設(shè) 圖G無奇度頂點(diǎn)，但它不是 Euler圖。令S = G | G是至少有一條邊 的n階連通圖，無奇度頂點(diǎn)，且不是 Euler圖，則S非空。取S中 邊數(shù)最少的一個(gè)，記為GO。因G0無奇度頂點(diǎn)，故G0中頂點(diǎn)的度至 少為2,因此GO含有圈，從而含有閉跡。設(shè)C是中一條最長的閉跡。 由假設(shè)， C 不是 GO 的 Euler 閉跡。因此 GO 中將 C 的邊去掉后必有 一個(gè)連通分支至少含有一條邊。記這個(gè)連通分支為G1。由于C是閉跡，故G1中沒有奇度頂點(diǎn)，且G1的邊少于GO的邊。由GO的選擇 可知，G1必有Euler閉跡，記為C1。因此C+ C1是的一條閉跡，且 它比C更長，這與C的選取矛盾。證畢。是不是看的稀里糊涂呢？其實(shí)仔細(xì)想想不難理解，考慮所有節(jié)點(diǎn) 度之和為偶數(shù)，則除去一個(gè) Euler