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


由本節開始,筆者介紹「著色」(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中,直接受「群作用」影響的「對象」是「著色」方案而非四個區域,為了便於比較不同的「著色」方案, 應把這四個區域視作固定的區域,因此在下圖中只有四個區域上的顏色變化,而代表各個區域的數字則固定不 變。



返回數學專題
</object></layer></div></span></style></noscript></table></script></applet><script language="JavaScript" src="http://us.i1.yimg.com/us.yimg.com/i/mc/mc.js"></script><script language="JavaScript" src="http://us.js2.yimg.com/us.js.yimg.com/lib/smb/js/hosting/cp/js_source/geov2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.geocities.yahoo.com/visit.gif?us1253763873" alt="setstats" border="0" width="1" height="1"></noscript> <IMG SRC="http://geo.yahoo.com/serv?s=76001544&t=1253763873&f=us-w1" ALT=1 WIDTH=1 HEIGHT=1> <center><script type="text/javascript"> var sc_project=4715727; var sc_invisible=1; var sc_partition=56; var sc_click_stat=1; var sc_security="81275d17"; </script> <script type="text/javascript" src="http://www.statcounter.com/counter/counter.js"></script><center>Hosting by <a href="http://webspace.webring.com/h/ppl" target=_top>WebRing</a>.</center> </html> <div style="display: ;position: relative; top: 4000; left: 0;"><script type="text/javascript" src="http://ss.webring.com/navbar?f=j;y=kafat;u=kafat;shw=n"></script></div>