32207 從`克隆`綿羊談起-圖形實現理論漫議

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。

★ 終極密碼為0到100之間 ★
您共有六次機會

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

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

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

1. "克隆"一個三角形

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

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

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

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

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

圖1. $\triangle ABC$ 與 $\triangle AB'C$ 有兩邊一角相等。

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

圖2

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

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

圖3

事實上, 滿足 $(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$ 便是一個反例。

圖4

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

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

又 $DE=AC=AB$

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

2. 歐拉的發現

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

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

圖5.①②③分別由同一大小的正三角形所形成的正多面體
④同一大小的正方形形成的正多面體
⑤同一大小的正五邊形所形成的正多面體。

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

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

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

圖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$ 的凸多面體均存在。

圖7
圖8

若 $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$。

圖9

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

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

圖10

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

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

圖11

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

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

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

圖12.圖 $D_2$ 的兩棵生成樹

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

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

圖 13
圖14

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

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

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

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

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

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

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

圖15

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

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

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

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

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

圖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$ 。

圖17

我們再來考察一下 $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

由圖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。

圖19
圖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$。

圖21

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

$n$ 1 2 3 4 5 67 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$ 就是平面圖。

圖22

$\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。

圖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個交叉點。

圖24.為"立交橋"

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

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

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

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

圖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

圖27

普爾, 格龍巴和史龍有一個很值得人們注意的猜想。 他們認為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上。

圖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。

圖29

圖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點行。

圖 31.
圖 32.

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

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

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

圖33

如果 $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點行的。

圖34

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

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

圖35

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

圖36

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

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

圖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

圖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

讀者對照下面的陣列, 就能找出圖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世紀數學領域取得的一大成就。

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

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

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

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

文章 推薦

電腦模擬與賭局

假設玩家A和B進行賭博。玩家A有m元,玩家B則有n元,然後擲1個公正的硬幣。如果出現正面就算玩家A贏,反面就算玩家B贏。每次賭注都是1元,如果A贏則A變m+1元、而B變n−1元,並稱此為1回合。雙方不斷地進行賭博,直到某方的錢歸零為止。在這個賭博中,有以下兩個問題:(1)玩家A和玩家B贏的機率各是多少?(2)每投1次硬幣決勝負,都稱為1回合,平均要幾回合,賭局才會結束(某方錢輸光)?....閱讀更多