一九九七年二月的一個夏夜, 地球上第一隻"克隆"羊在蘇格蘭羅斯林研究所誕生了。 這第一個真正"克隆"的哺乳動物---綿羊"多莉"引起世界的轟動。

所謂"克隆", 簡單地說是生物的一種"無性繁殖"方法。即利用成年動物的細胞複製出一個新的生命。 這在生物學上曾經認為是不可能的。

借用"克隆"這個概念, 在數學上, 我們常常可以從一個圖形"克隆"出另一個圖形。例如: 構作一個三角形和已知的三角形全等。

1. "克隆"一個三角形

"克隆"一個三角形, 需要具備某些條件。在中學教材裏, 我們就學習過這類"克隆"技術---兩個三角形全等的判定定理。

一個三角形有三個(內)角、三條邊。通常, 用英文字母 $a$ 表示內角, $s$ 表示邊。 在中學教材中, 我們已經學過: 如果一個三角形和另一個三角形, 滿足下列條件之一, 那麼這兩個三角形就全等:

1. 三邊分別對應相等 $(\hbox{簡稱 } s, s, s)$
2. 兩角一邊對應相等 $(a, a, s)$
3. 兩邊夾角對應相等 $(s, a, s)$

換一句話說, 如果我們知道一個三角形的三邊的長度, 或兩角一邊的大小, 或兩邊一夾角的大小, 那麼, 我們就可以作出一個和原來的三角形一樣大小的三角形來。

兩個三角形全等的條件不能隨意改動。誰都知道, 若一個三角形僅與另一個三角形兩邊相等, 這兩個三角形是不一定全等的。而下面的圖說明, 兩個三角形, 即使有兩邊和一角相等, 但如果這個角不是這兩邊的夾角, 則兩個三角形也不一定全等。

若把上面條件1中的 $(s, s, s)$, 改為 $(a, a, a)$, 那麼, 這兩個三角形不一定全等, 而是相似。(見圖2)

一個有趣的問題是: 如果兩個三角形的三個角分別相等, 並且還有兩邊也分別相等, $(a, a,$ $a, ~s, s,~)$, 我們能夠說, 這兩個三角形全等嗎?

如果上述的兩個三角形的三角兩邊中, 有兩角夾邊 $(a, s, a)$ 對應相等的話, 那麼這兩個三角形必然全等。 然而, 我們發現, 三角兩邊相等, 也可能不出現 $(a, s, a)$ 的情形, 那麼, 我們就不能斷言, 這兩個三角形必然全等。 請看圖3的兩個三角形, 它們的三個角分別相等 (兩三角形相似), 且有兩邊相等 (12, 18)。 顯然, 這兩個三角形並不全等。

事實上, 滿足 $(a, a, a, ~s, s, ~)$ 相等而又不全等的三角形有很多。 我們只要作出兩個三角形, 其三邊長分別為 $(n^3, n^2(n+1), n(n+1)^2)$ 和 $(n^2(n+1), n(n+1)^2, (n+1)^3)$ 這裏 $n$ 是大於1的自然數。 則作出的兩個三角形有三個角和兩條邊分別相等, 但兩個三角形不全等。 不難看出, 當 $n=2$ 時, 就會出現像圖3那樣的情形。

以上我們談的, 是數學上的圖形實現問題。也就是, 怎樣用最少的條件確定一類圖形的問題。 讀者對平行四邊形可能已了如指掌, 但是, 對下面的問題, 難免會有措手不及的感覺。

一對對邊相等及一對對角相等的四邊形必定是平行四邊形嗎?

如果你的回答是肯定的, 你必須給予證明。如果你的回答是否定的, 你必須給予一個反例。

下面我們給出一個反例: 任意作一個等邊三角形 $ABC$, 在底邊 $BC$ 上取 $D$, 使 $BD\gt DC$, 由 $D$ 點作 $\angle 2=\angle 1$ (如圖4), 取 $DE=AC$, 連 $AE$, 則四邊形 $ABDE$ 便是一個反例。

由作法可見, $\triangle ADC\cong \triangle DAE$,

故 $\angle E=\angle C=\angle B$

又 $DE=AC=AB$

即四邊形 $ABDE$ 是有一對對邊相等及一對對角相等的四邊形。 但, $AE=DC\lt BD$, 故四邊形 $ABDE$ 不是平行四邊形。

2. 歐拉的發現

上一節, 我們在平面上討論了圖形的確定問題。在空間中, 人們也早就注意到類似的問題。 早在二千多年前的古埃及, 人類已經知道有正多面體了。所謂正多面體就是各個面都是全等的正多邊形的多面體。 埃及人在建造廟宇和陵墓時, 早已認識了正四面體、正六面體和正八面體。

對正多面體的較系統的研究始於古希臘的數學家畢達哥拉斯。他發現除了埃及人知道的三種正多面體外, 還有正十二面體及正二十面體。畢達哥拉斯還證明了下面的結論: 每個面都是正三角形的正多面體, 只有正四面體, 正八面體, 及正二十面體; 每個面皆為正方形的正多面體, 只有正六面體; 每個面皆為正五邊形的正多面體, 只有正十二面體; 每個面皆為邊數大於5的正多邊形的正多面體不存在。也就是說, 只有五種正多面體存在, 如圖5。

在圖5中, 我們標出了各個正多面體的頂點數、面數和稜數 (面和面之間的公共邊, 稱為稜)。 我們把各個正多面體的頂點數和面數相加起來, 再減去其稜數, 可得到下列結果: $$ \hbox{頂點數} + \hbox{面數} - \hbox{稜數} = 2 $$

