都是我在 Graph Theory 課上碰到的問題, 不需要數學背景就可以解, 所以反過來說, 就算有深厚的數學背景, 也未必能解。
一個老鼠要吃一個 3*3*3 (inch^3) 的 cheese（如圖）, 而且他一次只能吃一個 1*1*1 的 cheese, 吃完後才能吃隔壁的。老鼠可以上下左右移動, 如果今天考慮他只能從角落開始吃, 那他有沒有可能把最中間的那塊 1*1*1 的 cheese 留到最後才吃？
這一題是我上次的 Graph Theory 作業四題中的一題, 我做不出來。老實說, 要看出答案並不是太難, 但是要給出一個完整而令人信服的證明卻不是那麼容易, 後來我還是向同學求救才解出這一題（不然我的作業成績就很難看了）。
證明如下：
我們要先有一個基本認知, 就是老鼠只能吃他隔壁的那塊 cheese, 他不能瞬間移動跳到隔壁的隔壁吃 cheese。根據這個我們可以利用 Graph Theory 中很基本的一個概念叫做 "bi-partite"。這個字看起來很嚇人, 其實概念很簡單, 就是比如說你把一群人分成紅組跟白組, 做紅白大對抗之類的遊戲, 規則就是, 紅組的人只能跟白組的人牽手, 跟誰牽不拘, 只要是白組的就可以, 而白組也是一樣, 只能跟紅組的人牽手。由此我們就可以得到兩組人, 這兩組人都不能跟同組的人牽手, 只能跟別組的人牽手, 這兩組人, 我們就稱為 bi-partite。
在 Cheese 上如果我們把相鄰的 cheese 類比為牽手, 我們就可以發現我們也可以把 Cheese 分成紅白（或是 A, B）兩組, 其中, A 組人跟 B 組人彼此相鄰, 但是 A 組人絕對不會碰到 A 組人。而 B 組人也是一樣, 不會碰到自己人。如圖：
兩側的 Cheese（隨便選哪兩側, 因為是點對稱的圖形）可以分成這樣。
夾在中間的 Cheese 則可以分成這樣。
根據這個分組設定, 我們會發現, 最中間的那塊 cheese, 是 B 組的, 而任意角落的 cheese, 則是 A 組的。
這時候我們就發現矛盾了。矛盾在哪呢？很顯然, 如果我們要老鼠從角落開始吃, 那他一定會吃 A 組的 cheese, 然後接下來吃隔壁的, 也就是 B 組的 cheese, 然後 A, 然後 B...用符號來表示的話就是：
A-B-A-B-A-B-A...
而我們知道, 全部總共有 27 塊 cheese。27 是個奇數, 所以如果從 A 組開始吃, 那他最後一塊吃的一定是 A 組的, 而我們前面已經看到, 中間那塊是 B 組的...所以, 老鼠永遠沒辦法把中間那塊放到最後來吃。
很簡單吧。不過這題我想了好幾天想破頭都不知道要怎麼做, 如果能往 bi-partite 上去想的話應該一下就搞定了, 但是方向錯誤就沒辦法的。
另外一個問題其實也不能算是問題, 只是一個很有趣的現象。就是 plain graph 的問題。在 Graph Theory 裡面有定義一種圖叫做 "complete graph", 乍看之下會有點摸不著腦袋, 不過他的定義真的是超簡單。就是, 如果你有一個點, 那個點就是 complete graph, 如果你有兩個點, 那把那兩個點連起來, 又是一個 complete graph, 如果是三個點, 就畫一個三角形, 如果是四個點, 那就是：
也就是正方形裡面畫個叉。
簡單的說, complete graph 就是你有幾個點, 就把每個點和每個點之間全部連起來。
現在問題來了, 有沒有可能把 K4（也就是有四個點的 complete graph 全部連起來, 但是線跟線彼此不交叉呢？
K4 是可以的, 畫起來是這樣：
那 K5 呢, 一般的 K5 表示法是這樣：
那 K5 能不能畫成彼此不交叉的形式呢？老師在黑板上幾經嘗試後, 告訴我們在 30 年代就有人證明了不可能。（所以說這老師很喜歡裝模作樣...）
可是為什麼不可能呢？哪些圖可能畫成不交叉的形式？哪些圖不行？
後來老師說, K5 無法完成, 其實只是在歐氏（Euclidian）平面上不能完成, 在甜甜圈（torus）上面是可以完成的：
有興趣的人可以試試看。:)
留言列表
