1、有影響的數學家Marianne Freiberger關鍵詞： 數學家引言作為一門學科，數學有簡樸之美的聲譽它對某些人產生共鳴，就像美麗的日出日落、動聽的交響樂或漂亮的圖畫可能對其他人產生共鳴一樣。然而，數學也有其應用的一面。如果沒有20世紀發展的數學，我們不會有正在從根本上改變我們21世紀初生活方式的手機。與數學的美感及適用性雙重背景相比較的是這樣的感覺：數學前沿與非數學使用者能掌握的東西越走越遠。數學證明已經變得越來越長、越來越復雜，并且在某些情況下，重要定理已經整體上需要計算機的幫助。這方面的例子有Wolfgang Haken和Kenneth Appel計算機證明了四色定理這一猜

2、想以及Thomas Hale計算機證實球體可以擠進三維空間并能達到最大密度。由于許多數學家的工作以及他們對數學的熱愛，以及清晰的洞察，使我們可以更清楚地看到數學的美感與適用性這兩方面。在這方面做出杰出貢獻的數學家很多，在這里，我想介紹前幾年去世的美國幾何學家Victor Klee的工作。Victor Klee是美國最杰出的幾何學家之一。他的去世（2007年8月）是數學界的重大損失。他出版的作品包括幾本書和超過240篇的研究論文。Klee于1925年出生在舊金山，在Pomona學院修了數學和化學兩個專業。雖然20世紀之前，幾乎所有的數學家（如牛頓、高斯、歐拉、拉普拉斯等）不僅在數學，而且在物理或

3、一些其他科學分支均有貢獻，但由于專業化的壓力，現在這很難得了。雖然Klee的工作大部分集中在幾何上，出于理論與應用的考慮，他的工作橫跨的興趣廣泛。他在弗吉尼亞大學跟隨著名的拓撲學家Edward McShane學習，獲得博士學位。他1949年的博士論文題目是“線性空間中的凸集”。Klee的早期訓練和研究是在拓撲學領域這個學科關注幾何對象屬性的研究，它超越了角度、距離和與歐幾里得幾何有關的領域的傳統。因此，從拓撲的觀點看，直線段和曲線段是一樣的，正方形和（歐幾里得）橢圓也是一樣的，但線段和圓不是一樣的。這種拓撲意義下的區別意味著一個圓圈把平面分為內部區域和外部區域，而線段則不能。因此，如果在平面上

4、取不共線的兩個點，則可以找到連接這兩點的一條曲線，它與該線段沒有共同的點。然而，對于圓內一點和圓外一點，連接它們的任何曲線和圓必有一個共同點。這是拓撲學家感興趣的一種幾何信息，而不需要關于距離的信息。圖1：幾何集可以看起來不同但是拓撲等價。Klee職業生涯的大部分時間都是在華盛頓大學（西雅圖）度過的；他1953年去那里教書，2000年從那里退休。在華盛頓大學的歲月里，他指導了34個博士生，其中大部分將自己說成是幾何學家。他的學生們進而也已經訓練出許多其他的幾何學家。根據“數學家譜名冊”，Klee有100個數學后代（他也有“正規的”孩子及孫輩）。Klee在華盛頓大學的大部分時間里，另一個突出的幾

5、何學家Branko Grünbaum也在那里。Klee和Grünbaum同處一地的30年時光使得華盛頓大學成為一個不斷發展的新型幾何中心。Klee從1971年至1972年擔任美國數學會的會長。他對組合學、凸性、算法及優化問題作出了貢獻，但他的工作始終有一個強烈的幾何風味。要充分認識Victor Klee在最近的幾何演變過程中所占的位置，有必要先講點題外話來簡短地看一看幾何從古代到近代的演變。什么是幾何在20世紀的初葉，幾何的研究處在一個十字路口上。19世紀末，不僅從數學而且從一般知識的觀點中，幾何的世界被思想史上的偉大里程碑之一所震撼。大部分歷史中的幾何研究支柱一直是歐幾里

6、得的幾何原本。這本書自從出世就已經歷盡眾多的版本和若干語言的翻譯。盡管我們對歐幾里得這個人知之甚少，并且沒有這本書可以追溯到甚至接近歐幾里得生活過的時代的版本，原本一直是幾何演變的中心。兩千年來，原本的內容不斷讓數學保持活力，并激勵了許多人成為數學家，特別是幾何學家。原本中有許多漂亮的結果，包括5個正多面體和素數的討論。稱為歐幾里得算法的尋找兩個正整數最大共因子的開創性算法，也可以在那里找到。歐幾里得著名的第五公設是：“如果與兩條直線相交的一條直線同一邊的內角之和小于兩直角，則這兩條直線，如果無限延長的話，將在滿足上面條件的那一邊相交?！睂υS多人而言，這似乎比其他公理更為復雜，人們試圖使用其他