19世紀著名的數學家歐拉早就注意到這一結論, 並且發現, 這個公式對一切凸多面體都是適用的。

什麼叫凸多面體? 用一句通俗的話說, 是沒有洞且"脹"起來的多面體。 用數學的語言描述, 就是: 若把多面體的任一個面延伸成一個平面, 其他各個面都在這個平面的一側的多面體, 如圖6。

歐拉用字母 $n$ 表示凸多面體的頂點數, $f$ 表示面數, $m$ 表示稜數, 他證明任何凸多面體, 都存在這樣一種關係: $$ n + f - m = 2, $$

這一公式, 稱為歐拉公式。歐拉公式能夠幫助我們判斷某些類型的凸多面體是否存在。

例如, 如果一個凸多面體 $n=6$, $m=12$, 那麼, 問這個凸多面體的每個面是否都是正三角形?

證明: 根據歐拉公式, 由 $n=6$, $m=12$, 得 $$f=m-n+2=12-6+2=8$$

平均每個面有邊 ${2m}/{f}={2\times12}/{8}=3$ 條

因為每個面至少有3條邊, 所以這個凸多面體的每個面都是一個三角形。

下面, 我們運用歐拉公式, 討論一下什麼樣的正整數 $m$, 才存在有 $m$ 條稜的凸多面體?

顯然, 對於一個凸多面體而言, 必有頂點數 $n\ge 4$, 面數 $f\ge 4$, 由歐拉公式 $$ n + f - m = 2 \ge 6 $$ 可知, 四面體的稜數 $m=6$

我們認為, 不存在 $m=7$ 的凸多面體。 否則, 若存在7條稜的凸多面體的話, 按此凸多面體每個面來計算邊的總數。 因每條稜在兩個面中作為邊出現, 故每個面中邊的總數之和 $\!=\!2\times 7$。

而每個面至少有3邊, 故 $f$ 個面至少有 $3f$ 邊。即 $$ 2 \times 7 \ge 3f $$ $$ f \le \frac{14}{3} $$ 又因為 $f\ge 4$, 故得 $f=4$。於是, 由歐拉公式 $n=m-f+2=7-4+2=5$。

但 $f=4$ 時, 唯一的多面體是四面體, $n=4$。因此, 7條稜的凸多面體是不存在的。

下面證明, 所有 $m\gt 7$ 的凸多面體均存在。

若 $m=2k$ $(k\ge 4)$, 以 $k$ 邊為底的稜錐, 便是所求的凸多面體, 如圖7。

若 $m=2k+1$ $(k\ge 4)$, 把底為 $k-1$ 邊的稜錐底角鋸掉一個尖角如圖8, 便得到一個稜數為 $m=2(k-1)+3=2k+1$ 的凸多面體。

於是, 可得出結論:

當 $m\ge 6$, $m\not =7$ 時, 有 $m$ 稜的凸多面體存在。

3. 一筆無須準備的獎金

第一節, 我們討論了平面上的圖形, 第二節, 我們考察了空間的圖形。用數學的語言來說, 它們分別屬於二維空間和三維空間的圖形。我們可以把它們聯繫起來, 找出它們共同的特徵。

如果我們只考慮圖中頂點和邊(稜)之間的連接關係, 而不考慮頂點的位置以及邊的曲直、長短, 那麼, 不論平面或空間的圖形, 我們都可統一用一種, 只有頂點和連結頂點的線(或直或曲)所組成的圖來表示。 圖中, 那些連結頂點的線稱為圖的邊。每個頂點連接的邊數, 稱為這個頂點的度數。

以一個正四面體為例, 把它的四個頂點分別標上1, 2, 3, 4, 如圖9。 如果我們僅考慮各點的連接關係, 那麼, $D_1$ 就可以表示成圖 $D_2$ 或 $D_3$。

$D_1$, $D_2$, $D_3$, 在數學上稱為同構圖。確切地說, 所謂兩個圖同構, 就是在兩個圖的頂點之間建立起一一對應的關係, 一個圖中的兩個點相連當且僅當它在另一個圖的對應點也相連。 由於我們不管頂點的位置及邊的形狀, 因此, 一個圖的同構可以有多種多樣, 而兩個圖同構, 就意味著它們的結構相同, 在研究它們的點、邊的連接關係時, 我們可以認為它們是毫無區別的。

圖5中的五種正多面體, 除了正四面體如上所述外, 其餘的四種正多面體有如下的同構圖如圖10。

現在, 我們討論一下圖的概念。 如果一個圖的任何兩點, 都有一條由邊組成的路, 從一點到達另一點, 則這個圖稱為連通圖。 一條由不同邊組成的路首尾相接, 稱為圖的圈。圖10所示的圖都是連通圖, 並且有很多圈。

沒有圈的連通圖, 稱為樹。它是我們生活中樹的類比, 如圖11。

那些只有1度的點稱為"樹"的葉點或懸掛點。 含有葉點的邊叫懸掛邊。"樹"是電腦科學中經常要用到的一類圖。 它有一個很重要的性質: "樹"的邊數恰好等於頂點數減1。

用下面的方法, 我們不難看出"樹"的這一性質: 如每次把"樹"的一條懸掛邊去掉, 則"樹"的頂點數和邊數各減去1。 如此延續, 到最後只剩下一條邊, 這時邊數是1而頂點數是2。邊數恰好是頂點數減1。

有趣的是, 任何一個圖, 沿著它的邊, 我們都可以找出一棵"樹", 使它恰好包含這個圖的所有頂點, 如圖12。

這棵"樹"叫這個圖的生成"樹"。 生成"樹"好比一個圖的骨架, 它用最少的邊撐起所有的頂點, 如果我們把一個圖的每個圈(如果有的話)的適當的邊去掉, 便得到它的生成"樹"。

