在《點算的奧秘:著色問題的基礎知識》中,筆者介紹了求解「著色」問題的基礎知識,其中包括「群」、「陪集」、「群作用」、「穩定集」、「軌道」等重要概念。在本節筆者將介紹如何利用這些概念求解基本的「著色」問題。為方便以下討論,現從上述網頁摘引有關「著色」問題的精確數學定義:
設有「物件」集合O和「顏色」集合C,並容許O作「運動」(「運動」集合用G表示),現要用C中元素對O中元素著色,並把「著色」方案表達為從O映射到C的函數(「著色」方案集合用F表示)。如果我們把任何兩個可在某「運動」下互相轉換的「著色」方案視作相同,那麼不同的「著色」方案數目便等於在G「作用」下F的「軌道」數目|F / G|。 |
根據以上定義,求解「著色」問題就是求|F / G|。我們首先需要以下的「軌道-穩定集定理」(Orbit-Stabilizer Theorem)。
定理1:設有一個「群」(G, •)作用於一個集合X,則對X中任何元素x而言,均有|G| = |Orb(x)| × |Stab(x)|,其中Stab(x)和Orb(x)分別為x的「穩定集」和「軌道」。
證明:我們首先定義由Stab(x)的「左陪集」組成的集合L(x),並證明Orb(x)的元素與L(x)的元素存在「一一對應關係」(One-one Correspondence)。根據前述網頁中的定義,Orb(x)的元素可表達為g*(x),其中g &isin G;而L(x)中的元素(即Stab(x)的「左陪集」)則可表達為g • Stab(x),其中g &isin G。現在我們定義一個由Orb(x)映射到L(x)函數f:
只要我們證明了上述的函數f是「一對一」(One-one)和「到上」(Onto)函數,便等於證明了Orb(x)與L(x)之間的「一一對應關係」(註1)。首先證明f是「一對一」函數。取G中任意兩個元素g和h,並設f[g*(x)] = f[h*(x)],即g • Stab(x) = h • Stab(x)。那麼根據上述網頁定理1的第3點,g和h屬於同一個「左陪集」。而根據定理1的第1點,我們有h ∈ g • Stab(x)。因此,根據「左陪集」的定義,我們有h = g • s,其中s ∈ Stab(x)。利用「群作用」定義中的條件1和Stab(x)的定義,我們有h*(x) = (g • s)*(x) = g*(s*(x)) = g*(x)。這樣,從f[g*(x)] = f[h*(x)],我們推得g*(x) = h*(x),由此證得f是「一對一」函數。其次證明f是「到上」函數,這是容易的。設有Stab(x)的某個「左陪集」g • Stab(x),那麼由於g ∈ G,必有對應於g的「群作用」g*,而根據f的定義,必有f[g*(x)] = g • Stab(x)。至此我們證明了f是「一對一」和「到上」函數,因此Orb(x)與L(x)存在「一一對應關係」。我們可以把這個結果概括為
根據上述網頁定理2的第1點,Stab(x)是G的「子群」,因此根據該網頁定理1的第5點,我們有以下等式:
可是|G:Stab(x)|正是Stab(x)的「左陪集」的個數,即|G:Stab(x)| = |L(x)|。把這個結果結合上面(1)和(2),遂有
以下用一個實例來驗證定理1。設G為上述網頁所定義的正方形的「標準運動」組成的集合,即D4 = {e, r, r2, r3, v, h, m, n},並設X為正方形上4個區域的「著色」方案(即由區域集合O = {1, 2, 3, 4}映射到顏色集合C = {o, g}的函數)組成的集合,並把這個集合稱為F。例如下圖便顯示F的一個元素:
我們把以上「著色」方案表達為「一行式」[o g o g]。接著讓我們利用上述網頁的公式(3)、表1以及「一行式」的運算法則求
舉例說,取g = r = [2 3 4 1]代入上式,便有
只要把D4的元素逐個代入g,便可求得Orb([o g o g]),其最終計算結果為:
接著求
舉例說,取g = r2 = [3 4 1 2]代入上式,便有
由於r2**([o g o g]) = [o g o g],所以[o g o g] ∈ Stab([o g o g])。利用此一方法,容易求得
由於|D4| = 8,|Orb([o g o g])| = 2,|Stab([o g o g])| = 4,這三者滿足公式(3)所表達的關係。
接著我們便可以推導求解「著色」問題的公式。
定理2:設G和F為以上定義的「運動」集合和「著色」方案集合,則
證明:我們首先證明對F中任一「軌道」Orb(k)而言,以下等式成立:
根據「軌道」的定義,k ∈ Orb(k),因此若f ∈ Orb(k),則f與k屬於同一個「軌道」,而根據上述網頁定理(2)的第2點,我們便得Orb(f) = Orb(k)。現在根據上面定理(1),我們有
Σf ∈ Orb(k) |Stab(f)| | = Σf ∈ Orb(k) |G| / |Orb(f)| |
  | = Σf ∈ Orb(k) |G| / |Orb(k)| |
  | = |Orb(k)| × |G| / |Orb(k)| |
  | = |G| |