7、公理通過邏輯法則來證明這個公理。直到19世紀后期人們才認識到這些努力注定要失敗。這項工作是由高斯、鮑耶、羅巴切夫斯基作出，但只有后兩位發表了他們的研究結果。所出現的是激動人心的一些幾何。它們通常被稱為“古典非歐幾何”，它們由把第5公設修改為“不存在通過給定的P點與直線m平行的直線”或“存在許多通過給定的P點與直線m平行的直線”而誕生。經典非歐幾何之一是射影幾何。你可以把這個幾何視為起始于3維歐氏空間中的一個球面?！靶隆睅缀稳绾谓忉屛炊x的術語“點”和“線”？在“新”幾何中，一個點將與球面直徑的兩端點等同起來，也就是說，如果P和P是一條直徑的兩端點，則把集合P,P看作一個點?！靶隆睅缀蔚木€將是球

8、面上中心為球心的圓?，F在很容易看到，這些點和線的定義導致“兩點確定一線”和“兩線交于一點”的結論，因此，我們有一個沒有平行線的幾何。下面的圖示可以幫助你直觀了解雙曲平面或鮑耶-羅巴切夫斯基平面的某些方面，這是另一傳統的非歐幾何。它被稱為凱萊-克萊因模型，因為數學家阿瑟·凱利和費利克斯·克萊因的研究之故。如果點和線未定義，我們可以如下解釋這兩個術語。一個點將意味著圓內任何一點，如圖2所示。一根線將意味著圓的任何弦（不包括邊界點）。因此，圖中的線m由弦上的點組成，但為了我們的目的，弦位于圓周上的兩個終點將被“刪除”。現在，你可以看到，如果點P不在m上，則有很多甚至無窮多的弦經過

9、P點且和弦m不相交。這樣，我們有無窮多個通過P點與不包含P點的線m平行！圖2：一個幾何模型和許多線平行于給定線穿過一個點。非歐幾何的發現在哲學界以及數學界造成了某種“危機”。由于從數學的角度看射影幾何和雙曲幾何都同等立足于歐幾里得幾何，什么是物理空間的真正幾何這一問題出現了。也許我們生活的空間不是歐幾里得的版本?。ㄔ跉W幾里得幾何里平面三角形的內角和等于180度，而在球面幾何中它們的和超過180度，在雙曲平面里小于180度。它也提出了幾何的研究應采取什么樣的方向的問題。相對而言，雙曲平面的研究比歐幾里得幾何更需精致。數學教育工作者面臨著多少注意力應該投向于新幾何的問題（在此期間有限幾何也得到發展

10、）。隨著澄清了歐幾里得的“疏忽”并為歐氏幾何提供了一個獨立的公理集合（即沒有公理可由其他公理證明）的希爾伯特公理體系的發表，幾何似乎在某些方面“失去勢頭”。在幾何研究的低潮時期，一定程度上重振幾何雄風的是杰出的幾何學家Harold Scott MacDonald Coxeter.Coxeter是傳記拯救幾何的人的主角，他屬于成長于19世紀幾何的那部分人。他的工作強調了幾何的度量（距離）和公理方面?？v觀一生，他充當著過去（19世紀及更早）的幾何和20世紀幾何學家涌現的新興趣之間的“橋梁”。Coxeter也作出了幾何和代數之間的連接。特別是，他發現了使用群理論和對稱性思想的力量來得到關于幾何問題的

11、洞見。Coxeter探索過包括高維多面體的許多問題。這項工作涉及到非常對稱的多面體，是歐幾里得曾經研究過的著名的五個正多面體（柏拉圖立體）的類似物。比Coxeter小18歲的Klee將全力遵循“幾何傳統”，但帶有與Coxeter非常不同的興趣點，部分地緣由他在拓撲方面的訓練。Klee的數學Klee的數學貫穿于幾何的許多方面。下面，我想提請注意Klee參與的三個重要成果，它可以用初等術語討論：畫廊定理、Klee-Minty多面體和Kleetopes。我們先品嘗幾樣東西，顯示他對理論和應用數學論題興趣交融。他對凸多面體的理論作出了特別重要的貢獻，尤其是高維空間的多面體。一個多面體是一有界凸集，它是

