由本節開始,筆者介紹「著色」(Colouring)問題(註1)。「著色」問題與筆者以往介紹的各種「點算組合學」問題很不同,需要用到很多「抽象代數學」(Abstract Algebra)上的概念和知識(主要是「群論」Group Theory和「群作用」Group Action)。在了解這類問題的解題方法前,讀者須先具備「抽象代數學」的有關知識,因此在本節筆者將介紹與「著色」問題密切相關的「抽象代數學」概念和知識。
「著色」問題是指以下的問題:給定一個有限物件集合O = {O1 ... On}和一個有限顏色集合C = {C1 ... Cr},現要替O中n個物件的每一件填上C中r種顏色中的一種,問有多少種不同的著色方案?在實際應用上,O中的物件都表現為某種幾何形狀上的「組件」,例如在下圖中,O便表現為正方形的4個區域(註2),C則是由橙、綠、白三種顏色組成的集合:
上圖顯示了O的三個「著色」方案。容易看到,如果以上圖形是靜止不動的,那麼應共有34 = 81個不同的「著色」方案。可是,如果我們讓以上圖形進行某些「運動」,並且把運動前後的圖形視為同一個圖形,那麼情況就會很不同。舉例說,如果我們讓上面最左面的圖形繞其中心按逆時針方向旋轉90度,便會得到中間的圖形,因此在這種旋轉下,上面最左面和中間兩個圖形的「著色」方案可以視為相同。我們不僅可以考慮「旋轉」(Rotation)運動,也可考慮「反射」(Reflection)運動,例如讓上面最左面的圖形以其中垂線為對稱軸作反射(這相當於把該圖形從左到右翻轉過來),便會得到最右面的圖形。因此在上述兩種「運動」下,上面三個圖形的「著色」方案都可視為相同。一般的「著色」問題就是要求在容許作某些「運動」的條件下有多少種不同的「著色」方案。
接下來我們要把上段的概念表達為精確的數學語言,這裡涉及幾方面的概念。首先,上述各種「旋轉及/或反射運動」不是無組織的,而是構成一個「群」(Group)。「群」是「抽象代數學」上的一個基本概念,其定義如下,設有一個集合G和該集合上的「運算」(Operation)「•」(我們可以把這個「•」看成抽象的乘法),如果G的元素和「•」滿足以下條件,我們便說(G, •)構成一個「群」:
|
根據以上定義,上述的各種「標準運動」便是集合G的元素。在「抽象代數學」中,這個「標準運動群」有一個專有名稱:「4階二面體群」(Dihedral Group of Degree 4),一般記作D4。D4所包含的「標準運動」包括:繞圖中心按逆時針方向旋轉0度(以e表示)、旋轉90度(以r表示)、旋轉180度(以r2表示)、旋轉270度(以r3表示)(註3)、以中垂線為對稱軸作反射運動(以v表示)、以穿過圖中心的水面線為對稱軸作反射運動(以h表示)、以圖形的「主對角線」(即從左上角到右下角的對角線)為對稱軸作反射運動(以m表示),以及以圖形的「副對角線」(即另一條對角線)為對稱軸作反射運動(以n表示)。上述運動的「複合」(Composition)構成D4上的「運算」「•」。舉例說,如果我們對上面最左面圖形進行h運動,便可得到上面中間的圖形,接著如果再對該圖形作r2運動,便可得到上面最右面的圖形。可是這個圖形正好是對最左面圖進行v運動後所得的結果。以上結果可以表達為以下算式:
由此可見,有了「群」的概念,我們便可以把幾何「運動」及其複合看成集合的元素及其運算,這樣做的好處是我們可以借助「抽象代數學」的結果來解決某些幾何變換的問題。嚴格地說,我們應證明上述的D4的確滿足上列的「群」定義的四個條件,但由於本網頁的主旨並非介紹「抽象代數學」,筆者將略去有關證明,只想在這裡指出,D4的「單位元」就是e,即相當於不作任何「運動」。而D4中每個元素的「逆元」則是有關運動的「逆運動」,例如r的「逆運動」就是r3,這是因為
除了「群」的概念外,我們還需要「子群」和「陪集」的概念。對於一個「群」(G, •)而言,如果存在G的一個「子集」H,運算「•」在H中滿足上述「群」定義的四個條件,我們便說(H, •)是(G, •)的「子群」(Subgroup)。舉例說,對於上述的D4,我們可以把H定義為D4中的「旋轉運動」。在「抽象代數學」中,這個「旋轉運動群」也有一個專有名稱:「4階循環群」(Cyclic Group of Degree 4),一般記作C4,即C4 = {e, r, r2, r3}。那麼容易證明,(C4, •)滿足「群」的定義,因此(C4, •)是(D4, •)的「子群」。
設有(G, •)的某個「子群」(H, •),那麼對應於這個「子群」以及G中任一元素g的「左陪集」(Left Coset) g • H定義如下:
即把g逐一「乘」以H中每一個元素後所得元素的集合(註5)。以上文的D4和C4為例,那麼對應於C4和元素v的「左陪集」v • H便是
請注意如果我們用上述D4中另外兩個元素r和h分別構造「左陪集」r • H和h • H,所得結果為
以上結果其實只是以下定理(證明從略)的特例(以下定理的第5點在「抽象代數學」中稱為「拉格朗日定理」Lagrange's Theorem):
定理1:對於任何「群」(G, •)及其「子群」(H, •)而言,
|
以上文的D4和C4為例,我們看到C4共有兩個「左陪集」:C4和v • C4 (註6),即|D4:C4| = 2。這兩個「左陪集」剛好構成D4的一個「劃分」。此外,由於|D4| = 8,|C4| = 4,|D4|、|D4:C4|和|C4|滿足上述定理中第5點的等式。
以上筆者介紹了如何利用「群」的概念來刻劃幾何「運動」的特性,我們還需要把這些幾何「運動」與受其影響的物件聯繫起來。為此,我們要引入「群作用」(Group Action)的概念。設有一個群(G, •)和一個集合X,如果對應於G中的每個元素g,都有X上的一個函數g*,並且滿足以下條件,我們便說G「作用」於X:
|
舉例說,我們可以把G設定為前文介紹的正方形「標準運動」組成的集合,即D4,X則是下圖的四個區域,分別用1、2、3、4代表,並把這個集合記作O。對應於D4的元素r (即「旋轉90度」),我們有O上的函數r*:r*(1) = 2, r*(2) = 3, r*(3) = 4, r*(4) = 1。
可是以上這種表達函數的方法十分累贅,我們至少有兩種簡化的記法。第一種方法是按某種既定的順序把函數的輸出值列出。這種方法稱為「一行式」(One Line Notation),例如上述函數r*的「一行式」便是
這裡我們約定上式中的第1個值是r*(1)、第2個值是r*(2),如此類推。由於有這種約定,我們無需把函數的輸入值列出,而只需列出其輸出值。
第二種方法是按以下方式把X的元素排在一行內:首先任意選取第1個元素,函數會把這個元素映射到某一個輸出值,我們以這個輸出值作為第2個元素。函數又會把這第2個元素映射到某一個輸出值,我們以這個輸出值作為第3個元素。如此類推,直至函數剛好把第n個元素映射到第1個元素,這樣便完成了一個「循環」。這種方法稱為「循環式」(Cycle Notation),例如上述函數r*的「循環式」便是
在上式中,1是任意選取的。由於r*(1) = 2,所以我們把2放在1之後。由於r*(2) = 3,所以我們把3放在2之後。如此類推,直至最後一個數字4,由於r*(4) = 1,而1剛好是第1個元素,我們完成了一個「循環」,且已窮盡O的所有元素,所以上式就是r*的「循環式」。由於「循環式」中的第1個元素是任意選取的,所以「循環式」可以有多種等價的寫法,例如以下幾個「循環式」雖然在表面上各不相同,但其實都等同於(1 2 3 4):
有些「群作用」的結果會表現為多個「循環」的形式。舉例說,當我們以D4中元素v作用於O時,所得結果為:
以上這個函數v*可表達為以下的「循環式」:
請注意在v的「作用」下,數字1、2互相對調,數字3、4也互相對調,但1、2與3、4之間卻互不相干,因此以上「循環式」表現為兩個「循環」。當然,各個「循環」之間的次序是無關重要的,因此上式也可重寫為以下形式:
當我們以D4中元素e作用於O時,全部四個數字保持不變。在此一「群作用」下,1、2、3、4這四個數字互不相干,因此其「循環式」應表現為四個「循環」,並可表達為以下任何一種形式:
有了「一行式」和「循環式」,我們便可以用很簡潔的方式表達「群作用」。為方便以後的討論,下表列出D4每個元素「作用」於O的結果的兩種表達形式。
D4的元素g | g*的「一行式」 | g*的「循環式」 |
---|---|---|
e | [1 2 3 4] | (1)(2)(3)(4) |
r | [2 3 4 1] | (1 2 3 4) |
r2 | [3 4 1 2] | (1 3)(2 4) |
r3 | [4 1 2 3] | (1 4 3 2) |
v | [2 1 4 3] | (1 2)(3 4) |
h | [4 3 2 1] | (1 4)(2 3) |
m | [3 2 1 4] | (1 3)(2)(4) |
n | [1 4 3 2] | (1)(2 4)(3) |
利用「一行式」或「循環式」,我們可以容易計算「群作用」複合的結果。下圖顯示前面提過的一個等式:r2 • h = v。利用上面「群作用」定義中的第1個條件,我們應有,對於O中任何元素x而言,r2*(h*(x)) = v*(x)。
現在讓我們驗證以上等式。首先,利用表1所列的「一行式」,我們計算得:
運算法則如下:對於元素1而言,根據上面第二個「一行式」,h*把1映射到4。接著根據第一個「一行式」,r2*又把4映射到2,所以這兩個「群作用」的複合結果為把1映射到2。O中其他元素的映射結果也可用相同方法求得。以上結果[2 1 4 3]正好是v*的「一行式」,以上等式乃得以驗證。
接著利用表1所列的「循環式」,我們計算得:
運算法則如下:首先考慮元素1。根據上面第三個「循環式」(1 4),h*把1映射到4。接著根據上面第二個「循環式」(2 4),r2*又把4映射到2。接著考慮元素2。根據上面第四個「循環式」(2 3),h*把2映射到3。接著根據上面第一個「循環式」(1 3),r2*又把3映射到1。因此這兩個「群作用」的複合結果為把1映射到2,並且把2映射到1,即(1 2)構成一個循環。元素3和4的映射結果也可用相同方法求得。以上結果(1 2)(3 4)正好是v*的「循環式」,以上等式乃得以驗證。
利用「一行式」或「循環式」,我們也容易計算「群作用」的「逆元」。舉例說,我們可以用以下方法求r的「逆元」r−1。根據r的「一行式」[2 3 4 1],r把4映射到1,因此r−1應把1映射到4。利用上述方法,容易求得[2 3 4 1]的「逆元」為[4 1 2 3]。根據表1,[4 1 2 3]就是r3的「一行式」,由此我們知道r−1 = r3。
利用「循環式」求「逆元」的運算法則更為簡單。舉例說,根據表1,r2的「循環式」為(1 3)(2 4),我們只需把各個「循環」中的數字按逆序重寫出來,便求得其「逆元」,即(r2)−1 = (3 1)(4 2)。不過由於(3 1)(4 2)實際等於(1 3)(2 4),我們求得(r2)−1 = r2。
我們還需要兩個與「群作用」有關的概念:「穩定集」和「軌道」。對於X中任一元素x,其在G的「作用」下的「穩定集」(Stabilizer)為
換句話說,當Stab(x)中的元素「作用」於x時,x保持不變。
對於X中任一元素x,其在G的「作用」下的「軌道」(Orbit)為
換句話說,如果某個「群作用」g*把x映射到X中某個元素y,則y就是Orb(x)的成員。
「穩定集」和「軌道」有以下特性:
定理2:對於任何群(G, •)和集合X而言,
仍以前面的D4和O為例。根據表1,元素1在e和n的「作用」下保持不變,所以Stab(1) = {e, n}。容易看到({e, n}, •)構成(D4, •)的一個「子群」。另外,根據表1,元素1在G中元素的「作用」下會被映射到1、2、3、4,因此Orb(1) = {1, 2, 3, 4}。顯然{Orb(1)}構成O的一個「劃分」,因此|O / D4| = 1。下文將會說明,|X / G|對於求解「著色」問題有非常重要的意義。
在以上討論中,受「群作用」影響的集合X都是幾何圖形上的「組件」,但其實X可以是更一般的「對象」。就「著色」問題而言,X可以是由「著色」方案組成的集合,我們把這個集合記作F。我們可以把一個「著色」方案看成一個函數,這個函數把物件集合O映射到顏色集合C。以下列這兩個F的元素為例(註9):
我們可以把這兩個「著色」方案表達為以下的「一行式」:
以上兩式分別代表上圖左、右兩個「著色」方案,o、g和w分別代表橙色、綠色和白色。接著我們考慮D4對F的「作用」。請注意我們不能把表1所列的「一行式」直接應用於F的元素,這是因為表1的「一行式」是就D4「作用」於O而言的。現在D4的「作用」對象是F而非O,因此以下用g**來表示D4的元素g對F的「作用」,而g*則表示g對O的「作用」,並希望求得g**與g*的關係。為此,我們首先集中研究D4的元素r對F的「作用」。上面右圖正是r「作用」於左圖的結果,因此我們應有
根據表1,r*的「一行式」為[2 3 4 1]。根據上面介紹的「一行式」的運算法則,[2 3 4 1]與[o g o w]和[w o g o]存在以下關係:
看到這裡,有些讀者可能會覺得這個關係式違反他們的「直觀」。筆者必須指出,「直觀」有時是不準確的。事實上,只要驗證一下上述關係式,便能證明其正確性。以元素1為例,根據等號右端第二個「一行式」,r*把1映射到2。接著根據等號右端第一個「一行式」(即「著色」方案[w o g o]),該方案把2映射到o。這兩個「一行式」的複合結果就是把1映射到o,而等號左端的「一行式」的第1個元素正是o。讀者可自行驗證以上關係式對其他元素也是正確的。
現在我們把上式左右兩端同時「乘」以[2 3 4 1]的「逆元」(即(r*)−1),便得
比較(1)和(2),我們可得出以下結論:
由於在上述推導中,r和[o g o w]並無特殊性,我們可以把上述結果推廣到一般情況,即對D4中任何元素g和F中任何元素f而言,都有
至此我們找到了g**的表達式,我們還要證明它滿足上面「群作用」的定義。對G中任何兩個元素g和h以及F中任何元素f而言,
(g • h)**(f) | = f[(g • h)*]−1 |
  | = f(g*h*)−1 |
  | = f(h*)−1(g*)−1 |
  | = g**[f(h*)−1] |
  | = g**h**(f) |
e**(f) | = f(e*)−1 |
  | = fe* |
  | = f |
以上證明了g**的確是g對F的「群作用」。接著我們便可以定義F中任一元素f在D4的「作用」下的「軌道」:
舉例說,由於根據等式(1),r**([o g o w]) = [w o g o],我們知道[w o g o] ∈ Orb([o g o w]),即上圖中的兩個「著色」方案屬於同一「軌道」。用通俗的語言表達,[o g o w]和[w o g o]屬於同一「軌道」,是因為我們可以透過「逆時針旋轉90度」這個「運動」把前者轉換為後者。一般地,對於F中任何兩個「著色」方案f和h而言,如果我們可以透過某種「運動」把f轉換為h,那麼f和h屬於同一「軌道」。由於我們把任何兩個可在某「運動」下互相轉換的「著色」方案視作相同(例如[o g o w]和[w o g o]便可視作相同的「著色」方案),因此「著色」方案的數目便等於F的「軌道」的數目,即|F / G|。
至此我們可以用精確的數學語言表述「著色」問題:
設有「物件」集合O和「顏色」集合C,並容許O作「運動」(「運動」集合用G表示),現要用C中元素對O中元素著色,並把「著色」方案表達為從O映射到C的函數(「著色」方案集合用F表示)。如果我們把任何兩個可在某「運動」下互相轉換的「著色」方案視作相同,那麼不同的「著色」方案數目便等於在G「作用」下F的「軌道」數目|F / G|。 |
至此我們把求解「著色」問題歸結為求解以上定義中「軌道」數目的問題,求解的具體方法將留待以後各節介紹。
註1:請不要把本網頁介紹的「著色」問題與「圖論」(Graph Theory)上的「四色問題」(Four Colour Problem)相混淆。