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

Posted on 10/04/2013 by ccjou

本文的閱讀等級：中級

朗博教授公告在走廊黑板的第二個挑戰問題抄錄於下：

(1) How many trees are there with n labeled vertices?
(2) Draw all the homeomorphically irreducible trees with n=10.

威爾的答案：(1) n^{n-2}，(2) 8 棵樹 (見電影劇照)。這兩個問題屬於組合數學的範疇。廣義的組合數學就是離散數學，狹義的組合數學是圖論、代數結構、數理邏輯等的總稱[1]。為了讀懂朗博教授的問題，我們先要瞭解一些關於樹 (圖論的一個主題) 的基本知識。

朗博教授和助教正在審視威爾的答案 From http://blogwillhunting.com/wp-content/uploads/2010/02/gwh_math2.jpg

 
令 G(V,E) 為一無向圖，其中 V 是頂點集合，E 是邊集合。若頂點 u,v\in V 是邊 e\in E 的兩個端點，我們稱 u 和 v 鄰接，記為 e=\{u,v\}。因為無向圖 G 的邊不具方向性，\{u,v\} 可視同兩頂點組成的集合。若任兩頂點之間存在一條旅行路徑 (path)，則稱為連通圖。如果 G 是一個沒有迴路的連通圖，則 G 稱為一棵樹。令 \vert S\vert 表示一集合 S 的基數 (cardinal number)，即 S 包含的元素的個數。以下是樹的等價性質。

  1. G 沒有迴路，但在 G 內添加任何一個邊即可形成一迴路。
  2. G 沒有自環，即 e=\{v,v\}，且存在唯一一條簡單路徑 (不重複拜訪頂點) 連接任兩個頂點。
  3. G 是連通圖，但若去除任一邊就不再連通。
  4. G 沒有迴路，且 \vert E\vert=\vert V\vert-1。
  5. G 是連通圖，且 \vert E\vert=\vert V\vert-1。

對於頂點 v\in V，度數 (degree) d(v) 是以 v 作為邊的一端點的次數，換句話說，d(v) 等於其鄰接頂點的總數。若 d(v)=1，則 v 稱為葉子 (leaf)。若一棵樹不包含度數等於 2 的頂點，則稱為同胚不可約樹 (homeomorphically irreducible tree)。標記頂點 (labeled vertex) 是指每一頂點都有一個識別記號 (通常是自然數或顏色)，具有標記頂點的樹稱為標記樹。見圖一的例子，樹 G=(V,E) 的頂點集合為 V=\{1,2,3,4,5,6\}，邊集合為 E=\{\{1,2\}, \{1,5\}, \{2,4\}, \{3,5\}, \{5,6\}\}，頂點的度數為 d(1)=2，d(2)=2，d(3)=1，d(4)=1，d(5)=3，d(6)=1。

Tree1

圖一：標記樹

 
第一個問題：總計有多少個包含 n 個頂點的標記樹？給定 V=\{1,2,\ldots,n\}，令 \Psi(n) 表示所有標記樹 G=(V, E) 所形成的集合。我們的目標要找出 \vert\Psi(n)\vert。德國數學家博爾夏特 (Carl Wilhelm Borchardt) 於1860年最先發現答案是 \vert\Psi(n)\vert=n^{n-2}，後人稱之為 Cayley 公式，原因是英國數學家凱萊 (Arthur Cayley) 在1889年進行了多方面的延伸工作。Cayley 公式的證法很多[2]，下面介紹德國數學家普呂弗 (Heinz Prüfer) 於1918年提出的一個巧妙證法。(類似的思路可應用於證明等差級數公式，見“等差級數和公式的無言證明”。) 普呂弗設計一個演算法使得每一棵標記樹 G 對應唯一一個長度等於 n-2 的序列，稱為 Prüfer 序列， p=(a_1,a_2,\ldots,a_{n-2})，其中每一 a_j\in\{1,2,\ldots,n\}。因此，我們可以立即推論 \vert\Psi(n)\vert 就是長度為 n-2 的序列數，即 n^{n-2}。按“維基百科”顯示 n=2,3,4 的所有著色標記樹。

 
給定一標記樹 G=(V,E)，其中 \vert V\vert=n，Prüfer 序列 p=(a_1,a_2,\ldots,a_{n-2}) 的算法如下：

  1. 初始化 i\leftarrow 1。
  2. 令 j 表示目前樹中最小的葉子，即 \displaystyle j=\min_{d(v)=1}v。刪除 j 及其鄰接邊 e=\{j,k\}，a_i\leftarrow k。
  3. 若 i=n-2，終止程序。
  4. i\leftarrow i+1，返回步驟 2。