12、平面的高維類似物的交集。（注：如果對一個集合中的任意兩點p和q，連接p和q的線段也在集合中，則該集合稱為是凸的。）圖3：凸五邊形(左)；非凸五邊形(右)多面體理論雖然從理論數學的角度來看屬于理論領域，但它與應用數學有著戲劇性的連接。線性規劃二戰期間，大批的男性和大量的材料必須從美國轉移到歐洲和太平洋戰區。經過大蕭條陣痛的美國，改裝工廠制造戰爭物資，而不是消費類產品。數學的一門新的子學科，運籌學或管理科學，在戰爭結束后出現。這項工作根植于為贏得二戰勝利而找到的一些數學工具。（數學在戰爭中的另一勝利是破譯德國和日本的密碼。）二戰結束后，生產管理、調度、成本最優化等大型問題在政府和企業中變得越來越重

13、要。這個新數學分支的基石成為眾所周知的線性規劃。一個典型的線性規劃問題可能涉及到如何從不同種類的原油生產出不同類型的汽油。其想法是，每個產品的生產需要一定數量的原材料。此外，一定數額的原材料以不同的成本可以獲得。這個過程的的目標是以最小成本從現有的原油供應生產所需汽油。類似的問題數學上可以表達成在一個線性不等式系統約束下找到一個線性表達式的最小值或最大值。如下顯示一個線性規劃的“嬰兒”問題，讓你看一看它的數學術語像什么：最小化3x+5y,其中2x+y4,3x+5y15且x0,y0.上述不等式對應于2維空間中某個多邊形中的點（在下面圖4中以紅色顯示；你能找到G點的坐標嗎？）。更一般的問題通常有數

14、百個變量，也許有數千個約束。這些問題導致多邊形概念在高維空間的推廣問題。這些就是稱為多面體的對象。滿足這些約束條件的點原來是一個高維多面體上面或內部的點。然而，值得注意的是，可以證明這樣一個問題的最優解總可以在“可行”多面體的某個頂點達到。在圖4的多邊形中有4個頂點，我們可以限制于此，以確定滿足約束的所有點的最大值發生在何處。給出這個結果的定理有時也被稱為角點定理。敘述這一結果的另一種方式是：不必檢查無窮多點求出最優（最佳）解，僅僅檢查有限多個角點，看最好的解在哪個點出現就可以了。圖4：分它滿足一個線性規劃問題的內容為了解決大型線性規劃問題，人們使用稱為單純形算法的一個工具，它由美國數學家Ge

15、orge Dantzig在二戰結束后不久發明的。單純形算法使得求解大規模生產、資源分配、調度和產品制造問題成為可能。然而，盡管該算法似乎能用合理的電腦時間來解決大型問題，當時還不清楚算法的理論復雜性是什么；即當線性規劃問題用變量和約束的數量來衡量的規模越來越大時，需要多少電腦計算量來求解這些問題？單純形法的工作方式是，它首先找到一個可行點，即滿足給定約束條件的點。假設我們正試圖求解的線性規劃問題是一個最大化問題。我們尋找變量的值使得某個線性函數（稱為目標函數）的對應值盡可能地大。從這個可行點開始，算法選擇可行多面體上與目前頂點以邊相接的一個相鄰頂點，檢查該點目標函數值是否不減。最終可以到達一個

16、點，使得目標函數在所有鄰點上的值都沒有比當前值更大，也就是說當前值就不能被改善。Victor Klee在幫助建立線性規劃的應用世界和多面體理論的理論景觀之間的連接方面起了關鍵的作用。他這方面的工作就是現在所謂的Klee-Minty多面體，與George Minty的合作成果。Klee的許多論文來自于他對線性規劃問題的興趣。如上所述，線性規劃是一個離散的優化模型，其目標是最大化或最小化變量在某個凸多面體內取值的一個線性表達式。由于線性規劃問題出現在各種各樣的情況中，包括資源分配、調度和混合，當問題的規模非常大時，采用單純形法需要多少計算時間變成一個有趣的問題。盡管在實踐中能快速求解問題，沒有理論

17、證明對于大規模問題的計算工作量是以小于多項式的方式增長的。Klee和Minty通過例子證明，對某些問題，單純形法可能需要指數量增長的時間求解。他們巧妙的構思是修改一個非常對稱的高維立方體結構，比如說d-立方體（有2d個頂點）。下面的圖顯示了一個4維的立方體。圖5：4-cube的示意圖通過選擇d-立方體的一個合適變形，Klee和Minty證明，從一個特定點開始的單純形算法將跑遍d-立方體的所有（這是指數級別的大數2d）頂點才到達目標函數取最優值的那個頂點。這意味著單純形算法沿著一條“哈密爾頓路徑”行進（也就是說，當路徑通過d-立方體的所有頂點時，路徑的第一個和最后一個頂點不必由一條邊相連）。這族