如果一個圖, 它的同構圖可以畫在平面上, 使任意兩條邊都不相交(除端點外沒有公共點), 那麼, 這個圖便是平面圖。例如圖9, 圖10, 圖11, 所示的圖都是平面圖。

圖13所示的圖是不是平面圖?

我們可以把它"攤"在平面上, 使它沒有兩條邊相交而成圖14。 那麼這圖叫做"能在平面上實現"。

判斷一個圖能否在平面上實現, 並不是一件很簡單的事情。讓我們從一個數學故事談起。

據說, 在十八世紀的歐洲, 有人曾懸賞一筆獎金徵解下面的一道智力題: 有3個城鎮, 分別稱 $A$, $B$, $C$; 有3個水塘, 稱為 $D$, $E$, $F$。 每個城鎮的居民須修築道路分別直接到三個水塘取水。 $A$, $B$, $C$ 三鎮居民互相不和, 都不希望在路途見面。 因此, 各自希望所修道路都互不相交。請問, 這些道路能夠修築成功嗎?

每個城鎮向3個水塘各修一條路, 共3條路, 於是3個城鎮合共要修9條路。 若能把這9條路(長短曲直不拘)互不相交地畫出來, 那麼, 就說明這樣的道路可修築成功。 否則, 不能修成。

讀者們, 請動手畫畫, 看這筆"獎金"能否拿到手。

在紙上塗畫一番後, 你會覺得, 要使這9條路不相交好象總是差那麼一點點。如圖15,

8條路已經畫出來了, 但第9條路 ------ 由 $C$ 到 $E$ 的這條路, 就是無法不與其他路相交。的確如此。

正是那充滿希望的"一點點", 吸引了不少人頑強地試下去, 不肯善罷甘休。

其實, 這是毫無希望的"一點點"!

數學, 幫助我們作出正確的判斷。

在數學家眼中, 這個"水塘道路問題"其實是如圖16所示的一個圖, 是否能在平面實現的問題。

為了方便敘述, 我們稱這個圖為 $K_{3, 3}$ 。

我們談過凸多面體的歐拉公式, 任何一個凸多面體都同構於一個平面圖。 凸多面體的頂點、稜、面, 分別對應於一個平面圖的頂點、邊和面。 所謂平面圖的面, 是指平面被圖的邊分成的區域, 例如, 圖9的 $D_2$, 具有4個面, 它們分別是 $\triangle 123$, $\triangle 124$, $\triangle 134$, $\triangle 234$ (這是指此三角形以外的平面部分)。

於是凸多面體的歐拉公式相當於連通平面圖的歐拉公式。下面, 我們來證明一下。

定理(歐拉公式): 如果連通平面圖 $G$ 有 $n$ 個頂點, $m$ 條邊, $f$ 個面, 那麼 $$ n + f - m = 2 $$

證明: 如果 $G$ 是"樹", 那麼 $f=1$, 由"樹"的性質 $m=n-1$, 所以 $n+f-m=n+1-(n-1)=2$。 歐拉公式成立。

如果 $G$ 不是"樹"。我們取 $G$ 的生成"樹" $T$。 在取 $T$ 的過程中, 每次減少一個圈中的一邊, 即既少一條邊, 也少一個面, $n+f-m$ 始終不變。 已證對於"樹" $T$, 歐拉公式成立, 所以對於圖 $G$, $n+f-m=2$。

我們可以採用反證法證明: $K_{3, 3}$ 不是平面圖。

假若 $K_{3, 3}$ 是平面圖, 則 $n=6$, $m=9$, 根據歐拉公式得 $$ f = 2 + m - n = 2 + 9 - 6 = 5 $$

而且, $K_{3, 3}$ 每個面至少有4條邊, 每邊至多在兩個面中出現。因此, $$ 4f \le 2m $$ 即 $4\times 5=20\le 2\times 9=18$。 因此, $K_{3, 3}$ 不能在平面上實現。則"水塘道路問題"是不可能解決的問題。征解懸賞? 原來是一筆無須準備的獎金。

4. 這不僅僅是一個遊戲

"什麼築路取水, 這分明是人造的遊戲"有些讀者可能不屑一顧, "道路相交又何妨呢? 值得花這麼大的力氣去探究嗎?"

說得對極了, 這的確是一個人造的遊戲。造出來是為了把一個有用的數學問題說得更有趣而已。 如果在你的面前, 要用鍍銅在電路板上把一個點(城鎮)和另3個點(水塘)接通。 那麼, 板上鍍出來的9條銅線是不能在平面上相交的, 否則就破壞了電路板原設計的效果。

對此, 你能說, 這僅僅是一個遊戲嗎?

我們把平面上的 $n$ 個點(無三點共線), 兩兩連結起來, 所成的圖稱為 $n$ 階完全圖, 記作 $K_n$ 。 圖17所示就是5階完全圖 $K_5$ 。

我們再來考察一下 $K_5$ 是不是一個平面圖。

手中有了數學理論, 就無須依靠拼拼湊湊的方法。

我們證明: $K_5$ 不是平面圖。

由圖可見, $K_5$ 有5個頂點, 10條邊, 即 $n=5$, $m=10$。 假設 $K_5$ 是平面圖, 根據歐拉公式, $$ \hbox{面數} f = 2 - n + m= 2 - 5 + 10 = 7 $$

因為 $K_{5}$ 每個面至少有3條邊。每條邊恰在兩個面中出現, 於是 $$ 3f \le 2m, $$ 即 $3\times 7\le 2\times 10$, $21\le 20$。 因此, $K_5$ 不是平面圖。