我們以圖一的標記樹為例說明算法過程。圖二顯示每一步驟的結果，紅色線條的頂點表示葉子，黃色頂點表示最小的葉子 (即 j)，綠色頂點表示與黃色葉子鄰接的頂點 (即 a_i)。圖二 (4) 是終止程序刪除 e=\{1,5\} 之前的情況。下表記錄運算結果，閱讀方式係由左而右，從上往下。

\displaystyle \begin{array}{cccccc} i&\vline&1&2&3&4\\\hline j&\vline&3&4&2&1\\ a_i&\vline&5&2&1&5\\\hline \end{array}

表中 a_i 列即為 Prüfer 序列 p=(5,2,1,5)，數對 (j,a_i) 是被刪除的邊 (連接黃色和綠色頂點的邊)，此例最後剩下一邊 \{5,6\}。

Tree2

圖二：標記樹 \to Prüfer 序列

 
若 p=(a_1,a_2,\ldots,a_{n-2}) 是一標記樹的 Prüfer 序列，我們可以從中推論出甚麼訊息？算法步驟 2 隱含：(1) 因為兩葉子不可能鄰接，Prüfer 序列僅由非葉子 (不為葉子的頂點) 組成；(2) 當非葉子 a_i=k 進入 Prüfer 序列時，k 的度數將減去 1 (因為刪除與葉子鄰接的邊)。這兩個性質說明頂點 v\in V 的度數等於 v 出現於 Prüfer 序列次數再加上 1，即

\displaystyle d(v)=\sum_{1\le i\le n-2}I(v,a_i)+1，

其中 I 表示識別函數，I(x,y)=1 若 x=y，I(x,y)=0 若 x\neq y。

 
再看相反方向的算法。給定一 Prüfer 序列 p=(a_1,a_2,\ldots,a_{n-2})，下列算法產生一棵標記樹 G=(V,E)，其中 \vert V\vert=n。

  1. 初始化 i\leftarrow 1。
  2. 令 j 表示度數等於 1 的最小頂點，即 \displaystyle j=\min_{d(v)=1}v。建立一邊 e=\{j,a_i\}，d(j)\leftarrow 0，d(a_i)\leftarrow d(a_i)-1。
  3. 若 i=n-2，建立一邊 e=\{u,v\}，其中 d(u)=d(v)=1；終止程序。
  4. i\leftarrow i+1，返回步驟 2。

我們仍然用上例展示算法。Prüfer 序列 p=(5,2,1,5) 表明標記樹各頂點的度數為 d(1)=2，d(2)=2，d(3)=1，d(4)=1，d(5)=3，d(6)=1。下表左邊呈現算法的初始狀態，右邊是算法結束後的結果，其中標示橫線的數字代表度數減去 1，數對 (a_i,j) 是建立的邊。

\displaystyle \begin{array}{cccccccc} i&&&\vline&1&2&3&4\\\hline a_i&&&\vline&5&2&1&5\\\hline j&&&\vline& & & & \\\hline d(1)&\vline&2&\vline&&&&\\ d(2)&\vline&2&\vline&&&&\\ d(3)&\vline&1&\vline&&&&\\ d(4)&\vline&1&\vline&&&&\\ d(5)&\vline&3&\vline&&&&\\ d(6)&\vline&1&\vline&&&&\\\hline \end{array}~~\Rightarrow~~ \begin{array}{cccccccc} i&&&\vline&1&2&3&4\\\hline a_i&&&\vline&5&2&1&5\\\hline j&&&\vline&3&4&2&1\\\hline d(1)&\vline&2&\vline&2&2&\underline{1}&\underline{0}\\ d(2)&\vline&2&\vline&2&\underline{1}&\underline{0}&0\\ d(3)&\vline&1&\vline&\underline{0}&0&0&0\\ d(4)&\vline&1&\vline&1&\underline{0}&0&0\\ d(5)&\vline&3&\vline&\underline{2}&2&2&\underline{1}\\ d(6)&\vline&1&\vline&1&1&1&1\\\hline \end{array}

