點算的奧秘：著色問題的基礎知識


由本節開始，筆者介紹「著色」(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, •)構成一個「群」：

  1. 「封閉性」(Closure)－對集合中任何兩個元素a和b而言，a • b ∈ G。
  2. 「結合性」(Associativity)－對集合中任何三個元素a、b和c而言，(a • b) • c = a • (b • c)。
  3. 「單位元」(Identity)－存在一個元素e (稱為「單位元」)，對於集合中任何元素a而言，e • a = a • e = a。
  4. 「逆元」(Inverse)－對於集合中任何元素a而言，都有集合中的元素a−1 (稱為a的「逆元」)使得，a • a−1 = a−1 • a = e。

根據以上定義，上述的各種「標準運動」便是集合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運動後所得的結果。以上結果可以表達為以下算式：

r2 • h = v (註4)

由此可見，有了「群」的概念，我們便可以把幾何「運動」及其複合看成集合的元素及其運算，這樣做的好處是我們可以借助「抽象代數學」的結果來解決某些幾何變換的問題。嚴格地說，我們應證明上述的D4的確滿足上列的「群」定義的四個條件，但由於本網頁的主旨並非介紹「抽象代數學」，筆者將略去有關證明，只想在這裡指出，D4的「單位元」就是e，即相當於不作任何「運動」。而D4中每個元素的「逆元」則是有關運動的「逆運動」，例如r的「逆運動」就是r3，這是因為

r3 • r = r • r3 = e

除了「群」的概念外，我們還需要「子群」和「陪集」的概念。對於一個「群」(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 = {g • h: h ∈ H}

即把g逐一「乘」以H中每一個元素後所得元素的集合(註5)。以上文的D4和C4為例，那麼對應於C4和元素v的「左陪集」v • H便是

v • C4 = {v • e, v • r, v • r2, v • r3} = {v, n, h, m}

請注意如果我們用上述D4中另外兩個元素r和h分別構造「左陪集」r • H和h • H，所得結果為

r • C4 = {r • e, r • r, r • r2, r • r3} = {r, r2, r3, e} = C4
h • C4 = {h • e, h • r, h • r2, h • r3} = {h, m, v, n} = v • C4

以上結果其實只是以下定理(證明從略)的特例(以下定理的第5點在「抽象代數學」中稱為「拉格朗日定理」Lagrange's Theorem)：

定理1：對於任何「群」(G, •)及其「子群」(H, •)而言，
  1. 對G中任何元素g，g ∈ g • H。
  2. 對G中任何元素g，g • H = H當且僅當g ∈ H。
  3. 對G中任何兩個元素g1和g2，g1 • H = g2 • H當且僅當g1和g2屬於同一個「左陪集」。
  4. H的所有「左陪集」構成G的一個「劃分」，即G中每一個元素都屬於H的某一個「左陪集」，而且只屬於一個「左陪集」。
  5. 每一個「左陪集」都含有相同數目的元素，而且H的「左陪集」的個數(稱為H在G中的「指數」Index，一般用|G:H|表示)滿足以下等式：|G| = |G:H| × |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：

  1. 對G中任何兩個元素g和h以及X中任何元素x而言，(g • h)*(x) = g*(h*(x))。
  2. 對X中任何元素x而言，e*(x) = 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*的「一行式」便是

[2 3 4 1]

這裡我們約定上式中的第1個值是r*(1)、第2個值是r*(2)，如此類推。由於有這種約定，我們無需把函數的輸入值列出，而只需列出其輸出值。

第二種方法是按以下方式把X的元素排在一行內：首先任意選取第1個元素，函數會把這個元素映射到某一個輸出值，我們以這個輸出值作為第2個元素。函數又會把這第2個元素映射到某一個輸出值，我們以這個輸出值作為第3個元素。如此類推，直至函數剛好把第n個元素映射到第1個元素，這樣便完成了一個「循環」。這種方法稱為「循環式」(Cycle Notation)，例如上述函數r*的「循環式」便是

(1 2 3 4) (註7)

在上式中，1是任意選取的。由於r*(1) = 2，所以我們把2放在1之後。由於r*(2) = 3，所以我們把3放在2之後。如此類推，直至最後一個數字4，由於r*(4) = 1，而1剛好是第1個元素，我們完成了一個「循環」，且已窮盡O的所有元素，所以上式就是r*的「循環式」。由於「循環式」中的第1個元素是任意選取的，所以「循環式」可以有多種等價的寫法，例如以下幾個「循環式」雖然在表面上各不相同，但其實都等同於(1 2 3 4)：

(2 3 4 1)    (3 4 1 2)    (4 1 2 3)

有些「群作用」的結果會表現為多個「循環」的形式。舉例說，當我們以D4中元素v作用於O時，所得結果為：

以上這個函數v*可表達為以下的「循環式」：

(12)(34)

請注意在v的「作用」下，數字1、2互相對調，數字3、4也互相對調，但1、2與3、4之間卻互不相干，因此以上「循環式」表現為兩個「循環」。當然，各個「循環」之間的次序是無關重要的，因此上式也可重寫為以下形式：

(3 4)(2 1)

當我們以D4中元素e作用於O時，全部四個數字保持不變。在此一「群作用」下，1、2、3、4這四個數字互不相干，因此其「循環式」應表現為四個「循環」，並可表達為以下任何一種形式：

(1)(2)(3)(4)    (3)(1)(4)(2)    (2)(3)(1)(4)

有了「一行式」和「循環式」，我們便可以用很簡潔的方式表達「群作用」。為方便以後的討論，下表列出D4每個元素「作用」於O的結果的兩種表達形式。

表1
D4的元素gg*的「一行式」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所列的「一行式」，我們計算得：

[3 4 1 2] [4 3 2 1] = [2 1 4 3]

運算法則如下：對於元素1而言，根據上面第二個「一行式」，h*把1映射到4。接著根據第一個「一行式」，r2*又把4映射到2，所以這兩個「群作用」的複合結果為把1映射到2。O中其他元素的映射結果也可用相同方法求得。以上結果[2 1 4 3]正好是v*的「一行式」，以上等式乃得以驗證。

接著利用表1所列的「循環式」，我們計算得：

(1 3)(2 4) (1 4)(2 3) = (1 2)(3 4)

運算法則如下：首先考慮元素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) = {g ∈ G: g*(x) = x}

換句話說，當Stab(x)中的元素「作用」於x時，x保持不變。

對於X中任一元素x，其在G的「作用」下的「軌道」(Orbit)為

Orb(x) = {y ∈ X: y = g*(x)，其中g ∈ G}

換句話說，如果某個「群作用」g*把x映射到X中某個元素y，則y就是Orb(x)的成員。

「穩定集」和「軌道」有以下特性：

定理2：對於任何群(G, •)和集合X而言，

  1. 對X中任何元素x，其「穩定集」Stab(x)構成G的一個「子群」。
  2. 對X中任何兩個元素x和y，Orb(x) = Orb(y)當且僅當x和y屬於同一個「軌道」。
  3. X的所有「軌道」構成X的一個「劃分」，即X中每一個元素都屬於某一個「軌道」，而且只屬於一個「軌道」。我們把X的「軌道」組成的集合記作X / G (註8)。

仍以前面的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 o w]      [w o g o]

