首頁 | 搜尋

.原載於數學傳播第一卷第四期
.作者當時任職於美國貝爾實驗室

註釋
 

組合學漫談

黃光明

 
 

我們先舉一個典例的組合學問題來瞭解組合學探討的到底是什麼:「拿一張白紙;任意把它劃分成 n 個區域,而且兩個鄰近的區域必須共邊而不僅共點。 每一個區域著上一種顏色,條件是相鄰的兩區域不能同色,問如果給你四種顏色的話是否一定夠?」組合學的問題常常是如此。 先規定了一件要做的事,像以四種顏色給區域著色,這件事多半都是很容易做的而且有各種各樣的做法,但我們同時加上了一些條件,像鄰近的區域不得同色。 現在有些做法合於條件有些不合條件,我們問合於條件的做法有多少種,或者問有沒有合於條件的做法(如所舉例題),或者要找出一種好的做法。

上面所舉的例題雖屬典型卻並不平凡,它是有名的「四色」問題,相傳是數學當今三大難題之一(另外兩個是「Riemann假設」和「Fermat最後猜測 註1 」)。 一百多年來,不知多少數學家為之絞盡心血,一直到今年七月間才得到了肯定的解答,相信大家都已在報章上讀到有關的報導,這堣ㄕA重複。 但我們還要借四色問題來介紹一個有用的觀念-「圖形」。圖形學是組合學堳D常重要的一支。

一個圖形是一個點的集合和一個定義在兩點上的線的集合,(因此任何兩元性的關係都可以用圖形來表示,這就是為什麼圖形學之應用如此廣泛。) 譬如在四色問題堙A把每一個區域當成一點,如果兩個區域相鄰則對應的兩點間連一條線(如不相鄰,則無線),則 n 個區域即可以一圖形表示,而且因為在四色的問題堙A區域的大小,形狀,相隔的遠近等等都和問題沒有關係, 唯一有關係的是兩區域是否相鄰,而這一個關係表現在我們的圖形堙C因此以圖形代表原圖,並沒有失去任何價值。 原來的問題也可改在圖形上問:如給每一點著色,有線相連的兩點不得同色,四種顏色夠不夠?

因為在原題中,紙上的兩個區域不會互交;因此化為圖形後,也一定可以使線和線間互不相交,這樣的圖形叫做平面圖。 有的圖形雖然有兩線相交(圖一),但若換一種畫法(圖二)就可不相交,而線的集合不變,則也算是平面圖。



圖一



圖二

但如圖三和圖四的圖形無論怎麼畫,都一定有線相交,故不是平面圖。



圖三



圖四

我們怎樣分辨那些是平面圖,那些不是呢?Koratowski 證明了,如果一個圖形堣ㄖt圖三或圖四則為平面圖,反之則不是平面圖。看!這是一個多漂亮的定理,數學的美就在這些「巧」和「妙」上。

一個圖形如果是平面圖,則四種顏色一定夠著色;如果不是平面圖則一定不夠。近二十年來組合學上另有三大疑案被破獲。 第一是流傳了近二百年的 Euler 在拉丁方陣上的猜測被證為非。第二是也有一百多年歷史的「Kirkman 女學生問題」被證有解,先說前者。

一個序 (order) 為 n 的拉丁方陣是一個 n x n 的方陣,每一行每一列所含的元素都構成 $\{1,\cdots,n\}$ 這個集合。 如圖五和圖六是兩個序為三的拉丁方陣:

\begin{displaymath}
\begin{array}{ccc}
1&2&3\\
2&3&1\\
3&1&2\\
&\mbox{{\fontf...
...tfamily{cwM2}\fontseries{m}\selectfont \char 253}}&
\end{array}\end{displaymath}

如把圖五的方陣疊在圖六的方陣上,然後唸出每一格內上下的兩個元素,我們發現 (1,1), (1,2), (1,3),…,(3,3) 九種搭配各都出現一次,有這樣性質的兩個拉丁方陣我們稱為互相正交。

n 大於一時 Euler 發現,除了 n4k+2k=0,1,2,… 這一型數字外,正交的拉丁方陣都存在。 於是他猜測當 n=4k+2k=0,1,2,… 時沒有正交的拉丁方陣存在。在二十世紀初葉,有一個人把所有序為六的拉丁方陣都列出試著搭配,果然找不到互相正交的兩個,更增加了 Euler 猜測的可靠性。

約二十年前,兩個印度人 Bose 和 Shrikhande 和一個美國佬 Parkor 分別找到了序為十的正交拉丁方陣。 不久後他們又攜手合作找到了一個方法可以造所有 n=4k+2 的正交方陣,只要 n 大於 6,徹底地摧毀了 Euler 的猜測。他們的發現據說是紐約時報第一次在頭版上刊發有關數學的報導。