18、例子現在已為Klee-Minty立方體。Klee-Minty例子表明，實際中的線性規劃問題似乎沒有像需要指數級工作量多面體那樣的可行區域，因為在實踐中單純形算法運行很快。這項工作來自于Klee關于高維多面體路徑結構的理論工作，展示了數學中的理論和應用想法可以相得益彰。直至今天，Klee提出并為之工作過的關于多面體直徑的一些問題（如d-多面體的頂點相距多遠），仍然沒有得到解決?？傊?，Klee和Minty所做的是構造一族多面體，其頂點的個數關于維數呈指數增長，并且當單純形法應用到這些多面體上的線性規劃問題時，然而該方法需要造訪多面體的所有頂點才能達到最優值。這族例子表明，單純形算法可能需要指數增長

19、的工作量?，F實世界中的線性規劃問題從來沒有見到過這么大的工作量，其中的原因尚不完全清楚。在實踐中，大型線性規劃問題通常采用單純形法很快求解。這使得世界各地的政府和企業生活得更輕松！Kleetopes早在多面體的歷史之初，多面體是否有一個包括其所有頂點的簡單閉回路的問題，即哈密頓回路問題，一直是數學家感興趣的。這種興趣部分源于這樣一個事實：至少有三條邊與某點相連的凸多面體如果有一個哈密頓回路，那么它的面可以用4種顏色著色?？吹竭@一點的方式是3維的凸多面體可以畫在平面上。一旦有這樣一個“平面”繪畫，如果這個圖P有一個哈密頓回路（由P的頂點和邊組成），則將約當曲線定理用于哈密頓回路，圖內圖外均有面。

20、現在可以分別用2種顏色著色內部和外部的面。下圖顯示了一個典型的例子。注意此圖中有一藍綠色特殊面，它圍繞所有其他面。哈密頓回路以粗黑邊顯示。哈密頓回路內的面所用的兩種顏色是紅色和綠色，而哈密頓回路外的面所用的兩種顏色是藍色和藍綠色。圖6：在飛機上畫一個圖，其中用4種顏色為哈密頓回路地區上色。（事實證明，處理四色問題的這種方法不奏效，因為存在非哈密頓3-價多面體，第一個這樣的例子屬于W.T. Tutte。）Klee自然有興趣問高維多面體是否總有哈密頓回路。這部分是因為他對線性規劃問題以及與多面體路徑相關的理論問題的濃厚興趣。使用一個非常簡單的想法，他證明了：對每一維數存在非哈密頓多面體。他的想法在

21、3維情形可用稱為“Kleetope”的思想來說明。從一個所有面都是三角形的多面體開始。圖7給出了這樣的一個例子。圖7：三角形面多面體圖該圖是正八面體的圖。注意它有6個頂點和8個面。因此，多面體有比頂點更多的面。Klee建立一個非哈密頓多面體的方法是在這個多面體的每個面上豎立一個金字塔。構造在圖8中進行。圖8：在圖7多面體的面孔上繪制的金字塔。這個新的多面體被稱為作為Kleetope。圖7中原來的頂點用小圓圈表示，金字塔“尖頂”的新頂點用小正方形顯示。注意此圖不是一個二分圖。（二部圖的頂點可用兩種顏色著色，使得任一邊兩端的頂點有不同的顏色。）然而，正方形的頂點僅僅聯接到圓圈標記的頂點，但圓圈標記

22、的頂點聯接到圓圈標記的頂點和正方形標記的頂點。上圖不能有一個哈密頓回路，因為要到達一個正方形的頂點，必須從一個圓的頂點而來，但沒有足夠多這樣的頂點與正方形的頂點形成一個簡單的回路，因為最初的多面體有比頂點更多的面。上述圖是一個組合圖，對于它Steinitz定理保證了圖可以由一個凸三維多面體實現。然而，為此目的不必調用Steinitz定理，如Klee所觀察到的。假設在圖7中挑選多面體的一個特別三角形。如果在這個面內部的上方選擇一個點非?？拷@個面，然后這個面上的“平”的金字塔不會破壞所產生的新的多面體的凸性。這個過程可以對圖7中原先多面體的每個面依次進行，直到得到一個和圖8有同一個圖的多面體。類似的想法在d維同樣可以進行，這時沒有Steinitz定理的類似物成立。因此，Klee的簡單想法使人們可以看到如何構造高維的非哈密頓凸多面體（及它們的圖）。這促使人們有興趣問具有更強性能的高維多面體是否總有哈密頓回路。例如，Victor Klee的博士生之一David Barnette的一個懸而未決的問題涉及4維多面體的哈密頓回路。一個d-維的凸多面體被稱為是簡單的，如果它每一個頂點都是d價（階）的。因此，一個簡單的3維凸多面體將有3價，而一個簡單的4維凸多面體有4價。雖然存在3價的非哈密頓簡單3維多面體（最小的例子有38個頂點），Dav