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

本文的閱讀等級:初級

本文是探討電影《心靈捕手》中數學問題的完結篇。這回麻省理工學院朗博教授和威爾將聯手出擊,他們的目標要破解一道組合數學問題:求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

 
下面證明對於任一圖 Gp_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 的著色,ak 種顏色可供選擇,b(k-1) 種可能的顏色,c 使用剩下的 (k-2) 種顏色。接著考慮外圍頂點 d,e,f。因為頂點 da 鄰接也和 b 鄰接,可知 d(k-2) 種顏色可使用。同樣道理,ef 各自也有 (k-2) 種顏色可用。所以,p_G(k)=k(k-1)(k-2)^4。這就是朗博教授和威爾得到的答案,但他們採用另一種計算方法 (見電影劇照)。

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

\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 所能延伸出良好著色的 GH 的圖數。因為 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_rr 個圖,且 G_i\cap G_j 是一完全圖,1\le i,j\le ri\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,dG_2 包含頂點 a,b,c,eG_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,頂點 ak 種顏色可供選擇,b(k-1) 種可能的顏色,cd 可以獨立選擇 (k-2) 種顏色。圖 G_2G_3 也有相同的著色程序,故 p_{G_i}(k)=k(k-1)(k-2)^2i=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。

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

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s