圖三顯示每一步驟的結果，紅色線條的頂點表示目前的度數等於 1，黃色頂點表示度數等於 1 的最小頂點 (即 j)，綠色頂點表示 a_i。圖三 (4) 是終止程序添加 e=(5,6) 之前的結果。

Tree3

圖三：Prüfer 序列 \to 標記樹

 
第二個問題：畫出包含 10 個頂點的所有同胚不可約樹，也就是說，畫出包含 10 個頂點的所有非標記樹，其中每一頂點的度數都不等於 2。為方便說明，我們仍以數字標記頂點。令 L 表示所有葉子所形成的集合，N 表示所有非葉子所形成的集合。明顯地，V=L\cup N，L 和 N 不為空集合且兩者無交集，故 \vert V\vert=\vert L\vert+\vert N\vert。使用樹的等價性質，由 \vert V\vert=10 可知 \vert E\vert=10-1=9。因為每一條邊連接兩個頂點，\sum_{v\in V}d(v)=2\vert E\vert=18。若 v\in L，則 d(v)=1。根據同胚不可約樹的定義，若 v\in N，則 d(v)\ge 3。所以，

\displaystyle 18=\sum_{v\in L}d(v)+\sum_{v\in N}d(v)\ge \vert L\vert+3\vert N\vert=\left(10-\vert N\vert\right)+3\vert N\vert=10+2\vert N\vert，

即 \vert N\vert\le 4。假設頂點按照度數大小以遞減方式排序，d(1)\ge d(2)\ge\cdots\ge d(10)。換句話說，非葉子排在前面，葉子排在後面。同胚不可約樹的設計方法是先解得非葉子的度數，據此畫出以非葉子為頂點的小樹，然後再按照度數長出葉子。下面分開四種情況討論。

  1. \vert N\vert=1：d(1)=18-9=9，我們得到一棵星狀樹，見圖四 (1)。
  2. \vert N\vert=2：d(1)+d(2)=18-8=10 且 d(1)\ge d(2)\ge 3 有三個解 (a) d(1)=7，d(2)=3，(b) d(1)=6，d(2)=4，(c) d(1)=d(2)=5。這三個解各自對應一棵樹，其中頂點 1 和 2 鄰接，見圖四 (2a)，(2b)，(2c)。
  3. \vert N\vert=3：d(1)+d(2)+d(3)=18-7=11 且 d(1)\ge d(2)\ge d(3)\ge 3 有兩個解 (a) d(1)=d(2)=4，d(3)=3，(b) d(1)=5，d(2)=d(3)=3。每一個解都存在二棵樹與之對應，解 (a) 的兩個度數為 4 的頂點鄰接或不鄰接，解 (b) 的兩個度數為 3 的頂點鄰接或不鄰接，見圖四 (3a)，(3b)。
  4. \vert N\vert=4：d(1)+d(2)+d(3)+d(4)=18-6=12 且 d(1)\ge d(2)\ge d(3)\ge d(4)\ge 3 有唯一解 d(1)=d(2)=d(3)=d(4)=3，我們得到二棵樹，其中一棵樹的一個度數為 3 的頂點未與任何葉子鄰接，另一棵樹的每一個度數為 3 的頂點都和至少一葉子鄰接，見圖四 (4)。
Tree4

圖四：同胚不可約樹

 
圖四的黑樹就是威爾畫在黑板上的 8 棵樹，綠樹是遺失的 2 棵樹。有此一說，威爾還沒來得及畫完最後 2 棵樹就被突然冒出的朗博教授給打斷了 (見“電影《心靈捕手》的數學問題 (二)”，YouTube 影片)。讀者不妨找一個不被打擾的安靜場所，運用上述方法畫出包含 11 個頂點的所有同胚不可約樹 (總計有 14 棵)。

 
參考來源：
[1] 維基百科：組合數學
[2] 維基百科：Cayley’s formula

繼續閱讀：
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