文章專區

台大的 PTT（批踢踢）是國內最大的 BBS（電子布告欄），號稱有上萬個看板，常駐在其上的「鄉民」時時刻刻都超過13萬人……呃，我也是其中之一。做數學的就是長久坐在書桌和電腦前面，不上網也難。

群眾是一窩蜂瞎起鬨的，所以一些熱門看板每每會失控暴動，出現大量無關的垃圾發文洗版。最近一次莫名其妙的暴動出現在CCR（跨國戀情版），導因是某些鄉民看不慣崇洋的另外一些鄉民，因此一言不合後引發文章洗版大戰，至今還未平息。（如果讀者看不太懂這一段，要小心和年輕人有點脫節了。）我看著CCR版無厘頭的胡鬧，一面大笑，竟一面想到底下這個數學問題。

眾人來自不同國家，有些彼此有認識關係。我們規定認識是雙向的——甲認識乙，則乙一定也認識甲。可以將「崇洋」定義為「喜歡外國人 甚於喜歡本國人」（純粹是數學定義，勿過度延伸）。因此若某個崇洋者，他認識的人之中外國人比較多，那他一定頗高興。當然，若他的朋友全是外國人，那他想必非常快樂。現在我們就有 一個 CCR 問題：

問題一：一群人參加聚會，這群人之中本來已經有一些認識關係了。現在要分成兩組。假設對於任一個參加者而言，如果（他／她）在另一組認識的人數，大於等於（他／她）在自己這一組認識的人數，（他／她）就會很興奮。主辦單位能不能將每個人分組，讓每個人都很興奮？

用數學的語言來說，這是一個圖論的染色問題。一個圖由一些點與線連結而成。每個點代表 一個人，兩點之間的連線代表兩人彼此認識。現在問題變成：

問題一：任給一個圖，能不能將頂點染成紅黑兩色，使得每個頂點的鄰居之中，異色點個數大於或等於同色點個數？……【更多內容請閱讀科學月刊第514期】