自然, 人們便產生了這樣的問題: 怎樣判斷一個圖能否在平面上實現? 什麼樣的圖是平面圖?

通過用筆在紙上作圖來證明固然不是好辦法, 而用歐拉公式也僅僅能證明, 某些圖不是平面圖。 因此, 對平面圖, 僅靠歐拉公式是難以判定的。

問題引起了數學家的注意, 然而, 解決它也並非輕而易舉。

問題一直延續到二十世紀。1930年, 波蘭的一個叫庫拉托斯基的數學家解決了這個問題。 庫拉托斯基得出了一個令人驚異的結果, 他只用兩個圖便說清楚了一個重要的結論:

一個圖是平面圖, 而且當把這個圖的所有度數為2的點收縮後, 它不含有圖 $K_5$ 或 $K_{3, 3}$ 。

所謂把點 $v$ 收縮, 即把 $v$ 和它的鄰點 $u$ 合併為一個點 $w$, 並且使所有與 $u$, $v$ 相鄰接的點都與 $w$ 相鄰。

由圖18可見, 圖 $G_1$ 與 $G_2$ 同構, 而 $G_2$ 把所有的2度點(點2, 4, 8, 9)收縮後, 得到圖 $K_5$。 因此, 由庫拉托斯基的結論可知, 圖 $G_1$ 不是平面圖。 而在 $G_2$ 中, 所有的2度點, 都好像把一個 $K_5$ 圖的邊分開來。 [ 因此像 $G_2$ 那樣, 把 $K_5$ 的邊增加一些剖分點(2度點), 所成的圖也叫 $K_5$ 剖分圖 ]。 類推, 把 $K_{3, 3}$ 的邊增加一些剖分點所成的圖也叫 $K_{3, 3}$ 剖分圖。 把 $K_5$ 和 $K_{3, 3}$ 剖分圖中的剖分點(2度點)收縮後, 便成 $K_5$ 和 $K_{3, 3}$ 。

於是, 庫拉托斯基定理也可表述為:

一個圖如果是平面圖, 它就不包含任何 $K_5$ 或 $K_{3, 3}$ 剖分圖。

回顧一下圖13, 它雖然邊如蛛網密布, 但它不含 $K_5$ 和 $K_{3, 3}$ 剖分圖。 因此, 它仍然是一個平面圖, 圖14正驗證了這一點。

上面所述的平面圖, 我們都把它畫在平面上使所有的邊互不相交(除端點外)。 雖然, 我們沒有把每邊都畫成直線段。但是, 要真正使它們每邊"拉直", 是完全可能的。 這一結論, 早在68年前(1948), 已由數學家法雷嚴格證明了。

誠然, 庫拉托斯基定理在理論上已完全解決了平面圖的判定問題。 但在應用上, 要判斷有沒有 $K_5$ 和 $K_{3, 3}$ 的剖分圖卻不是輕而易舉的。 因此, 尋找如何把一個圖"攤"在平面上的有效方法, 仍是數學家熱心研究的課題。

5. 立交橋的啟發

我們要將一個非平面圖, 使它們的邊不相交地畫在平面上是不可能的。 例如, 圖15中, 從城鎮 $C$ 到水塘 $E$ 的道路, 必然會跟其他路線相交。 但是, 如果從 $C$ 到 $E$ 的路上架一座立交橋的話, 那麼, 就可以使從 $C$ 到 $E$ 的道路與其他路線"不相交"成為可能。 而建一座立交橋, 就意味著我們討論的道路相交問題從二維擴充到三維。

可以證明一個令人興奮的結果: 所有圖都能在三維空間中實現。

例如圖 $K_{5}$ 雖然不能在平面上實現, 但我們卻可以把它不相交地鋪在一個充氣的自行車輪胎 --- 環面上, 如圖19。

如果我們把一條矩形的紙帶兩端, 扭一下再粘接起來的話, 所成的帶稱為莫比烏斯帶。 圖 $K_{3, 3}$ 也恰好能不相交地鋪在莫比烏斯帶上, 如圖20。

一個平面圖固然有很多有用的性質, 然而, 即使是一個不可平面圖, 在數學家眼中, 仍然有很多需要探索的問題。

我們知道, 一個非平面圖要畫在平面上就不可避免地出現有邊相交的情況, 而這種邊之間的交點(非端點)的最小個數, 稱為一個圖的交叉數, 用字母 $c$ 表示。 從第3節的分析中, 我們知道, $K_{3, 3}$ 的交叉數是1, $K_{5}$ 的交叉數也是1。 如果一個圖的交叉數是0, 則這個圖就是平面圖。

為了便於說明問題, 我們來看看完全圖。$K_{5}$ 是非平面圖, 根據庫拉托斯基定理可知, $K_{6}$ 更是非平面圖, 而且它們交叉數比 $K_{5}$ 多。 圖21就畫出了一個 $K_{6}$, 其中6個頂點用"$\circ$"表示, 而3個"$\bullet$"點, 就是它的交叉點, 於是 $C(K_{6})=3$。

我們知道, 完全圖是屬於簡單、對稱, 有一定規律的圖。 即使如此, 對於這類圖的交叉數, 現還沒有弄得清楚, 更不用說其他的圖類了。 目前, 對完全圖的交叉數, 我們只知道在 $n\le 10$ 情況下, 有下列結果:

$n$	1	2	3	4	5	6	7	8	9	10
$C(K_{n})$	0	0	0	0	1	3	9	18	36	60

