電影《心靈捕手》的數學問題 (四)

Posted on 10/07/2013 by ccjou

本文的閱讀等級：初級

本文是探討電影《心靈捕手》中數學問題的完結篇。這回麻省理工學院朗博教授和威爾將聯手出擊，他們的目標要破解一道組合數學問題：求3─太陽圖 (3-sun graph) G(V,E) 的色多項式 (chromatic polynomial)，其中 G 的頂點集合是 V=\{a,b,c,d,e,f\}，邊集合是 E=\{\{a,b\},\{a,c\},\{a,d\},\{a,e\},\{b,c\},\{b,d\},\{b,f\},\{c,e\},\{c,f\}\} (見圖一)。

3-sun graph

圖一：3─太陽圖

 
我們先介紹相關的背景知識。所謂 n─太陽圖是指一圖有 2n 個頂點，其中 n 個頂點位於中心，n 個頂點在外圍。中心的每一頂點和其他所有的中心頂點鄰接，稱為完全圖 (complete graph)，外圍的每一個頂點和距離最近的兩個中心頂點鄰接。圖二顯示 4─太陽圖和 5─太陽圖。

4-sun graph and 5-sun graph

圖二：4-太陽圖和 5-太陽圖

 
考慮著色圖 G(V,E)，其中每一頂點 v\in V 都有一種顏色。如果任何兩個鄰接頂點有不同的顏色，則稱之為良好著色 (well-coloring)。一圖 G 的色多項式 p_G(k) 是 k 種顏色所能繪出的良好著色圖數。色數 (chromatic number) 是最小的正整數 k 使得 p_G(k)>0，即一良好著色圖所需使用的最少顏色數。舉例來說，若 G 是一個頂點數為 n 的完全圖，則 p_G(k)=k(k-1)\cdots(k-n+1)，k\in\mathbb{N}。明顯地，完全圖 G 的色數為其頂點數 n。

 
下面證明對於任一圖 G，p_G(k) 的確是一多項式，且最高次數為頂點數 n。考慮頂點真子集 W\subset V。如果任意 u,v\in W 彼此不鄰接，即 \{u,v\}\notin E，我們稱 W 為一獨立集。若一良好著色圖按照顏色將頂點分割成組，則相同顏色的頂點形成一獨立集。反過來說，假設圖 G 分割為 r 個獨立集。第一個獨立集可用 k 種顏色來著色，第二個獨立集可用 (k-1) 種顏色，以此類推，最後一個獨立集可用 (k-r+1) 種顏色。因此，使用 k 種顏色的所有著色方式等於 r 次多項式 k(k-1)\cdots(k-r+1)，其中 r\le n。

 
現在我們計算用 k 種顏色所能繪出的良好著色3-太陽圖數。首先考慮圖中心頂點 a, b, c 的著色，a 有 k 種顏色可供選擇，b 有 (k-1) 種可能的顏色，c 使用剩下的 (k-2) 種顏色。接著考慮外圍頂點 d,e,f。因為頂點 d 和 a 鄰接也和 b 鄰接，可知 d 有 (k-2) 種顏色可使用。同樣道理，e 和 f 各自也有 (k-2) 種顏色可用。所以，p_G(k)=k(k-1)(k-2)^4。這就是朗博教授和威爾得到的答案，但他們採用另一種計算方法 (見電影劇照)。

威爾正在解3─太陽圖的色多項式 From http://www.masculinity-movies.com/wp-content/gallery/good-will-hunting/good-will-hunting-5.jpg

 
朗博教授和威爾的思路是利用3-太陽圖的特性──中心為一完全圖──來簡化計算。我們需要下面這個定理：若兩圖 G 和 H 的交集是一完全圖，則

\displaystyle p_{G\cup H}(k)=\frac{p_G(k)p_H(k)}{p_{G\cap H}(k)} 。

