美麗的電腦世界 - 四色問題

(5/31/2011) 今天五月三十一日是美國國殤紀念日。我在本文最後貼了兩張美國華府舉辦的國殤遊行中我們中華民國社團參加遊行的照片。

(5/29/2011)

什麼叫四色問題呢？這個問題是說：任何一張地圖，都可以用四種不同的顏色來畫，使得沒有鄰近的區塊用相同的顏色畫。這個數學問題已經被人證明，而且是用電腦程式證明。我倒沒有意圖想另一個證明方法。我只是想寫個Java程式來用四色畫地圖：給一張地圖，程式可以用四色來畫圖。做法其實不難：把四色問題轉換成圖形(graph)問題即可。怎麼轉換呢？可以想像：鄰接的地區就好像連在一起的點(譬如：美國的加州和奧勒岡州鄰接，和內華達州鄰接，也和亞利桑納州鄰接。以這個例子來看，只需要三色，而且不能少於三色：因為奧勒岡州不和內華達及亞利桑納鄰接。但是加州和內州及亞州這三個州都是彼此鄰接的)。這種連在一起的點的問題，在數學上就叫圖形問題(Graph problem)。我先用下圖來解釋四色問題轉換成圖形問題的道理：

你可以看到他們用了五色。我們可以把這種地圖著色的問題轉換成圖形學(Graph)裡的結點(node或vertex)，就得到下面的圖：(CA: 加州；AZ: 亞利桑納州; OR: 奧勒岡州; NV:內華達州)

這裡的OR其實不需塗黃色，可塗紅色或青色。因此只需三色。我的程式就是用圖形學來解問題的。其實恐怕所有的解法都用了圖形學。圖形學是大學應用數學的學問。我下面抄一個已知的四色問題演算法供有興趣者參考。其實，你在網路上可找到。

演算法：

1. If the graph has ≤ 4 vertices, color it optimally by brute
force. Stop.
2. Find a vertex X with minimum valency ν.
3. Delete X from the graph. (Optionally, the ν-gonal
“hole”may now be triangulated by diagonals.)
4. Color the remaining smaller graph recursively.
5. Color X with the first color not used by its neighbors.
Stop. 

他們證明了這個演算法的計算時間是線性(Linear Time)的。我前一次講的Tower of Hanoi的計算時間則是指數(Exponential Time)的。所謂線性的，是指它的計算時間跟運算項目成正比(簡單地講)。所謂指數的，是計算時間跟運算項目成指數倍數。

我基本上已經有了這個問題的Java程式。還有很多地方需要修改。譬如：我要把州的簡名寫上去(加州是CA等)。還有，這個地圖的座標有點錯，譬如愛我華州(Iowa, IA)和堪薩斯州(Kansas, KS)並沒有連在一起。所以你看我畫出來的圖把IA和KS都給了同色，好像不對。沒有的事，是地圖的多邊形畫錯了。我會找時間更改。(至少放到Android手機時一定會改)我用這張地圖是因為多邊形(polygon)的點都已取出。但是我在解問題的時候已經把地圖的地區連結關係轉換成圖形學(Graph)裡的結點(vertex or node)。

(5/31/2011)我已更改地圖，有點粗糙。原地圖本來就畫得不好，Iowa州(IA)本來就應該很小，它畫得很大。

下面是美國氣象局做的美國地圖：

這個畫地圖的程式其實還可以用來教地理。我將來可能會擴充到一些有趣的地理知識或常識。

這個Java Applet的網站在：

http://homepage8.seed.net.tw/web@3/heuristic/FourColor02.html

作者按：雖然我可以把Java Applet程式嵌在這篇文章中，但是它把後面所有的東西都砍掉了。我只好忍痛把Applet程式拿掉了。謝謝部落格網友思無邪告訴我這個問題。

[QS2011亞洲大學排名]QS2011年的亞洲大學排名出爐。臺灣各大學的排名如下：

ESI世界大學教授論文引用率資料(以清華大學列入排名之學科為準)：

QS2011世界大學排名中學科排名的材料科學與冶金學(Metallurgy)是臺灣大學排名最好的學科：臺大(38)，清大(72)，成大(127)，交大(183)。如下表：

5/31/2011 美國國殤紀念日遊行照片：

(一)只看到我們中華民國的國旗。

(二)中美國旗飄揚。

6/1/2011 今天看到一個故事，值得一記：亞里斯多德居然有這樣的邏輯，他認為男人比女人強壯，個頭一般也比較高大，所以男人的牙齒比女人多。他居然也不實際去比較一下男女的牙齒數目。這故事有趣。

[數學遊戲] 6/3/2011 有個數學問題：給1,2,3,4,5,6,7,8,9九個阿拉伯數字，用這九個數字組成三組整數。每個數字不得重複，譬如：156, 237, 489是三組數，每個數都沒有重複的阿拉伯數字。問題是：其中兩組數相乘的結果必須是第三組數。
根據這樣的限制，我們可以知道：不可能有三位數乘以三位數能得到三位數。所以只有兩種可能：
1. 一位數乘以四位數得到四位數。
2. 二位數乘以三位數得到四位數。
沒有其他任何可能了。注意沒有一個數的單一數字能和其他數字重複，也不能是零。
這個問題，寫個程式就可解決。不過，沒有電腦以前，人們是怎麼解決的呢？
我們可以很容易地算出來1和9不能是答案：1乘以任何數一定是被乘的數：
1XN = N。9乘以任何12開頭的四位數就已變成五位數。8,7,6可以找到類似的結果。5乘以任何數一定以0或5結尾，所以也不能用。2呢？你無法把5放進另兩個數而能使2乘以其中一數而得到另一數。3比較麻煩，但是也可得到結論：3不是答案。
唯一的一位數答案是4。
二位數呢？