數學家們猜想: 它們之間可能存在這樣一種關係: $$ C(K_{n}) = \left \{ \begin{array}{lcl} \displaystyle\frac{n(n-2)^{2}(n-4)}{64} & \quad & \qquad \hbox{當 $n$ 是偶數} \\[8pt] \displaystyle\frac{(n-1)^{2}(n-3)^{2}}{64} & \quad & \qquad \hbox{當 $n$ 是奇數} \end{array} \right. $$ 但是, 至今, 這仍是一個未得到證明的結論。

也許有人會建議, 能否通過電腦來幫助我們求出一個圖的交叉數, 然而數學家的回答也許令人失望 ------ 1983年, 數學家加利和貝拉證明, 計算一個圖的交叉是一個用電腦也不能解決的問題。 因為當圖的階數增加時, 計算交叉數的工作量將很快增加, 以至超過電腦的工作極限。 看來, 要解決這一問題, 目前非得通過理論的嚴格證明不可。

如果一個電路板上的線路圖是一個非平面圖的話, 我們已經知道, 線路的交叉將會影響電路板的功能, 由此, 我們想到, 能否通過增加電路板, 把原來鋪在一塊板上的圖改鋪在多塊板上, 從而使電路板的線路不交叉。這實際上是能夠做到的。 於是, 就有一個所需電路板的最小數問題, 而這個最小數稱為原來電路圖的厚度, 換言之, 一個圖 $G$ 的厚度就是把 $G$ 分成平面圖的最小數目, 以 $\theta(G)$ 表示。如果 $\theta(G)=1$, 則 $G$ 就是平面圖。

$\theta(K_{5})=2$, 圖22便是用兩塊板鋪出 $K_{5}$ 的形象說明。

已經證明 $\theta(K_{n})\ge [\frac{n+7}{6}]$, $n\gt 3$, $n\not=9$。 這裏 $[x]$ 表示不大於 $x$ 的最大整數。例如 $[3/2]=1$, $[9.99]=9$。 請注意, 這裏僅僅給出了關於 $\theta(K_{n})$ 的一個不等式, 即 $\theta(K_{n})$ 至少是 $[\frac{n+7}{6}]$。 至於等號是否成立, 還要具體探索。

例如, 在 $\theta(K_{6})\ge [\frac {6+7}{6} ]=2$ 式裏, 要具體研究 $K_{6}$, 可以把它畫成兩個平面圖, 如圖23。

因此, 可以得出結論 $\theta(K_{6})=2$。

要使一個非平面圖的邊避免交叉, 除了用增加平面的方法外, 還可以用加蓋"立體交叉橋"的方法。 而這種"立交橋"的最小數目, 稱為一個圖的虧格。圖 $G$ 的虧格記為 $\gamma(G)$。對於平面圖 $G$ 來說, $\gamma(G)=0$。 回想起第二節, 一個有 $n$ 個頂點, $m$ 條稜, $f$ 個面的凸多面體 $(\gamma=0)$ 可表達成歐拉公式 $n+f-m=2$ 。 而對於一個格為 $\gamma$ 的多面體, 歐拉公式的表達為 $n+f-m=2-2{\gamma}$ 。 數學家曾對 $\gamma(G)$ 有一個大致的估計, 即當一個圖 $G$ 有 $n$ 個頂點和 $m$ 條邊時, 則 $$ \gamma(G) \ge \frac{m-3n}{6} + 1 $$ 而直到1968年, 倫喬和揚斯才證明 $$ \gamma(K_{n}) = \Big \{\frac{1}{12}(n-3)(n-4) \Big \} $$ 這裏 $\{x\}$ 表示不小於 $x$ 的最小整數, 例如 $\{5.1\}=6$, $\Big \{\displaystyle\frac{7}{3}\Big \}=3$ 。

前面講過圖的交叉問題, 但不要以為一個非平面有多少個交叉點, 就可通過搭多少座立交橋來解決。 因為按此想法, 很容易誤認為 $c(G)=\gamma(G)$ 而事實是, $\gamma(G)\le c(G)$。 我們來看看 $\gamma(K_{6})$。按上述公式 $\gamma(K_{6})=1$, 但 $c(K_{6})=3$, 從圖24可知, 只要在 $K_{6}$ 中搭起一座"立交橋", 就可以讓3條路(邊)在橋上通過而避免3個交叉點。

6. 果園中的思索

從二維圖形到三維圖形, 即從平面到空間, 竟然引出如此多的數學問題。然而, 即使僅僅考慮平面圖形, 對於它的構造, 人們往往仍要費盡心機。在拙作"你會畫圖嗎? " (《數學傳播》第二十三卷第一期)就敘述過十九世紀化學家艱辛探索苯結構式的故事。

我們已經知道, 構作化學結構式相當於數學上的從已知頂點數和每個頂點的度數, 設計出一個合要求的圖的過程。 而在作圖中, 如果我們不再限制每個頂點所經過的邊數(即度), 而倒過來, 限制每條直線所具有的點數的話, 這就成了數學上有名的"果園"的問題。

"果園"問題也稱為"種樹"問題, 可表述為一個農民要在果園裏種n棵樹, 要求種的時候每行恰有 $k$ 棵樹。

這是一個平凡的問題。平凡到誰也可以隨手在紙上畫出來。 然而, 如果問: 它最多能夠排出多少行來? 這就是一個極不容易回答的問題。 直到現在, 人們還局限於在 $k=3$ 或 $k=4$ 的範圍內去探索它。

這類問題的困難在於, 還沒有人能找出一整套可行的方法去解決它。因為每一類題都需要不同的機智和技巧。 人們只能"打一槍換一個地方"。

我們認識一下這個問題, 當 $k=2$ 時, 這是一個不足道的問題, 因為在任兩個點都可成一直線, 只要使 $n$ 個點無三點共線, 排出來的線就最多, 用r來表示最大的線數。即當 $k=2$ 時, $r=\displaystyle\frac{1}{2} n(n-1)$。(想想看, 為什麼?)

當 $k=3$ 時, 問題不僅僅是困難和有趣, 而且它跟很多現代數學分支有聯繫。在這裏, 我們看看數學家(包括業餘數學家)研究它的結果。

每行3點的最大行(簡稱為三點行或三點線)數解, 從 $n=3$ 到11, 我們把它的解列在圖25上。 圖中的 $r$ 表示對應 $n$ 的最大行數。當然, 具有這樣 $(n,r)$ 的圖可能不止一個。 在這裏我們只是把其中的一個解繪出來而已。

從圖25中, 我們可知, 在9以前, 最大行數 $r$ 都小於 $n$ 。 在 $n=9$ 時, 我們可以輕易地畫出具有8行的圖來, 即是把9棵樹成三行排成一個正方形陣列。 (每邊3點, 中心1點)。然而, 要增加兩行, 這需要動腦筋思考。 下一節, 我們將用數學來幫助我們設計。

11點16行的圖是在1897年由數學家作出來。整整過了近50年後, 12個點最多19行的結論才被證明出來。 如果說, 從3到11個點的圖, 還能在一張紙上直觀地畫出來的話。 那麼, 12個點的圖, 就要由讀者發揮一下自己超越紙面邊緣的想象了, 能想象出來嗎?

12點19行圖是由普爾, 格龍巴和史龍三位數學家於1946年合作研究證明出來的, 如圖26。

從圖26中可以看出, 3組平行線(每組4條), 在 $\infty$ 方向看成是在無窮遠處相交於一點。 因此, 從每個 $\infty$ 出發都可以數出4條三點線(共 $4\times 3=12$ 行)。 又在可見的六邊形中, 可數出6條三點線, 再加上一條無窮遠直線上面有3個點 $\infty$, $\infty$, $\infty$。這樣合計共有 $12+6+1=19$ 條三點線。 這裏, 除了可見的形象外, 還有要讀者有一些無限數學的觀點。

而當 $n=13$ 時, 我們還不知道 $r$ 的最大值, 但人們能夠作出一個圖具有22條三點行的圖, 如圖示27。 在觀察此圖時, 也應把 $\infty$ 看作是6條"平行"直線的交點。 至於 $n$ 大於13的三點線最大問題, 只有當 $n=16$ 時, 前面提到的三位數學家已證明了 $r$ 的最大值為37。 其餘情形, 只知道一些答案結果。 我們把 $n$ 從14到20目前所知道的最好結果列表、作圖(如圖27)如下:

n	14	15	16	17	18	19	20
r	26	31	37	40	46	52	57

普爾, 格龍巴和史龍有一個很值得人們注意的猜想。 他們認為7, 11, 16和19外, n的三點線的最大數是 $$ 1 + \Big [\frac{n(n-3)}{6}\Big ] $$

式中符號 $[x]$ 表示不大於 $x$ 的最大整數(參見第5節)。 如果上述猜想是正確的話, 那麼, 當 $n=13$ 時, $1+\Big [\displaystyle\frac{13(13-3)}{6}\Big]=22$ 行便是最小的了。

至於, 每行4點的情形, 問題將變得更加複雜和困難。 有趣的是, 它和三點行的問題一樣, 從 $n=4$ 到12, $r$ 的最大值問題已有結論。 同樣, 從 $n=13$ 開始, $r$ 的最大值仍是一個未解決的問題。 我們把 $n=4$ 到12的4點行 $r$ 最大值的解列在圖28上。

對於 $n$ 從13到20,我們只能列出目前4點行 $r$ 的數值, 而還未能證明它們是否最大, 如下表。

n	13	14	15	16	17	18	19	20
r	9	10	12	15	15	18	19	21

值得一提的是, 當 $n=16$ 時的情形, 數學家作出的15條四點行像一幅非常優雅的花形圖案, 如圖29。 受自然界中花的形象啟發, 我們不難作出20個點、22條四點線的圖來, 如圖30。

7. 數學家也來種樹

讀完第8節後, 如果你把那些眼花繚亂的圖僅僅當作智力遊戲來讀, 那麼現在我們來看一看, 數學是如何參與這些形象設計的。數學家不懂園藝, 也許, 他們不內行如何鬆土, 施肥。 然而, 按特定的要求安排種植, 他們也能幫得上忙的。

讓我們先從上一節的"果園"問題的3點行談起。以 $n=9$, $r=10$ 的圖為例(圖25)有人對它的評價頗高, 據說它的構圖者的靈感來自於射影幾何的巴普斯定理的啟發而來。

從數學的直覺可知, 9棵樹擠成10個3點行, 每個點通過的行數不會太小。 如果我們把3點行中除中點外的兩個點稱為端點的話。 那麼10個3點行應該有20個端點, 相交的端點算作2個, 現在已知有9個點(9棵樹), 它們要扮演20個端點的角色。顯然, 就至少要有一棵樹(點)是3個3點行的端點。 把這個端點記為1, 落在以1為端點的3行上的其餘各點為2, 3, 4, 5, 6, 7, 如圖31。

用類似於上述的推理, 我們還可證明, 所求的圖中至少有3棵樹是4行的交點。 讀者可作為一個練習去完成它。

圖31上有7個點, 現在我們要考慮的是還有兩個點(8, 9)應往哪里擺, 方可造出10個3點行來。 先假設2, 3, 4, 5, 6, 7這六個點形成一個凸多邊形 $G$, 若 $G$ 是六邊形, 如圖32。 即2, 3, 5, 7, 6, 4成一凸六邊形。

只要再造出7個3點行就夠了。把$\{3, 5\}$, $\{2, 7\}$, $\{4, 6\}$安排在適當的位置, 它們能交於一點8, 於是就增加了3個點行。又把24, 36, 57延長交於點9, 又可得另外3個3點行。 這時8, 1, 9成三點行, 連同原來由1為端點的3個3點行, 便共有10個3點行。

讀者也許會問, 為什麼能保證在構圖中會有3線共點和3點共線?

事實上, 這運用了數學中射影幾何的基本理論。

如果 $G$ 是凸五邊形, 如圖33。 那麼, 按照上面的作法, 249和648這兩個點行消失了, 增加了一個246的3點行, 總行數只能是9。 在這種情況下, 無論點8和9怎麼擺, 也得不到10個3點行。

如果 $G$ 是凸四邊形, 即把圖33的中3, 5, 7也拉直成一條3點行, 這時的解便成圖25中所示的圖。

如果 $G$ 是凹多邊, 那麼從圖33的分析也可知, 它所能拼湊出的3點行是遠遠不夠10條的。

我們還可以用數學嚴格證明: 當 $G$ 是凸六邊形和凸四邊形時, 所得的解在同構的意義上是唯一的。 因此, 9棵樹成10個3點行的解只有2個。

我們再來看4點行。有一個著名的例子就是五角星形, 如圖28。可看作它是由10棵樹形成的5個4點行。 那麼, 除了五角星形外, 這類的圖究竟有多少個?

先來觀察五角星形。這個圖的特點是每一棵樹(點)恰只屬於2行, 這是一個很重要的特點。

我們需要證明: 這類圖是不是都有這一特點?

顯而易見,回答這個問題只須證明能否有一棵樹落在3行上?

然而, 回答是否定的。因為, 若真有一點落在3個4點行上, 這時每一行均有4個點, 3行已經佈滿了10個點, 如圖34。除了圖中所示的3條4點行外, 任取4個點, 就至少有2點落在已知的4點行上, 因2點可決定唯一直線。 因此, 在這種情況下是作不出第4條4點行的。

這樣, 我們就證明了: 任一棵樹至多只能屬於2個4點行。如果我們把5條直線無3線共點地兩兩相交, 就一共能交出10個點, 這也是交點的最大數目。若把樹種在這些交點上, 就可得到符合要求的圖。

為了不重覆、不遺漏地畫出10個點、5個4點行的圖, 可以採取分步驟進行的方法。 先畫出3條不共點的直線, 如圖35(1)。 為容易辨認, 我們把圖中間的三角形加黑, 而成"黑三角"。 下面, 只要再增加2條直線, 使5條直線3線共點就行了。當然, 重要的是辨認出同構的圖形。 先加第一條直線, 用粗實線來表示, 如圖35(2), 圖示為每線都含3棵樹的2種情形。

現在, 我們再把增加的第2條直線(用虛線表示)加上去 [務必做到: (1)每線有4個點; (2)無3線共點], 由圖35的(2.1)可得到下列3個圖, 如圖36:

從圖中可以看出, 虛線的移動是有規律的。它的規律性可以從交點的情況看出來。

再由圖35的(2.2), 添加上述要求的另一條直線(用虛線表示), 又可得出未曾出現過的另兩個圖, 如圖37,也請注意虛線的規律。

我們還可以作出很多圖, 但他們都屬於這5種圖之中的任一個的同構圖。 因此, 10棵樹成5個4點行的構圖只有5種。

拼湊不是數學, 只能是遊戲。 當然, 在數學中也常採用拼湊的方法(如中學代數中因式分解的十字相乘法), 但是, 這種拼湊是通過數學分析, 按照特定的程式進行的。 正因為有了這種程式, 電腦才進入了數學, 通過人腦和電腦結合, 數學家可以解決更多過去無能為力的問題。

8. 有限個點的幾何

我們跟隨著數學家種完樹以後, 經過一番辛勞, 終於可以稍作歇息。

可是, 數學家的思維不會中止於某個特定的實例上, 他們希望把特殊的性質總結為一般的規律。

從上面的討論中, 我們知道一直線可安排3點, 4點, 5點, 那麼, 如果在平面上有 $n$ 個點, 每 $m$ 個點 $(m \!\le\! n)$ 在一直線上, 最多能構成幾條這樣的直線呢?

這不是一個簡單的問題, 從這樣的一個問題思索開始, 已經發展為近代數學的一個分支------有限幾何學。

有限幾何就是研究有限個點、線、面之間的關係。 在我們熟知的平面幾何裏, 每一條直線都包含著無限個點, 每個平面上都有無限條直線。 而在有限幾何裏, 只假設平面上有有限個點, 每條直線只包含有限個相同數量的點。 當然, 在平面上也僅僅有有限條直線。 例如, 在有限幾何中研究一種稱為 $n$ 階的有限射影平面, 它僅包含 $n^{2}+n+1$ 個點, 只要假定存在這樣一條直線, 它恰好包含 $(n+1)$ 個點 $(n\ge 2)$, 就可以用數學嚴格的證明: 在這平面上的每一條直線都正好包含 $(n+1)$ 個點, 以及每一個點恰好是 $(n+1)$ 條直線的交點, 從而證明這平面上包含 $(n^{2}+n+1)$ 條直線。

乍聽起來, 這似乎是一個數學家的怪異想法。 為了讓你理解數學家的"怪異", 我們先來敘述一個著名的古典問題, 稱之為"散步"問題: 一個房間裏有7名學生。要求每天傍晚, 有3名學生結伴外出散步, 每一對學生只能同時出現在一天傍晚, 如甲, 乙, 丙同在星期一散步後, 甲和乙, 甲和丙, 乙和丙再不能在一起散步。問一周7天, 該怎麼安排這些學生散步呢?

我們將這7名學生表示為 ① 、 ② 、 ③ 、 ④ 、 ⑤ 、 ⑥ 、 ⑦ 。 散步問題的數學意義就在於, 把這7個數位分為7組, 每3個數字一組, 而每兩組之間不能有多於兩個相同的數字(因每一對學生只能同時出現在一天傍晚)。 通過思考我們就會發現, 在每兩組之間必定有一個數字相同, 否則無法按要求安排7天的散步。

問題來自生活, 解決它卻需要理論。問題是: 如何安排這些小組的組成?

我們可把上面給出的條件進一步數學化: 把 ① ② ③ ④ ⑤ ⑥ ⑦ 看成平面上的7個點, 那麼只需要構作一個圖, 使圖中的每條線(不一定是直線)上有3個點, 每兩條不同的線只有唯一的交點, 共有7條這樣的線。 想想看, 按照這個圖, 不是可以把散步的小組成功地分出來嗎?

下面, 我們就把"散步"問題的圖畫出來, 如圖38。 在圖38中, 三角形有3邊、 3中線, 加上連結 ④ ② ⑥ 的一條線, 便共有7條線。 據此, 便可確定7名學生散步的組合方案。 \begin{eqnarray*} && \hbox{星期一: } ① ② ③ \\ && \hbox{星期二: } ③ ④ ⑤ \\ && \hbox{星期三: } ⑤ ⑥ ① \\ && \hbox{星期四: } ① ⑦ ④ \\ && \hbox{星期五: } ② ⑦ ⑤ \\ && \hbox{星期六: } ③ ⑦ ⑥ \\ && \hbox{星期日: } ④ ② ⑥ \end{eqnarray*}

圖38中的7個點的號碼可隨意調換, 每日的安排亦可上下移位, 這樣便可以寫出這7位同學的很多不同的"散步"方案來。

圖38的構形為"范諾"構形。它是在1892年被數學家范諾所繪製出來的。 別以為, 范諾的這一套東西僅僅用於安排散步, 在理論上, 它就是上述的 $n$ 階有限射影平面。 而圖38, 便是當 $n=2$ 時的情形。不是嗎? 平面上有 $n^{2}+n+1=2^{2}+2+1=7$ 個點, 每條線恰有 $n+1=2+1=3$ 個點, 每個點恰是 $n+1=2+1=3$ 條線的交點, 平面上有 $n^{2}+n+1=7$ 條線。 在應用上, 如果把7個人換作是7種產品添加劑, 要求每次同時放3種來改進產品的質量, 安排7次試驗, 怎樣設計出最佳試驗方案, 探索用哪三種添加劑配合使用最好?

那麼, 上述的"范諾"構形便是一種較好的試驗設計。

如果把添加劑擴大到13個, 每次試驗取4種, 安排13次試驗, 設計最佳方案。 這個問題可用一個3階有限射影平面來解決, 即把13個標號點分成13組, 每組4個點, 每一對點只能同時出現在一組中, 則它的"范諾"構形可表示為圖39:

讀者對照下面的陣列, 就能找出圖39的13條"直線"。事實上, (下面的各組數是按圖的"直線"列出來的)

1. ① ② ③ ⑩ ;	2. ④ ⑤ ⑥ ⑩ ;	3. ⑦ ⑧ ⑨ ⑩ ;
4. ⑦ ④ ① ⑫ ;	5. ⑧ ⑤ ② ⑫ ;	6. ⑨ ⑥ ③ ⑫ ;
7. ⑬ ① ⑤ ⑨ ;	8. ⑬ ② ⑥ ⑦ ;	9. ⑬ ③ ⑧ ④ ;
10. ⑪ ③ ⑤ ⑦ ;	11. ⑪ ② ④ ⑨ ;	12. ⑪ ① ⑧ ⑥ ;
13. ⑩ ⑪ ⑫ ⑬ ;

有趣的是, 近100年來, 數學家們一直在尋找一個有111個點、111條線, 每線有11個點的構形 ------10階有限射影平面圖。為什麼呢?

因為這個圖在數學理論上有著重要意義。 一直以來, 人們無法在理論上證明或否定這一構形的存在。 "肯定"和"否定"的兩派各持己見, 亦各有學術依據。 直到1988年12月20日, 美國《紐約時報》發表了一條引人注目的消息: 加拿大康哥迪亞的華裔數學家林永康教授領導的一個小組, 用電腦花了近2000小時, 終於證明了10階有限射影平面圖是不存在的。 於是, 數學上的一樁"懸案"又告解決, 這被認為是20世紀數學領域取得的一大成就。

從"克隆"綿羊談起, 我們漫談了圖形理論。 畫圖, 是每個人都能躍躍欲試的工作; 要把各種有限制條件的圖精確的表達出來, 這便是數學家的追求。

數學, 不僅讓我們在紙上直觀地讀圖, 畫圖, 還教會我們跳出紙面, 甚至在無限遠的地方把一個圖想象出來。

不要說: "築路", "造橋", "種樹", "散步"儘是數學家造出來的鬼把戲, "都云作者癡, 誰解其中味"(曹雪芹)。 讓我們在每個"怪誕"的想法中, 回味個中的理論含量和應用前景。

---本文作者任教於中國廣州市華南師範大學數學科學學院---