證明於下。固定一個良好著色的 G\cap H，令 f_G(k) 和 f_H(k) 分別表示由目前的 G\cap H 所能延伸出良好著色的 G 和 H 的圖數。因為 G\cap H 是一良好著色的完全圖，所有的頂點必定有不同的顏色。根據對稱性，無論 G\cap H 是那一種良好著色圖，f_G(k) 和 f_H(k) 維持不變。所以，p_G(k)=p_{G\cap H}(k)f_G(k) 且 p_H(k)=p_{G\cap H}(k)f_H(k)。另外，G-(G\cap H) 和 H-(G\cap H) 彼此獨立 (無相連邊)，故可推論

\displaystyle p_{G\cup H}(k)=p_{G\cap H}(k)f_G(k)f_H(k)=\frac{p_{G\cap H}(k)f_G(k)p_{G\cap H}(k)f_H(k)}{p_{G\cap H}(k)}=\frac{p_G(k)p_H(k)}{p_{G\cap H}(k)} 。

使用歸納法，上述定理可以推廣至多圖的情形。若 G_1,G_2,\ldots,G_r 是 r 個圖，且 G_i\cap G_j 是一完全圖，1\le i,j\le r 且 i\neq j，則 　

\displaystyle p_{G_1\cup G_2\cup\cdots\cup G_r}(k)=\frac{p_{G_1}(k)p_{G_2}(k)\cdots p_{G_r}(k)}{\left(p_{G_1\cap G_2\cap\cdots\cap G_r}(k)\right)^{r-1}} 。

 
運用分治法 (divide-and-conquer)，將3─太陽圖分解成 G=G_1\cup G_2\cup G_3，其中 G_1 包含頂點 a,b,c,d，G_2 包含頂點 a,b,c,e，G_3 包含頂點 a,b,c,f。注意，G_1\cap G_2\cap G_3 是頂點 a,b,c 形成的完全圖，因此 p_{G_1\cap G_2\cap G_3}(k)=k(k-1)(k-2)。考慮圖 G_1，頂點 a 有 k 種顏色可供選擇，b 有 (k-1) 種可能的顏色，c 和 d 可以獨立選擇 (k-2) 種顏色。圖 G_2 和 G_3 也有相同的著色程序，故 p_{G_i}(k)=k(k-1)(k-2)^2，i=1,2,3。合併以上結果，

\displaystyle\begin{aligned} p_G(k)&=p_{G_1\cup G_2\cup G_3}(k)=\frac{p_{G_1}(k)p_{G_2}(k)p_{G_3}(k)}{\left(p_{G_1\cap G_2\cap G_3}(k)\right)^2}\\ &=\frac{k^3(k-1)^3(k-2)^6}{k^2(k-1)^2(k-2)^2}=k(k-1)(k-2)^4.\end{aligned}

在電影中，朗博教授和威爾沒有繼續尋找4─太陽圖和─5太陽圖的色多項式。按照往例，這個問題就留給讀者自行完成，並且歸納 n─太陽圖的色多項式。

 
據說，人類天生就有探索數學奧秘的衝動。一些看過《心靈捕手》的人很可能想更了解裡面的數學問題和解答過程，我希望這一系列的介紹與討論不僅帶給讀者樂趣，也對增進智識有所助益。最後我引用數學家波利亞 (George Polya) 說的一段話作為結語[1]：

就算學生在數理上頗具天分，機會還是可能從指尖溜走，因為這些天賦異稟的學生也跟其他人一樣，必須花點功夫探索自己的天分，培養自己的興趣。想想看，如果沒嚐過覆盆子派，哪裡會知道自己喜不喜歡呢？然而，學生最後可能還是會發現，數學問題也許就像填字遊戲一樣好玩，他們還可能發現解數學題時的心智活動，也可以像一場勢均力敵的網球賽一樣讓人嚮往。學生一旦嚐過了數學的愉悅之處，就很難再忘記，而這樣一來，數學就有機會在他們的生命中占有一席之地，成為他們的嗜好、未來從事專業工作時必需的工具、成為他們的專業，或幻化成他們的抱負。

 
參考來源：
[1] 《怎樣解題》，How to Solve it，波利亞著，蔡坤憲譯，遠見天下出版，2006。

Advertisement
This entry was posted in 圖論 and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s