由於對F中每一個「軌道」,公式(4)均成立;而F共有|F / G|個「軌道」,而且F中每一個元素均屬於剛好一個「軌道」,因此我們可以把公式(4)擴展為
對上式作簡單的代數變換,便可得到我們要證明的公式。□
以下我們以一個看定理2的應用。
例題1:設O、C、D4和F為上文定義的正方形區域、顏色、「標準運動」和「著色」方案集合。試求有多少種不同的「著色」方案。
答1:我們運用定理2來求|F / D4|。對於F中每一個元素f,我們先要求出|Stab(f)|。由於共有4個區域,每個區域可填上2種顏色,F共有24 = 16個元素。下表列出這16個元素的「穩定集」:
f | Stab(f) | |Stab(f)| |
---|---|---|
[o o o o] | {e, r, r2, r3, v, h, m, n} | 8 |
[o o o g] | {e, m} | 2 |
[o o g o] | {e, n} | 2 |
[o o g g] | {e, v} | 2 |
[o g o o] | {e, m} | 2 |
[o g o g] | {e, r2, m, n} | 4 |
[o g g o] | {e, h} | 2 |
[o g g g] | {e, n} | 2 |
[g o o o] | {e, n} | 2 |
[g o o g] | {e, h} | 2 |
[g o g o] | {e, r2, m, n} | 4 |
[g o g g] | {e, m} | 2 |
[g g o o] | {e, v} | 2 |
[g g o g] | {e, n} | 2 |
[g g g o] | {e, m} | 2 |
[g g g g] | {e, r, r2, r3, v, h, m, n} | 8 |
因此,根據定理2,|F / D4| = (8 × 2 + 4 × 2 + 2 × 12) / 8 = 6。□
上題的解答顯示,定理2不是求解「著色」問題的有效方法,因為我們必須逐一計算F中每個元素的「穩定集」。由於F的元素是由O映射到C的函數,只要O或C的元素個數頗多,我們的計算量便會很大。舉例說,假如我們把正方形分為9個區域,而顏色的數目為3個,那麼F便有39 = 19683個元素,要求這19683個元素的「穩定集」幾乎是不可行的事。
造成上述困難的主要原因是,定理2的計算乃建基於F,而F的元素個數可能很大。我們必須設法把|F / G|的計算改為建基於G,因為G的元素個數通常不很大。為此,我們引入一個新的「固定集」概念。對於G中任一元素g,其「固定集」(Fix)為
請注意「固定集」的定義與「穩定集」的定義非常相似,兩者不同之處在於,「固定集」是以G的元素為其「參數」並以F的元素為其成員,而「穩定集」則是以F的元素為其「參數」並以G的元素為其成員。「固定集」的重要性在於,它使|F / G|的計算可以建基於G。我們有以下的「伯恩賽德引理」(Burnside's Lemma):
定理3:設G和F為以上定義的「運動」集合和「著色」方案集合,則
證明:以上公式與定理2的公式非常相似,只要能夠證明
本定理便得證。我們首先看看上式等號左端的式子。根據Σf ∈ F |Stab(f)|的定義,這個式子其實是代表以下集合的元素個數:
以上集合由「有序對」(f, g)組成,對應於每一個f,我們列出所有滿足關係式g**(f) = f的g,即Stab(f)的所有元素。
我們也可以把上述「有序對」中的f和g對調,從而得到以下集合:
這個集合由「有序對」(g, f)組成,對應於每一個g,我們列出所有滿足關係式g**(f) = f的f,即Fix(g)的所有元素。因此這個集合的元素個數可表達為Σg ∈ G |Fix(g)|,即等式(5)等號右端的式子。
上述兩個集合顯然是同一個集合,因此它們的元素個數應相同,由此我們證得等式(5)是成立的,本定理得證。
□
例題2:試用定理3再次求解例題1。
答2:我們固然可以像例題1的解答那樣製作一個表,就每個g列出相應的Fix(g)的全部元素。但這樣做跟答1的做法其實相差無幾,所以仍是沒有效率的解題方法。因此,在計算|Fix(g)|時,我們應運用一些推理技巧,而不是嘗試列出Fix(g)的全部元素。在進行推理時,我們可以利用上述網頁表1中各個g*的「循環式」(註2)。
我們首先以r為例看看如何進行這種推理。根據表1,r的「循環式」為(1 2 3 4)。這個「循環式」告訴我們,r把1映射到2 ... 把4映射到1。因此,如果我們希望在對某一「著色」方案f進行r運動後仍然得到原來的f (即r**(f) = f),則1、2、3和4必須填上相同的顏色。由於共有2種可供選擇的顏色,所以共有21 = 2個「著色」方案在r運動下保持不變,即|Fix(r)| = 2。
我們再考慮r2。根據表1,r2的「循環式」為(1 3)(2 4)。由此得知,r2把1和3互相映射到對方,又把2和4互相映射到對方。因此,如果我們希望在對f進行r2運動後仍然得到原來的f (即r2**(f) = f),則1和3必須填上相同的顏色,而2和4也必須填上相同的顏色。由此得知,共有22 = 4個「著色」方案在r2運動下保持不變(註3),即|Fix(r2)| = 4。
我們可以把上述推理推廣到一般情況。假設某個g含有N個「循環」(不論各個「循環」的長度為何),如果我們希望在對f進行g運動後仍然得到原來的f (即g**(f) = f),則處在同一「循環」內的元素必須填上相同的顏色。由此得知,共有2N個「著色」方案在g運動下保持不變,即|Fix(g)| = 2N。
循著以上思路逐一考慮D4中每一成員,便可求得各個|Fix(g)|。現把計算結果列成下表:
D4的元素g | g*的「循環式」 | |Fix(g)| |
---|---|---|
e | (1)(2)(3)(4) | 24 = 16 |
r | (1 2 3 4) | 21 = 2 |
r2 | (1 3)(2 4) | 22 = 4 |
r3 | (1 4 3 2) | 21 = 2 |
v | (1 2)(3 4) | 22 = 4 |
h | (1 4)(2 3) | 22 = 4 |
m | (1 3)(2)(4) | 23 = 8 |
n | (1)(2 4)(3) | 23 = 8 |
現在,應用定理3,|F / D4| = (16 + 8 × 2 + 4 × 3 + 2 × 2) / 8 = 6,所得結果與例題1完全吻合。□
以上例題顯示,「著色」問題的解答取決於每個g*所含「循環」的數目。為了使我們的求解公式更能反映g*所含「循環」的數目,以下引入「循環類型」和「循環指數」的概念。
對某一「群作用」g*而言,其「循環類型」(Cycle Type)(可記作Z[g*])記載了g*所含各種長度的「循環」的數目。舉例說,e*的「循環式」由4個長度為1的「循環」組成,因此我們把Z[e*]記作z14,其下標1代表「循環」的長度,上標4代表「循環」的數目。同理,n*的「循環式」由2個長度為1和1個長度為2的「循環」組成,因此我們把Z[n*]記作z12z2 (指數為1時可以不寫出)。
由於Z[g*]反映了g*所含「循環」的數目,而根據例題2的解答,|Fix(g)| = cN (其中c為顏色的數目,N為g*所含「循環」的數目),我們可以預期,Z[g*]與|Fix(g)|有極為密切的關係。仍以例題2中的D4為例,當g = e時,Z[e*] = z14,它告訴我們e*含有4個循環。如果我們把這裡的z1換成2,便得到|Fix(e)| = 24;當g = n時,Z[n*] = z12z2,它告訴我們n*含有3個循環。如果我們把這裡的z1和z2換成2,便得到|Fix(n)| = 23。這裡清楚顯示一個規律,對於任何g而言,只要我們把Z[g*]中的z1、z2等統統換成顏色數目2,所得結果就等於|Fix(g)| (註4)。
確定了對應於G中元素g的Z[g*]後,我們便可以定義G的「循環指數」(Cycle Index)(記作Z[G])如下:
舉例說,利用上面的表2,容易求得Z[D4]為
我們可以把上式看作以z1、z2 ...為「不定項」的「多項式」。為了突出上式所含的「不定項」,我們可以把Z[D4]寫成Z[D4](z1, z2, z4)。請注意Z[G]的定義與定理3的公式完全對應,因此我們可以把定理3改寫成「循環指數」的形式。事實上,如果我們把上式中的「不定項」當作「變項」,並把顏色數目2代入這些「變項」,便可得到以下結果:
此一結果正是例題2的答案。事實上,利用Z[g*]與|Fix(g)|,以及Z[G]與定理3中公式的對應關係,我們可以把定理3改寫為以下的「波利亞定理」(Polya's Theorem)(「伯恩賽德引理」和以下的「波利亞定理」又可合稱「伯恩賽德-波利亞定理」Burnside-Polya Theorem):
定理4:設G和F為以上定義的「運動」集合和「著色」方案集合,Z[G](z1, ... zn)為G的「循環指數」,c為顏色的數目(即c = |C|),則
至此我們終於找到了求解「著色」問題的有效公式。定理4較定理3的優勝之處在於,前者把計算建基於g* (因為Z[G]的定義是建基於Z[g*]),後者則把計算建基於g** (因為Fix(g)的定義是建基於g**),而在一般情況下,g**所涉及的對象數目遠較g*為多,因此利用定理4會較為簡便。
例題3:設O為以下正方形的9個區域,C = {o, g, w}為顏色集合,D4和F為「標準運動」和「著色」方案集合。試求有多少種不同的「著色」方案。
答3:我們須先就D4的每個元素g寫出相應的Z[g*]。請注意由於本題O的元素不是前面定義的正方形的4個區域,我們必須重新計算每個g*的「循環式」和Z[g*]。現把計算結果列於下表:
D4的元素g | g*的「循環式」 | Z[g*] |
---|---|---|
e | (1)(2)(3)(4)(5)(6)(7)(8)(9) | z19 |
r | (1 7 9 3)(2 4 8 6)(5) | z1z42 |
r2 | (1 9)(2 8)(3 7)(4 6)(5) | z1z24 |
r3 | (1 3 9 7)(2 6 8 4)(5) | z1z42 |
v | (1 3)(2)(4 6)(5)(7 9)(8) | z13z23 |
h | (1 7)(2 8)(3 9)(4)(5)(6) | z13z23 |
m | (1)(2 4)(3 7)(5)(6 8)(9) | z13z23 |
n | (1 9)(2 6)(3)(4 8)(5)(7) | z13z23 |
根據表3,容易求得Z[D4]為
根據定理4,本題答案為