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

本文的閱讀等級:中級

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

(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 的兩個端點,我們稱 uv 鄰接,記為 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)=2d(2)=2d(3)=1d(4)=1d(5)=3d(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)=1x=yI(x,y)=0x\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 0d(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)=2d(2)=2d(3)=1d(4)=1d(5)=3d(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 NLN 不為空集合且兩者無交集,故 \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=1d(1)=18-9=9,我們得到一棵星狀樹,見圖四 (1)。
  2. \vert N\vert=2d(1)+d(2)=18-8=10d(1)\ge d(2)\ge 3 有三個解 (a) d(1)=7d(2)=3,(b) d(1)=6d(2)=4,(c) d(1)=d(2)=5。這三個解各自對應一棵樹,其中頂點 12 鄰接,見圖四 (2a),(2b),(2c)。
  3. \vert N\vert=3d(1)+d(2)+d(3)=18-7=11d(1)\ge d(2)\ge d(3)\ge 3 有兩個解 (a) d(1)=d(2)=4d(3)=3,(b) d(1)=5d(2)=d(3)=3。每一個解都存在二棵樹與之對應,解 (a) 的兩個度數為 4 的頂點鄰接或不鄰接,解 (b) 的兩個度數為 3 的頂點鄰接或不鄰接,見圖四 (3a),(3b)。
  4. \vert N\vert=4d(1)+d(2)+d(3)+d(4)=18-6=12d(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

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