看板 WaKnow
作者 標題 [知識分享] 遊戲和圖論: 一筆畫問題
時間 2011年04月14日 Thu. PM 06:47:55
今天我們來玩個遊戲，用一筆畫通過所有的點畫完一個圖形，每個點不能重複通過～！
![[圖]](http://waknow.com/wp-content/uploads/2011/04/picture.jpg)
歐拉用圖論解決了七橋問題, 而這篇1736年的論文《柯尼斯堡的七橋》, 也順帶解決了我們小時候常玩的 "一筆畫遊戲" 喔!
還記得歐拉把 "地圖" 抽象化成 "圖" 的過程嗎?
![[圖]](http://waknow.com/wp-content/uploads/2011/04/picture-2.png)
對照一下本文最上面的四個一筆畫問題, 如果我們把每個轉折點和交叉點, 視為七橋問題中的 "陸地" (也就是 圖 的"頂點"), 把每條小線段視為 "橋" (圖 的 "邊"), 那麼 "七橋問題" 就是一個標準的 "一筆畫問題" 了!
在看以下的證明之前, 各位可以先試玩一下（ 這個連結有更多） , 會發現四個圖都可以一筆畫完成. 圖 (1) 和 (3) 要特別選擇起點和終點, 而 (2) 跟 (4) 可以從任一個點出發, 走完所有的邊以後回到原點.
證明的方法, 跟歐拉論述七橋問題的方法一模一樣: 在一趟不重複過線段 ("橋") 的旅程中, 除了起點和終點的兩個點 ("陸地") 以外, 進出一個點恰會用掉兩條線段, 所以與這樣的點相連的線段總數 (圖論中稱為點的 "度數"), 就必須是偶數.
換句話說, 一個連通圖能夠一筆畫走完的必要條件是, 這個圖每一點的度數都是偶數, 或者這個圖恰有兩個點的度數是奇數.
歐拉也提出了 "充份條件", 也就是實際的走法, 不過解釋起來比較複雜, 有興趣的同學可以參考 維基百科.
圖 (2) 中, 每一個點的度數不是2就是4; 圖 (4) 中, 每一個點的度數不是4就是6, 所以可以一筆畫完成. 選定任一點出發, 用掉一條邊以後, 起點剩下沒走過的度數就變成奇數了, 所以起點也必須是終點.
圖 (1) 的房子, 除了底部的兩個點度數為3以外, 其它點的度數不是2就是4. 所以存在的一筆畫走法, 必定以底部兩點為起點和終點.
圖 (3) 跟 圖 (2) 只差在左下角一條線段, 但就是因為這條線段, 使得左下角的兩個點, 度數都變成奇數了. 所以存在的一筆畫走法, 必定以左下角兩點為起點和終點.
最後, "一筆畫問題" 還有一個有趣的特性: 走法常常不只一種! 譬如下圖 五角星形 就有兩種常見的走法:
![[圖]](http://waknow.com/wp-content/uploads/2011/04/1334400755.jpg)
要列舉出所有的走法, 牽涉到排列組合, 因為每到達一個交叉點, 就會有多種選擇接下來走哪一條線段. iMath 也有相關的題目和觀念可供參考喔!
iMath關鍵字搜尋（ 點此前往 ）：「每條道路都要經過」
--
※ 作者: waknow 時間: 2011-04-14 18:47:55 來自: 180.218.42.212
※ 看板: WaKnow 文章推薦值: 2 目前人氣: 0 累積人氣: 1323
回列表(←)
分享