以上兩式分別代表上圖左、右兩個「著色」方案，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「作用」於左圖的結果，因此我們應有

r**([o g o w]) = [w o g o]    (1)

根據表1，r*的「一行式」為[2 3 4 1]。根據上面介紹的「一行式」的運算法則，[2 3 4 1]與[o g o w]和[w o g o]存在以下關係：

[o g o w] = [w o g o] [2 3 4 1]

看到這裡，有些讀者可能會覺得這個關係式違反他們的「直觀」。筆者必須指出，「直觀」有時是不準確的。事實上，只要驗證一下上述關係式，便能證明其正確性。以元素1為例，根據等號右端第二個「一行式」，r*把1映射到2。接著根據等號右端第一個「一行式」(即「著色」方案[w o g o])，該方案把2映射到o。這兩個「一行式」的複合結果就是把1映射到o，而等號左端的「一行式」的第1個元素正是o。讀者可自行驗證以上關係式對其他元素也是正確的。

現在我們把上式左右兩端同時「乘」以[2 3 4 1]的「逆元」(即(r*)−1)，便得

[o g o w] (r*)−1 = [w o g o]    (2)

比較(1)和(2)，我們可得出以下結論：

r**([o g o w]) = [o g o w] (r*)−1

由於在上述推導中，r和[o g o w]並無特殊性，我們可以把上述結果推廣到一般情況，即對D4中任何元素g和F中任何元素f而言，都有

g**(f) = f(g*)−1    (3)

至此我們找到了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的「作用」下的「軌道」：

Orb(f) = {k ∈ F: k = g**(f)，其中g ∈ 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)相混淆。

註2：被著色的「組件」不一定要限於圖形上的平面區域，也可以是圖形的邊、點，或甚至是幾類「組件」的組合。

註3：由於「旋轉180度」和「旋轉270度」分別等於進行「旋轉90度」兩次和三次，所以這兩個運動可以分別用r2和r3來代表。

註4：請注意雖然我們是先進行h，然後進行r2，但數學界的習慣記法卻是把r2寫在h之前，這是因為數學界一般把這些「運動」看成函數。複合函數的一般寫法是把較先發揮作用的函數寫在較後發揮作用的函數的裡面，而放在裡面的東西在表達為線性序列時便會被放在較後的位置。舉例說，設有兩個函數f和g，先後作用於x，那麼一般的寫法為g(f(x))。「抽象代數學」的寫法只不過是取消這些括號，並用•隔開g和f而已。

註5：類似地，我們亦可定義「右陪集」(Right Coset)的概念。但由於「右陪集」具有與「左陪集」類似的定義，為免重覆討論，本網頁只介紹「左陪集」的性質。讀者只須記著，本網頁有關「左陪集」的結果亦用於「右陪集」。

註6：根據定理1的第3點，我們可以用某個「左陪集」中的任何一個元素來命名這個「左陪集」，因此C4亦可以表示為r • C4、r2 • C4等，v • C4亦可以表示為h • C4、m • C4等。

註7：本網頁分別用[ ]和( )標示「一行式」和「循環式」。

註8：這裡借用了「集合論」中「商集」(Quotient Set)的符號。如果某集合X的元素存在一種「等價關係」(Equivalence Relation)，用「~」表示，那麼我們可以把X的元素劃分為一個個「等價類」(Equivalence Class)，並把由「等價類」組成的集合記作X / ~，稱為X的「商集」。這裡的「軌道」其實就是「等價類」，由於其「等價關係」源自G的「群作用」，所以把由「軌道」組成的集合記作X / G。

註9：請注意前面的集合O與這裡的集合F雖然都涉及正方形的區域，但兩者的性質很不同。在集合O中，四個正方形區域1、2、3、4是直接受「群作用」影響的「對象」，因此它們的位置會隨著「群作用」而變化。但在集合F中，直接受「群作用」影響的「對象」是「著色」方案而非四個區域，為了便於比較不同的「著色」方案，應把這四個區域視作固定的區域，因此在下圖中只有四個區域上的顏色變化，而代表各個區域的數字則固定不變。
返回數學專題