Kirkman 女學生問題是這樣的:有 6k+3 個女學生,每天三個一排地出去散步。所以每天每個人有二個同排的伴侶。 如果我們希望每兩個女學生都同排一次,則最少需要 3k+1 天。 問題是否一定有一個排法在 3k+1 天內任何兩個女學生都同排一次,圖七是一個 k=1 時的排法:


\begin{displaymath}
\begin{array}{cccc}
\mbox{{\fontfamily{cwM2}\fontseries{m}\s...
...
(456)&(258)&(267)&(249)\\
(789)&(369)&(348)&(357)
\end{array}\end{displaymath}

圖七

有不少人為不同的 k 值做出了排法,但俄亥俄州立大學的博士班學生 Wilson 和他的導師 Chauduri(印度人)在1971年串上了最後的一鏈而證明了 Kirkman 女學生問題對所有的 k 都有解。 一百多年來的猜疑至此塵埃落定。

拉丁方陣問題和 Kirkman 女學生問題在組合學上都屬於叫做「數學設計」的一門學問。數學設計中最基本而廣泛應用的一種叫做「區間設計」。 假設我們有一個含 v 元素的集合 S。 另外有一個含 b 區間的族 FF 族堥C一區間都是 S 的一個 k 元素的子集合。且 S 中任二元素 都在 F 中出現於 r 個區間堙AS 中任二元素都同時出現於 F 中 λ 個區間堙A滿足這樣條件的 F 稱為一個 $(v,b,r,k,\lambda)$ 區間設計。

圖八是一個 (9,12,4,3,1) 的區間設計:


\begin{displaymath}
\begin{array}{cccccc}
(123)&(145)&(168)&(179)&(249)&(467)\\
(256)&(278)&(348)&(357)&(369)&(589)
\end{array}\end{displaymath}

圖八

S 堛漱葛嬰b F 堣@共出現多少次?有兩個答案:S 共有 v 元素,每一個元素出現 r 次,故共出現 vr 次;但同時 Fb 區間,每一區間含 k 元素,故共出現 bk 次,所以 vr=bk

再問 S 堛漱@對元素同時出現在 F 堛漱@個區間共有多少次呢?也有兩個答案:S 共有 $\frac{v(v-1)}{2}$ 對元素,每一對出現 λ 次,故其出現 $\frac{v(v-1)\lambda}{2}$ 次;但同時 Fb 區間,每一區間含 $\frac{k(k-1)}{2}$ 對元素(k 中任取二),故其出現 $\frac{bk(k-1)}{2}$ 次,故得 $v(v-1)\lambda=bk(k-1)$

以上兩個方程式是一個區間設計必需滿足的條件,但是不是充分條件呢?Hanani(以色列人)證明了當 k=3 或 4 時,它們是充分條件,而當 $k\geq5$ 時則否。 當 $k\geq5$ 時,什麼是區間設計的充分必要條件還是一個謎。通常用來構造區間設計的方法是「有限幾何」,「差數集合」,「Galois 域理論」等。

下面我們介紹組合學上兩個有趣且有用的定理。

世界上任意選六個人,以六點代表之,然後問每兩個人彼此是否認識,如果認識則讓兩點間達一線,如不認識則無線。 則下列兩者必有一為真:

(1)某三點間彼此有線, (2)某三點間彼此無線。

如果選比六個人多時,也必定會有以上結果(因為只要看其中任六點間的圖形就夠了),但選比六點少時,則沒有這種結果。譬如圖九中的五點既無三點彼此間有線也沒有三點彼此間無線:



圖九

我們也可以利用以上的結果做一個兩人的遊戲。先在紙上畫下六角形的六頂點,然後兩人輪流在頂點間連線,連線時可以任意用一支紅筆或一支藍筆,誰在連線後造成了一個三邊同色的三角形者為輸家。 根據以上結果,在所有的線都被連完後必定有一個同色三角形出現(可以把紅色三角形當成三點間彼此有線,藍色三角形當成三點間彼此無線),故必定有一輸家。

廣義的Ramsey定理說: 現有一個 N 點的集合 S、把 S 中所含 r 點的子集合分成互不相 交的 kS1,…,Sk。設 l1,l2,…,lkk 個不小於 r 的數,則當N不小於 nr (l1,l2,…,lk)(後者稱為一個 Ramsey 數)時,下列的陳述對於某一個 i 而言,i=1,…,k, 必為真:

S 中有某 li 個元素的集合 $X=\{x_1,\cdots,x_{l_i}\}$,其任意 r 點的子集合都在 Si 這一組內。」

這個定理有點不容易瞭解,回到原例題,S 是一個 N 點的集合,所有二點的子集合可分成有線和無線的兩組 (r=2,k=2)l1=l2=3n2(3,3)=6,當 $n\geq6$ 時(例題中 n=6),必有三點其中任兩點間都有線或必有三點其間任兩點間都無線。

Ramsey 定理祇說 Ramsey 數一定存在,卻不告訴 Ramsey 數是多少。譬如我們知道 n2(3,4)=9, n2(4,4)=18, n2(4,5) 以上即不知道了。

著名的數論家和組合學家 Erdös 和 Turan(皆匈牙利人)在四十年前研究一個形式上很不一樣但實質上和 Ramsey 定理頗有關的數論問題:設R為任意一個正整數所成的無限集合且 R 的密度大於零,即對任意 n

\begin{displaymath}\frac{\vert R\bigcap\{1,\cdots,n\}\vert}{n}>0\end{displaymath}

則無論 k 多大,他們猜測 R 中必有一個含 k 元素的算術級數。Erdös 且提供美金一仟元給能解出此題的人(在當時一仟元是 Erdös 的最高獎金,其他題目自五元至數百元不等)。二十年後 Roth 證明此猜測在 k=3 時正確,再過了十年又一個匈牙利人 Szemeredi 證明 k=4 也成立。Szemeredi 對這問題鍥而不捨,又面壁十年,終於證明了 Erdös-Turan 的猜測,對所有 k 都正確。證明非常繁複,據 Erdös 推許為人類腦力所能達到的極限。

其次我們介紹 Hall 定理。我們要把 n 個女孩和 n 個男孩配成舞伴,我們問每一個女孩那幾個男孩她願意接受為舞伴。設 S 為男孩的集合,則每一個女孩的回答是一個 S 的子集合。現在我們要在每一個子集合堿D出一個元素(即選出一男孩作該女孩的伴),但是 n 個子集合所挑出的元素必需不重覆(一個男孩不能作兩個女孩的舞伴)。問在什麼情形下挑選可以成功。首先我們看看成功的必要條件。如果有某 k 個子集合的聯集其所包含的元素少於 k 則顯然挑選不能成功,因為找不到 k 個男孩分配給這 k 個女孩。Hall 證明了這個必要條件也是充分條件。Hall 定理有各種態式的表現方式和條件略異的變形,它被應用在作業研究的分派問題上,電話交換網路的操作上及很多其他地方。

下面我們介紹兩個圖形學上的未解題,這兩個問題和四色問題曾被圖形學大師 Hardy 合稱為圖形學上當今三大難題。

第一個問題是問一個圖形是否含有一個 Hamiliton 圈,這個圈的定義我們等一下再給。先談一個有關的,但已在二百年前被解決的問題。就是一個圖形是否有一個 Euler 圈,這也是歷史上第一個圖形的問題。



圖十

Königsberg 這個區域被河流劃分為 A,B,C,D 四區(見圖十),有七座橋溝通區際的交通。問能否從某一區出發,每一座橋經過一次且僅一次而回到原區。

把每一個區以一點表示,每一座橋以一條線表示,則得圖十一。如果從任一點出發,每條線經過一次且僅一次回到原點,稱為一個 Euler 圈。



圖十一

與一個點相接的線的數目稱為該點的度數,很顯明的,如果有任一點它的度數是奇數,則 Euler 圈不可能存在。Euler 證明了這一個必要條件也是充分條件。

如果從一點出發,每一點經過一次且僅一次而回到原點稱為一個 Hamilton 圈。 一個圖形含有Hamilton圈的充分必要條件還是未知。原則上線越多,Hamilton圈存在的機會越大。 到現在為止最好的充分條件是:

1.圖形必須為一連接圖形,即沒有孤立部分。

2.如果每個點的度數照大小次序排列為

\begin{displaymath}
d_1\leq d_2\leq\cdots\leq d_n\quad\mbox{({\fontfamily{cwM2}\...
...\mbox{{\fontfamily{cwM2}\fontseries{m}\selectfont \char 245})}
\end{displaymath}

d1 需不小於 2,且對所有不大於 n/2i,不是 $d_i\geq i$,就得 $d_{n+1-i}\geq n+1-i$

第二個問題叫做「Ulam 猜測」。一個圖形堳袧え 1 的點叫做終點。設圖形 G 中有 k 個終點,令 Gi 為從 G 中拿走第 i 個終點及接它的線所得之圖,從 G 當然很容易得到 (G1, G2,…,Gk)。 Ulam 猜測說從 (G1,G2,…,Gk)G 可以被唯一決定。當圖形 G 是一棵「樹」時,即 G 中任意兩點只有一條路線連接(這路線可以經過別的點),Ulam 猜測已被證為真,但對一般的圖形還是一個未解題。

1.Marshall Hall, Jr.《Combinatorial Theory》,1967(臺北市新月圖書公司)。
2.Frank Harary,《Graph Theory》,1971,Addison-wesley.

 
對外搜尋關鍵字:
Riemann假設
Fermat最後猜測
Euler
拉丁方陣
Ramsey定理
Ramsey數
Erdos
四色問題

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:李渭天 / 繪圖:簡立欣 最後修改日期:4/30/2002