王獻芬

(河北師范大學 數(shù)學與信息科學學院,石家莊,050016)

惠特尼 (HasslerWhitney,1907—1989年)[1]是美國最具國際影響的數(shù)學大師之一。1982年,他成為第一位獲國際最高數(shù)學大獎之一——沃爾夫 (R.Wolf,1887—1981年)獎的美國數(shù)學家。他的重大成就主要在拓撲學領(lǐng)域,開創(chuàng)了一系列新概念、新理論,其中最主要的是擬陣、微分流形的拓撲學、上同調(diào)、纖維叢、示性類 (特別是施蒂費爾-惠特尼示性類)、分類空間、分層、可微映射的奇點理論和幾何積分論等[2,3]。他是微分拓撲學的主要奠基人之一。他的貢獻已成為現(xiàn)代數(shù)學的基礎(chǔ) (例如:李群是微分流形),影響了 20世紀50—70年代主流數(shù)學的發(fā)展。當時,幾乎有一半菲爾茲獎獲得者的思想來源直接與他有關(guān),如托姆 (R.Thom,1923—2002年)、米爾諾 (J.Milnor,1931—年 )、斯梅爾 (S.Smale,1930—年)等。1958年獲得菲爾茲獎的托姆吸收了惠特尼關(guān)于可微映射的奇點理論的思想;米爾諾由于大大發(fā)展了惠特尼的理論,榮獲 1962年菲爾茲獎,而在大會上介紹米爾諾工作的正是惠特尼;斯梅爾于 1966年獲菲爾茲獎主要因為證明了廣義龐加萊 (H.Poincaré,1854—1912年)猜想,其中引用了惠特尼的論文 Differentiable manifolds(Ann.of M ath,1936年,37卷,第 645—680頁)?？梢娀萏啬岬挠绊懼?此外,他還影響了中國數(shù)學家吳文俊。吳文俊的早期拓撲學工作就是對惠特尼工作的直接繼承和發(fā)展:他第一個工作是關(guān)于惠特尼對球叢乘積公式的明顯證明;他關(guān)于示性類的工作是對惠特尼示性類工作的發(fā)展,著名的吳-公式就是關(guān)于施蒂費爾-惠特尼示性類的表示公式;他的示嵌類工作的出發(fā)點是惠特尼的微分流形在歐氏空間中嵌入理論的延續(xù)和發(fā)展。在 2008年出版的《吳文俊選集》中,30余篇拓撲學論文中只有 5篇吳自己認為是最重要的文章,而每篇都引用了惠特尼的論文[4]。

惠特尼生于一個學術(shù)世家。祖父W.惠特尼 (W illiam D.Whitney,1827—1894年)是語言學家,外祖父紐康門 (Simon Newcomb,1835—1909年)是天文學家和數(shù)學家,他們都是美國科學院院士。父親 E.惠特尼(Edward B.Whitney)是法官。

惠特尼興趣廣泛。1928年,取得哲學學士。第二年又拿到音樂學士學位。同年,因?qū)λ纳孪敫信d趣,便考取了哈佛大學伯克霍夫 (G.D.Birkhoff,1884—1944年)的博士研究生,專攻圖論,于 1932年獲哲學博士學位。由于工作出色,1931—1933年就成為美國國家研究委員會成員。1935年,他參加在莫斯科舉行的一次國際拓撲學家大會[5],此次會議影響了他以后的學術(shù)生涯,對他轉(zhuǎn)向拓撲學方向具有決定性意義。為什么這么說呢?筆者認為,這與他的早期圖論工作有關(guān)。由于沒能成功解決四色猜想,客觀上也促使他將精力投入到拓撲學研究;同時,因為他研究圖論時的拓撲學思維為其后來轉(zhuǎn)向拓撲學奠定了思想基礎(chǔ)。

無獨有偶,伯克霍夫在成為國際知名的數(shù)學家以前,也熱衷于四色猜想。他是當今熱門的動力系統(tǒng)理論的奠基者。1913年,他由于證明了龐加萊最后定理,轟動了整個數(shù)學界。但是,就四色猜想而言,惠特尼和他都未取得成功。

然而在研究路線上,惠特尼與伯克霍夫不同。19世紀末以前,四色猜想主要有兩條研究途徑:一是英國數(shù)學家、律師肯普 (A.B.Kempe,1849—1922年)于 1879年提出的可約構(gòu)型和肯普-鏈方法;一是英國物理學家、數(shù)學家泰特 (P.G.Tait,1831—1901年)[6]于1880年對三次正則圖的邊著色研究。進入 20世紀,數(shù)學家們對四色猜想的證明基本上是按照肯普的想法在進行。1913年,伯克霍夫在肯普的基礎(chǔ)上引進了一些新技巧。沿此路線,最終由阿佩爾 (K.Appel,1932—年)和哈肯 (W.Haken,1928—年)[7]于 1976年借助計算機證明了四色定理。與伯克霍夫不同,惠特尼是按照泰特的思路進行的。為解決四色猜想,他開始研究圖論。自 1931年起,除提前刊于《美國科學院學報》的 2篇概要外[8,9],他還相繼發(fā)表了 10篇圖論論文[10—19]。這 10篇論文雖未成功解決四色猜想本身,但由此而得到的一些概念、定理及方法,對圖論后來的發(fā)展影響深遠,其中,最突出的成就就是創(chuàng)立了擬陣論這一新分支[19]。

分析惠特尼早期致力于圖論研究的這些工作,可以更好地幫助我們理解圖論乃至擬陣論的思想框架和發(fā)展脈絡(luò),以及這兩門學科之間的聯(lián)系。然而,遺憾的是,目前關(guān)于惠特尼對圖論的貢獻的歷史研究還比較零散。鑒于此,筆者潛心研究了惠特尼于 1931—1935年發(fā)表的圖論方面的全部原始文獻,并結(jié)合相關(guān)理論的當前動態(tài),追根溯源,論述了下述重要理論的來龍去脈。特別地,從惠特尼研究四色猜想的切入點考慮,筆者把這些文章大體分成了四類:

(1)一些文章主要研究可平面圖[9,11,15—18]?；萏啬岬拇蟛糠謭D論工作都與可平面圖有關(guān),他給出了平面圖的判定定理,并將平面嵌入與圖的連通性聯(lián)系起來,為以后一般曲面的嵌入理論打開了道路。

(2)一些文章主要研究平面圖的哈密頓回路問題[10,12]?；萏啬岬玫搅怂纳孪氲囊粋€等價命題,他的工作引導了一般意義上平面圖哈密頓回路問題的研究。

(3)一些文章直接與著色問題有關(guān)[8,13,14],主要研究了色多項式理論?；萏啬釋⒉嘶舴虻纳囗検接傻貓D (map)推廣到了一般的圖 (graph),這種推廣從理論上開拓了色多項式的一般性研究,為后續(xù)發(fā)展提供了廣闊的空間。

(4)最后也是最重要的一篇文章——《關(guān)于線性相關(guān)性的抽象性質(zhì)》([19],509—533),標志著擬陣論的誕生。開創(chuàng)擬陣論并奠定其基本理論是惠特尼在圖論中的最大成就。

相應(yīng)地,本文在對原始文獻進行分類研究的基礎(chǔ)上,從以下四個方面論述了惠特尼對圖論的貢獻:可平面圖、平面圖的哈密頓回路問題、色多項式和擬陣理論。前兩個屬于平面圖理論,色多項式直接與著色問題相關(guān),而擬陣理論是惠特尼從圖論研究中開創(chuàng)的一門新理論。文中一些術(shù)語詳見文獻[20—22]。

1 可平面圖

在圖論中,可平面圖是指可嵌入到平面的一類圖。這種圖當被畫到一個平面上時,邊只能在端點處相交。這屬于可平面圖的刻畫問題。它一直是平面圖理論的核心問題之一。若而當 (C.Jordan,1838—1922年)首先意識到平面上不自交的閉曲線將平面劃分為內(nèi)、外部兩個區(qū)域,直到 1905年,維布倫 (O.Veblen,1880—1960年)才給出第一個正確的證明[23]。1930年,波蘭數(shù)學家?guī)炖蟹蛩够?(K.Kuratowski,1896—1980年)[24]得到了第一個可平面圖判定定理:一個圖可平面必定不含同胚于K5和K3,3的子圖①1930年,美國數(shù)學家弗林克(O.Frink)和史密斯(P.A.Smith)獨立于庫拉托夫斯基也得到了相同的結(jié)論。但這個定理一般稱為庫拉托夫斯基定理。。這是從解析拓撲的觀點對平面圖進行刻畫的。

實際上,在庫拉托夫斯基證明他的著名定理以前,人們認為可平面圖的概念可以通過一些組合的而非拓撲的性質(zhì)來刻畫?？履嵯?(D.K?nig,1884—1944年)早在 1916年就斷言,四色猜想的進展可能依賴于平面圖的這種刻畫[25]。盡管這個著名猜想對于庫拉托夫斯基的發(fā)現(xiàn)并無幫助,但沒過多久,它卻間接地啟發(fā)了另一位數(shù)學家的思想,這位數(shù)學家就是惠特尼。

惠特尼研究可平面圖的方法是建立在推廣對偶概念的基礎(chǔ)上的。在圖論中,對偶一般是指平面或球面上的圖的對偶。對偶的思想源于多面體與多面體之間的對偶關(guān)系[26]。對偶被廣泛地應(yīng)用于圖論主要還是由于四色猜想?？掀赵缭?1879年就已指出,通過地圖的幾何對偶,四色猜想可以等價地考慮其對偶圖的頂點著色,其中相鄰頂點著色不同[27]。然而,這種將對偶應(yīng)用于地圖著色的想法,直到 20世紀 30年代,由于惠特尼的工作才得以發(fā)展。

當把這種對偶應(yīng)用于平面圖時,問題出現(xiàn)了:在數(shù)學中,某一對象的對偶的平方 (即兩次對偶)等于自身是一種好的性質(zhì),但就平面圖而言,卻不保持這一特性;此外,對偶依賴于特定的平面嵌入,換言之,對偶并不唯一,同一個圖可以有不同構(gòu)的對偶圖。

所以,通常的對偶導致了對偶圖與原圖之間的某些組合關(guān)系。惠特尼研究了這些組合關(guān)系,并推廣為一種代數(shù)對偶①本節(jié)若不特別說明,均簡稱對偶。的概念。后人為紀念他,也稱它為惠特尼-對偶②惠特尼-對偶,簡寫為 W-對偶 [O.Ore(1899—1968年),1967年 ],也稱組合對偶 [F.Harary(1921—2005年 ),1969年 ]。。這種推廣并不是平凡的推廣,惠特尼說:“它與平面或球面圖的通常的對偶是一致的,但對于較高連通性的曲面 (如環(huán)面)的圖,一般不存在 (抽象)對偶”[11]。換言之,他的對偶概念能夠區(qū)別一個圖可平面與否。1931年,他在《不可分離圖和可平面圖》概要中[9],宣布了他的結(jié)論。一年后,發(fā)表了全文 ([11],339—362)。文章共分三部分:第一部分主要是對不可分離圖的一般性研究;第二部分用組合方法定義了圖的對偶,并研究了可平面圖的對偶;最后一部分,證明了他的平面圖判定定理。

惠特尼強調(diào),“秩和零化度的概念是基本的”([11],339頁):

……任意給定一個圖G,如果其頂點、邊和連通分支數(shù)分別為V、E、P,那么G的秩R和零化度N由下面式子確定:它們是“龐加萊的矩陣H1的秩和零化度”([11],340頁)。實際上,惠特尼是吸收了龐加萊的思想[28],并把后者的關(guān)聯(lián)矩陣的秩和零化度,巧妙地定義成圖的秩和零化度。一旦在圖論中引入了這兩個概念,圖的許多組合性質(zhì)就能由它們揭示出來了。特別是,由此還可以引入下一個更加深刻的概念:

定義 從圖G到G′有一個 1-1映射,令H為G的任一子圖,H′為H在圖G′中所對應(yīng)的圖的補圖,如果r′=R′-n,則稱G′為G的一個對偶。其中R,R′,r,r′分別是G,G′,H,H′的秩;n為H的零化度。([11],351頁)

這就是惠特尼定義的代數(shù)對偶概念。為了證明他的平面圖判定定理,惠特尼首先應(yīng)用代數(shù)對偶給出了一個與“邊收縮”有關(guān)的引理:G與G′為對偶圖,若G中的邊α對應(yīng)于G′中的邊α′,則從G中刪去α后所得的圖Gα,與在G′中收縮α′后所得的圖G′/α′互為對偶圖([11],356頁)。根據(jù)這個引理和若爾當曲線定理,惠特尼證明了主要定理:

定理 29 一個圖是可平面的充分必要條件是它存在對偶。([11],357頁)最后,他還研究了他的平面圖判定定理與庫拉托夫斯基定理之間的聯(lián)系。他證明,K5和K3,3及它們的重分均不存在代數(shù)對偶。換言之,由庫拉托夫斯基定理可以推出惠特尼的定理。1933年,他進一步證明,該命題的逆命題也成立([18],81頁)。他不僅說明了這兩個定理的等價性,同時還給出了庫拉托夫斯基定理一個拓撲意義不強的證明。這是平面圖理論上的一個重大進步。

就代數(shù)對偶的判定,惠特尼還明確指出,在確定兩個圖是否互為對偶時,不必考慮它們所有的子圖,只需考慮其中一部分即可([18],73—76頁)。為說明這一點,他還研究了平面圖確定對偶圖的程度。他證明,如果G′是G的對偶,則G″是G的對偶當且僅當G′與G″是 2-同構(gòu)的。換言之,同一個平面圖的對偶圖不唯一,但卻是 2-同構(gòu)的。進而,他在《同構(gòu)圖與圖的連通性》中又證明:3-連通平面圖有唯一的代數(shù)對偶([12],79頁)。也就是,3-連通可平面圖有唯一的平面嵌入,而嵌入其他曲面時,一般不成立。這就是著名的惠特尼唯一性定理。另外,在引入圖的 2-翻轉(zhuǎn)和相似嵌入的概念后,他還研究了 2-連通圖嵌入平面的問題,并證明,任意兩個 2-連通圖在平面內(nèi)的嵌入是惠特尼-相似的([17],245—254頁)。這激發(fā)后人研究與圖的連通性有關(guān)的平面嵌入問題[29]。

惠特尼由于揭示了圖嵌入平面的一些重要性質(zhì),被認為是繼歐拉、庫拉托夫斯基之后拓撲圖論的又一位先驅(qū)。他運用代數(shù)對偶的存在性對平面圖特征的刻畫,似乎不是一個十分深刻的結(jié)論,但它卻具有非常重要的理論意義:它給圖論和擬陣論之間的聯(lián)系提供了重要紐帶。在惠特尼解決了判定圖的平面性問題之后,可平面圖的研究引起了人們的極大興趣:麥克萊恩(S.Mac Lane,1909—2005年)[30]、吳文俊、塔特 (W.T.Tutte,1917—2002年)[31]等都曾相繼在這方面建立了他們各自的理論。

2 平面圖的哈密頓回路問題

哈密頓圖的刻畫是圖論中最具挑戰(zhàn)的問題之一,其主要任務(wù)是尋求一個圖含有哈密頓回路的充分必要條件。哈密頓回路是經(jīng)過每個頂點一次且只經(jīng)過一次的回路。這個遍歷問題是由柯克曼 (T.P.Kirkman,1806—1895年)和哈密頓 (W.R.Hamilton,1805—1865年)在 19世紀中期提出來的,哈密頓圖因后者的名字而得名 ([26],21—36頁)。起初哈密頓問題所研究的圖與四色猜想所研究的圖一樣,都是平面圖,后來才推廣到其他曲面上的圖。自然地,平面圖的哈密頓回路問題就與四色猜想產(chǎn)生了不解之緣。泰特在研究四色猜想時最早注意到了它們之間的聯(lián)系,雖然他提出了一個后來發(fā)現(xiàn)是錯誤的假設(shè),但正是這個假設(shè),使對四色猜想感興趣的另外兩位數(shù)學家在平面圖哈密頓回路問題上作出了巨大貢獻,他們就是惠特尼和塔特。

19世紀末以來,數(shù)學家對圖論的興趣主要集中在四色猜想上。由于地圖上區(qū)域及其鄰接方式千變?nèi)f化,導出的 (幾何)對偶圖的頂點之間的鄰接關(guān)系相應(yīng)地也就復雜多端,所以要得出一個普遍的數(shù)學證明十分困難。凱萊 (A.Cayley,1821—1895年)和肯普都已指出,只要就 3-正則圖的情況,證明四色猜想就夠了。1880年,泰特證明,3-正則圖的頂點 4-著色等價于對其邊進行 3-著色 ([6],501—503頁),這個等價命題本質(zhì)上是正確的,但泰特在論證 3-正則圖可邊 3色時,用到了一個有關(guān)平面圖的哈密頓回路問題的假設(shè):任何 3-連通、3-正則平面圖都是哈密頓的。泰特對此深信不疑,但他沒有給出證明。這樣,四色猜想仍是一個懸案。許多人想證明泰特猜想也沒能成功。

盡管如此,泰特卻把四色猜想與 3-正則平面圖的哈密頓回路問題聯(lián)系起來。從此,圖論中的兩大難題不再是孤立的了,人們開始認為四色猜想的解決可能在某一天隨著平面圖哈密頓問題的解決而解決。那么到底在什么條件下一個平面圖才是哈密頓的呢?這方面的研究開始于惠特尼關(guān)于極大平面圖的工作[10—12,18],后來塔特在此基礎(chǔ)上推廣到了一般的平面圖 。

1931年,惠特尼發(fā)表了第一篇圖論文章,題為“圖的一個定理”,該文于 1930年 2月22日提交給美國數(shù)學會,刊于《數(shù)學年刊》[10]?；萏啬嵩陂_篇的引言中就陳述了基本定理:

定理Ⅰ 給定一個平面圖,它由基本三角形構(gòu)成,其中的回路除這些基本三角形外,沒有 1-回路、2-回路或 3-回路,則這個平面圖存在一個通過所有頂點的回路。([10],378頁)

惠特尼討論的這類平面圖即極大平面圖,他實際上得到了極大平面圖包含哈密頓回路的條件:一個極大平面圖,若無分離三角形,則存在哈密頓回路。由于極大平面圖是 3-正則平面圖的 (幾何)對偶圖。因此,所有極大平面圖的結(jié)果均有 3-正則平面圖的對偶形式,只是在表達方式上有繁簡之分。換言之,惠特尼證明了無環(huán) 3-正則圖的對偶圖總是哈密頓的[10,33]。由此,惠特尼還得到了四色猜想的一個等價命題:四色猜想成立當且僅當一個哈密頓的平面圖可四色。即只要考慮平面圖是否是哈密頓的就足夠了。這是一個深刻的結(jié)論,任何試圖領(lǐng)會惠特尼圖論貢獻的人都必將承認這一點 ([26],185頁)。對此,塔特后來在《我所了解的圖論》中也給予了極高的評價:這可能是當時圖論的至高點。[34]

圖的哈密頓回路問題與圖的連通性有關(guān)。圖的連通性中有一個著名定理是由門格爾(K.Menger,1902—1985年)于 1927年證明的門格爾定理。門格爾定理將圖的連通性與圖中兩個不同頂點之間的頂點-不鄰接道路的數(shù)目聯(lián)系了起來。此后,圖論中出現(xiàn)了它的許多“變式”和推廣。1932年,惠特尼對連通性進行了推廣,獨立地得到了門格爾定理的第一個變式,即惠特尼定理。這些思想包含在《同構(gòu)圖和圖的連通性》一文中 ([12],150—168頁 )。

惠特尼在文中首先給出了兩圖同構(gòu)的條件,他證明,

定理 1:令G和G′均是連通圖,且均不含ab,ac,ad型的三邊。對于兩圖的邊之間的 1-1對應(yīng),若使得一個圖中任意兩條有公共頂點的邊對應(yīng)于另一圖中兩條有公共頂點的邊,那么G和G′是全等的(congruent)。([12],150頁)

進而他又證明,

定理 2:令G和G′均是 3-連通圖。對于它們的邊之間的 1-1對應(yīng),若使得一個圖中任意構(gòu)成圈的邊集都對應(yīng)于另一個圖中一組構(gòu)成圈的邊集,那么G和G′是全等的。([12],156頁)

顯而易見,他的“全等”即現(xiàn)在意義上的同構(gòu)。請注意惠特尼在定理 2的條件中,考慮了連通性更強的 3-連通圖。這告訴我們,連通性是尋找哈密頓回路的基本出發(fā)點,要想深入研究圖的哈密頓回路問題,不能只滿足于一般的連通性,而需要定義反映頂點之間更緊密聯(lián)系的n-連通性。

接著,他給出了n-連通圖的定義:

令圖G至少包含n+1個頂點,不可能通過去掉n-1個或更少數(shù)頂點及其相關(guān)聯(lián)的邊,破壞圖的連通性。那么就稱圖G是n-連通的。([12],158頁)

這樣,通常的連通圖即 1-連通圖。那么,“更加連通”的n-連通圖又有何特征呢?惠特尼下面這個定理揭示了n-連通圖的一個自然的本質(zhì)特征:

定理 7 一個無重邊的 (非平凡)圖是n-連通的充要條件是其任意兩個頂點之間都有n條不相交鏈。([12],160頁)

這就是惠特尼定理。它給出了n-連通圖的一個判別法則。

另外,惠特尼還定義了圖G的連通度 (即頂點-連通度)概念:“若G是n-連通的但不是n+1連通的,則G的 (頂點)連通度為n”([12],158頁),這是圖的最重要的連通性參數(shù)之一,另一個是邊-連通度。二者在決定兩個圖哪一個“更連通”時非常有用。特別地,惠特尼還得到了它們與圖的頂點度之間的一個重要不等式,即頂點連通度≤邊連通度≤頂點度。

由n-連通圖的定義知,2-連通圖即任意兩個頂點之間都存在 2條內(nèi)點不鄰接道路。2-連通性的重要意義在于它能給出哈密頓圖的必要條件,也就是,任何哈密頓圖一定是 2-連通的。但這只是一個必要條件,反過來,2-連通圖未必都是哈密頓圖。

惠特尼的n-連通圖概念為后人研究平面圖的哈密頓回路問題提供了概念基礎(chǔ)。由此,人們希望 3-連通圖可能使條件有所改進,但這也是辦不到的。1946年,圖論大師塔特首先舉出了反例,否定了泰特猜想 ([31],45—50)。塔特在找出泰特猜想的反例后,并未就此停止,他進一步考慮了反映圖結(jié)構(gòu)更緊密的 4-連通性。他通過把惠特尼定理證明的每一步,依次推廣至所有平面圖,從而使他在 1956年證明了,每個 4-連通可平面圖均是哈密頓的 ([31],837—874)。之后,許多數(shù)學家運用惠特尼的n-連通性研究平面圖的哈密頓回路問題,他們沿著惠特尼鋪墊的道路不斷前進。如格林伯 (è.Grinberg)[35],鮑耐特(D.Barnette)[36]等。

惠特尼雖未能最終解決四色猜想,但他對圖論做出了巨大貢獻,他把四色猜想等價于證明平面圖含有哈密頓回路的命題成為當時圖論研究的至高點。他還為圖論引入了新的概念,無論是對一般意義上的平面圖哈密頓問題還是圖的結(jié)構(gòu)研究都具有重要意義。他進行數(shù)學研究正如他愛好登山一樣表現(xiàn)出驚人的耐性和創(chuàng)造力。除上述與平面圖理論有關(guān)的兩方面貢獻以外,惠特尼為了解決四色猜想,還研究了色多項式理論。

3 色多項式

色多項式是現(xiàn)代圖論的一個核心概念,是代數(shù)圖論中一個重要結(jié)構(gòu),而且由此產(chǎn)生了圖著色的重要分支。色多項式是一個關(guān)于色數(shù)的函數(shù),用來計算圖著色的數(shù)目。它是由伯克霍夫為研究四色猜想于 1912年[37]最早提出的,后來由惠特尼和塔特推廣到了塔特-惠特尼多項式。

伯克霍夫曾把人們關(guān)于四色猜想的研究方法分成兩類:“定性方法”和“定量方法”[38]?！岸ㄐ苑椒ā?即假定比地圖M面數(shù)少的所有地圖均可四色,再從得到的信息中推斷M也可四色。他認為,色多項式以前,四色猜想的研究主要集中于“定性方法”。色多項式是作為研究四色猜想的一種“定量方法”而引入的:

讓我們不要只滿足于區(qū)別可四色和不可四色。對于任意一個地圖M,對它進行四著色的方法數(shù)都是一個整數(shù),記作P(M,4)。讓我們研究一般地圖的這類函數(shù)的

性質(zhì)。當要研究時,讓我們將函數(shù)推廣到除 4以外的其他色數(shù),也就是研究函數(shù)

P(M,λ),即用λ種顏色給地圖M著色的方法數(shù)。([37],42—46頁)

1912年,伯克霍夫第一個定義了地圖的色多項式:“用λ種顏色對有n個區(qū)域的地圖M染色的方法數(shù)是關(guān)于λ的n次多項式P(λ),稱之為地圖的色多項式”([37],42頁)。此外,他還給出了一個表達式,但推導起來相當繁瑣。他還證明了色多項式的一個不等式[39]:P(λ)≥λ(λ-1)(λ-2)(λ -3)n-3,其中n≥3,λ≠4。他還把顏色數(shù)從 4擴展到一般整數(shù)λ,顯然是希望獲得對著色問題更為深刻的見解。

但是,伯克霍夫的色多項式是局限于地圖上的色多項式。20世紀 30年代初,惠特尼在伯克霍夫的指導下開始準備關(guān)于著色問題的博士論文。受伯克霍夫所提出的“定量方法”啟發(fā),惠特尼站在了一個更高的起點開始了自己的研究之路,那就是嘗試著將原先適用于地圖的色多項式延伸并推廣到一般的圖上。

雖然肯普早在 1879年就指出可考慮頂點著色,但是,在惠特尼的文章[13,14]發(fā)表以前,著色理論幾乎只是地圖的面著色,還沒有把一般圖 (graph)的著色問題提上日程。到1932年,惠特尼由于在《數(shù)學中的邏輯推廣》一文中,用M(λ)表示用λ種顏色對給定的圖進行著色的方法數(shù),并證明它是λ的多項式,從而把色多項式從地圖推廣到一般的圖上來,奠定了一般圖的色多項式理論的基礎(chǔ),大大拓展了一般圖的著色研究。([13],572—579)

惠特尼把著色多項式推廣到一般的圖上后,他又運用“邏輯推理”方法,導出了一個與伯克霍夫的色多項式類似的公式,且更加簡單:“

其中,mij(G)是秩為i、零維數(shù)為j的所有子圖的個數(shù)”([13],577頁)?；萏啬岱Q,這是他運用邏輯推理方法獨立得到的([13],576頁)。塔特后來把惠特尼的色多項式叫做惠特尼顯式([34],54頁)。

1932年,惠特尼發(fā)表了論文《圖的著色》([14],688—718頁)。在這篇文章中,他繼續(xù)研究色多項式,特別是對M(λ)的系數(shù)mij進行了更為詳細的討論,并給出了它的計算方法。他在第一部分首先介紹了mij,mi和M(λ)的基本性質(zhì),用圖的虛線圈 (broken circuit of the graph)表示mij。第二部分中,簡化了mij的計算。他寫道:

為得到mij,我們必須算出G的秩為i、零維數(shù)為j的所有子圖的個數(shù)。在這一部分我們將要證明沒有必要把所有這種子圖的總數(shù)都數(shù)出來,只須算出不可分離子圖的個數(shù)。([14],693—694頁)

換句話說,惠特尼意識到,用不著非要到所有子圖那么大的集合上去尋找秩為i、零維數(shù)為j的子圖,而只需要考慮其中的不可分離子圖就能得到mij。他還證明了,mij可以表示成關(guān)于不可分離子圖的數(shù)目N1,N2,…的多項式。顯然,數(shù)出不可分離子圖的個數(shù)要比直接計算mij容易得多。

惠特尼并不是為推廣而推廣。他在色多項式的研究中得到了四色猜想的一個強命題,所謂強命題即由這個命題成立就可以推出四色猜想成立。他的結(jié)論如下:

關(guān)于地圖四色猜想,我們提到下面的定理。如果G是一個平面圖,G′是它的對偶圖,分別對應(yīng)有數(shù)mij和m′ij,那么,

這可由文章N中對偶圖的定義立即得到①作者把下面這篇文章簡記作 N:“Non-separable and planar graphs”,Transactions of theAmericanM athematical Society,1932,34:339—362.?？紤]到圖G中有mij個秩為i、零維數(shù)為j的子圖,則上面給出的數(shù)m′ij也應(yīng)該是其對偶圖G′中的這類圖的數(shù)目相應(yīng)的一組數(shù)是m′ij,那么G中的這類圖就包含了所有的平面圖(見N,定理 29)。因此下面的命題必然蘊含四色定理:對于G的任意的上述這類圖，由于

上述這類圖中包含不可平面的圖,故這是地圖四色定理的一個強命題。([14],689頁)

此后,伯克霍夫②這時他研究的已是一般圖的色多項式,除此之外,包括第一篇色多項式的文章在內(nèi),他的色多項式研究都是針對地圖而言的。等人于 1946年也使用圖的色多項式給出了四色猜想的一個強命題([33],25頁;[38],355—451)。

色多項式曾一度被認為只能作為研究四色猜想的一種工具,但用它來攻克四色猜想?yún)s從未取得任何突破性進展。不過重要的是,現(xiàn)在它已在獨立地發(fā)展著。這源于惠特尼在色多項式理論上的工作,由此開始了色多項式理論的一般性研究,同時也開拓了圖的著色理論。1968年,瑞德(R.C.Read)發(fā)問,哪些多項式是某一個圖的色多項式[40],從此使色多項式研究再次活躍起來。這個問題至今未決。

惠特尼和瑞德以后,色多項式逐漸發(fā)展起來,其中一個發(fā)展方向是計算它的根。由于估計色多項式在λ=4處的值太困難了,于是人們就把它作為實函數(shù)甚至復函數(shù)來研究其函數(shù)性態(tài),特別是它的零點。這一方面是由塔特和波曼 (Gerald Berman)在 20世紀 60年代末共同推動的 ([31],548—550頁)。當(其中,即黃金分割比),|P(λ)|≤τ5-k,這里k為頂點數(shù)。由此觀之,P(λ)的值隨著頂點數(shù)的增多而趨于零。30多年過去了,這些結(jié)論對于四色猜想到底意味著什么直到今天仍然是四色猜想研究者所關(guān)注的課題。

色多項式的另一個重要方向就是通向了塔特-惠特尼多項式。塔特在研究完美拼方時經(jīng)常使用一個與“邊收縮”有關(guān)的圖的生成樹的遞推式。他說,“后來我就想知道是否還有其他類似于遞推公式的有趣的圖的函數(shù)”[41]。他在惠特尼的文章[13]中發(fā)現(xiàn)這樣一個遞推式,便將色多項式由一個色數(shù)變量推廣至兩個色數(shù)變量,得到了二色多項式([31],51—70、153—168頁),后人稱之為塔特多項式 (Tutte Polynominal)。當注意自己的二色多項式被稱為塔特多項式時,塔特寫道,“這可能對惠特尼不公平,他知道并使用了類似的系數(shù),而沒有麻煩地給它們附加上兩個變量”([41],7—8頁)。事實上,惠特尼于 1932年在《圖的著色》一文的腳注中,就曾提到一個歸功于福斯特 (R.M.Foster)的遞推式 ([14],718頁):

特別地,他還引入了惠特尼秩生成函數(shù)。這就是為什么塔特多項式也有塔特-惠特尼多項式之稱的原因。

塔特-惠特尼多項式在圖的計算中起著核心作用,它的重要作用源于它所包含的圖的信息。起初,這個多項式是作為同時推廣了圖著色和無處不為零-流的一個遞推式,隨著它的不斷發(fā)展,數(shù)學家發(fā)現(xiàn)它與數(shù)學的其他專業(yè)領(lǐng)域有著密切的聯(lián)系,特別是紐結(jié)理論和統(tǒng)計力學。組合學大師羅塔 (G-G.Rota,1932—1999頁)曾說,從馮·諾伊曼 (John von Neumann,1903—1957年)代數(shù)到紐結(jié)理論、辮子理論和統(tǒng)計力學,塔特多項式已經(jīng)變成它們所特有的理論[42]。塔特-惠特尼多項式在許多方面都有推廣[43],特別是它還能推廣到結(jié)構(gòu)更廣的擬陣上來。擬陣理論是惠特尼開創(chuàng)的一個新分支,這是惠特尼在圖論中的最大貢獻。

4 擬陣理論

擬陣理論是 20世紀數(shù)學的一門新興學科。與其他學科相結(jié)合是擬陣論的發(fā)展特征,比如擬陣與圖論、格論、代數(shù)、組合、幾何等分支的交叉滲透,使得擬陣理論有了許多生長點,從而不斷發(fā)展壯大。今天,擬陣在組合優(yōu)化、整數(shù)規(guī)劃、區(qū)組設(shè)計、橫貫理論、網(wǎng)絡(luò)流以及電網(wǎng)絡(luò)理論中都有著廣泛的應(yīng)用。

1935年,惠特尼試圖從理論上抓住“無關(guān)性 (independence)”②向量空間中線性無關(guān)性概念的推廣。概念的本質(zhì),而引入了擬陣,他的定義概括了驚人多樣的組合結(jié)構(gòu) ([19],509—533頁)。一個擬陣M是由有限個元素的集合E連同其上具有“無關(guān)性”結(jié)構(gòu)的子集族 ?構(gòu)成的一個二元系統(tǒng)(E,?)。這里,集合E可以是矩陣的列集或圖的邊集,也可以是其他任意具有類似“無關(guān)性”的數(shù)學對象的子集。作為擬陣的具體實例,可基于矩陣A的列集定義一個擬陣M:M是由A的列集和它的線性無關(guān)的列子集族組成的一個二元系統(tǒng)。換言之,若取A為域F上的m×n矩陣,則E是由A的n個列向量組成的集合,E中所有線性無關(guān)向量組構(gòu)成擬陣的獨立集族 ?;又如,從圖G的邊集出發(fā)也可以定義一個擬陣M(即圖擬陣):M是由G的邊集與不構(gòu)成圈的邊子集族組成的一個二元系統(tǒng),即,取E為圖G=(V,E)中的邊集E,?為E的不含圈的邊子集即可。從字源上看,擬陣 (matroid)源于矩陣 (matrix)。它是一種同時推廣了線性代數(shù)和圖論中無關(guān)性的統(tǒng)一化概念。由于這種類似“無關(guān)性”的概念在數(shù)學中普遍存在,導致擬陣有多達數(shù)十種形式迥異但本質(zhì)等價的公理系統(tǒng),這個特性是擬陣所獨有的。

擬陣的提出與四色猜想有著不解之緣。20世紀 30年代,四色猜想依然是圖論的核心問題。為攻克這一問題,惠特尼開始研究圖論,試圖從各個可能的角度尋找解決問題的突破口。他對圖論特別是平面圖及其對偶的研究催生了擬陣這一新理論。他在研究平面圖時曾證明一個著名的對偶定理[9,11]:一個圖是可平面的當且僅當它存在對偶 ([11],357頁)。有了這個漂亮的定理作判別準則,平面圖的研究也隨之更加深入。其中,有一類特殊的圖叫平面對偶圖,它是由一個平面圖派生出的平面圖。當一個可平面圖以不同的形式嵌入一個平面上時,其對偶圖往往不同構(gòu),但它們卻具有許多共同性質(zhì),并體現(xiàn)在不同對偶圖中那些不構(gòu)成回路的邊子集上?；萏啬岬膫ゴ笾幘驮谟谒⒁獾搅藞D中不構(gòu)成圈的邊子集與代數(shù)中線性無關(guān)性的相似性,于是就對這些相似性進行了抽象公理化,并定義為擬陣,從而開創(chuàng)并奠定了擬陣的基本理論。

惠特尼于 1935年發(fā)表的論文《關(guān)于線性相關(guān)性的抽象性質(zhì)》標志著擬陣論的誕生。全文結(jié)構(gòu)如下:引言 (§1);第Ⅰ部分 (§2—§9)“擬陣”,其中定義了擬陣的四種公理系統(tǒng),并論證了它們的等價性;第Ⅱ部分 (§10—§11)“可分離性和對偶”,這一部分主要將《不可分離圖和可平面圖》的大部分理論推廣到了擬陣;第Ⅲ部分 (§12—§16)“矩陣和擬陣”,研究了二者的關(guān)系;最后是附錄,“模 2的整數(shù)矩陣”,主要刻畫了二元擬陣的特征。

惠特尼定義的擬陣是建立在矩陣列子集之間無關(guān)性的基礎(chǔ)上的:

令C1,C2,…,Cn為矩陣M的列,任意一組列子集或者線性無關(guān),或者線性相關(guān),從而這些子集可劃分為兩類,但這些類并非任意,例如必須滿足下面兩個法則:

(a)一個無關(guān)集的任意子集是無關(guān)的。

(b)如果Np和Np+1分別是p個列和p+1個列的無關(guān)集,則Np加上Np+1中的某個列構(gòu)成一p+1個列的無關(guān)集。

由于我們在 §16給出了一個系統(tǒng)的例子,它滿足這兩個法則但不代表任何一個矩陣。所以,存在由這兩個法則不可推論的其他一些法則,然而卻又很難找到另外的法則。我們就把滿足(a)和(b)的一個系統(tǒng)叫做“擬陣”。([19],509頁)

不難看出,惠特尼認為這種類似于矩陣但又不僅僅是矩陣的系統(tǒng)是一種新的數(shù)學對象,將其命名為“擬陣”。這不僅印證了擬陣的名稱確實源于“矩陣”,同時說明了惠特尼的創(chuàng)新思想。

如何刻畫一個擬陣呢?惠特尼的基本思想就是推廣。一旦忘掉線性無關(guān)性的具體的外在表象,只記住哪些子集線性無關(guān),就得到了他的獨立集公理系統(tǒng)。所謂“獨立”,即線性無關(guān)概念的推廣。正像群的抽象概念一樣,擬陣也是為了用一個統(tǒng)一的概念把握具體對象及其所具有的“獨立”性質(zhì),且預(yù)先包括可能尚未發(fā)現(xiàn)的更大范圍的對象,故需要以高度抽象的形式來表述它的基本概念。這種思想正是由惠特尼通過把滿足下列條件的數(shù)學對象的集合叫做擬陣來實現(xiàn)的。集合M中的數(shù)學對象具體是什么并不重要,重要的是“對于M的任意子集N,它們或者“獨立”,或者“不獨立”,但必須滿足下面兩個公設(shè):

(I1)一個獨立集的任意子集是獨立的。

(I2)如果N=e1+…+ep,N′=e′1+…+e′p+1,分別是獨立的,那么對于某個i,e′i,不在N中,N+e′i是獨立的?！?[19],513頁 )

這就是擬陣的獨立集公理系統(tǒng)。顯然在這個抽象系統(tǒng)下,絲毫沒有確定擬陣的具體的“物質(zhì)”形態(tài)。所以,擬陣本質(zhì)上是一個定義了某種“獨立結(jié)構(gòu)”的抽象的公理系統(tǒng)。

惠特尼由于洞察了擬陣隱匿形態(tài)下的本質(zhì)特征——抽象的線性無關(guān)性,所以他并沒有停留在從“矩陣”得到“擬陣”的定義方法,他說,“可以等價地考慮歐氏空間中的點或向量,甚至是多項式等來取替矩陣的列”([19],509頁)。這句話表達了他對擬陣公理系統(tǒng)多樣性特征的深刻理解。這些思想形成了《關(guān)于線性相關(guān)性的抽象性質(zhì)》第Ⅰ部分的主要內(nèi)容。除獨立集公理系統(tǒng)外,他還基于秩函數(shù)、基和圈等概念定義了擬陣,并論證了它們的等價性。文中是按照如下順序進行論證的[44]:

定義了擬陣的公理系統(tǒng)以后,在前期圖論工作的基礎(chǔ)上,惠特尼便開始應(yīng)用圖的理論來建立他的擬陣理論。他指出,這篇關(guān)于擬陣論的文章與他的《不可分離圖和可平面圖》有著緊密聯(lián)系:……從理論上講,雖然圖是擬陣的一類很小的子類 (見附錄),但是,很多圖特別是不可分離圖和對偶圖的簡單定理,也適用于擬陣。這就是為什么把圖論中的各種術(shù)語延用到擬陣理論的原因。值得注意的是,由于擬陣代表矩陣,所以,對偶擬陣有簡單的幾何表示,這與圖相比有很大不同。([19],509頁)

具體地,惠特尼主要從以下幾方面奠定了擬陣的基本理論:

4.1 擬陣的連通

在刻畫了擬陣的公理系統(tǒng)后,惠特尼下一步是研究擬陣的基本性質(zhì):不可分離劃分和對偶。我們知道,將大的目標對象分解成較小的、易于理解的部件,是數(shù)學中一個普遍的技術(shù)。對于擬陣,第一個這樣的分解結(jié)論是由惠特尼給出的 ([19],519頁),當他證明,每一個擬陣均可唯一地寫成其連通分支的直和形式的時候,就預(yù)示了擬陣分解理論的開始,其中重要的方法是擬陣的連通。

擬陣的連通是擬陣奠基之作《關(guān)于線性相關(guān)性的抽象性質(zhì)》[19]第Ⅱ部分 (§10—§11)的主要內(nèi)容之一?；仡櫼幌?惠特尼曾在引言中提到:這一部分可以取代文獻[11]的大量內(nèi)容。他把不可分圖和平面圖的大部分結(jié)論推廣到了擬陣。然而,由于擬陣中沒有與圖的頂點相對應(yīng)的概念,因此,也就不存在與通常的圖連通相對應(yīng)的性質(zhì),即一般的圖連通度無法在其圈擬陣中表現(xiàn)出來,但圖的 2-連通性可以在擬陣中得到合理的推廣。自然地,如果把由秩函數(shù)刻畫的圖的不可分離劃分,推廣到擬陣的不可分離劃分 (即連通),那么擬陣的不可分離劃分就對應(yīng)于圖的 2-連通。這些思想體現(xiàn)了惠特尼的非凡創(chuàng)造力。由于一個圖不可分離劃分的充分必要條件是不存在這樣一種分割:它將圖分成H1和H2兩部分(H1、H2均至少含有一邊)且R=R1+R2。因此,惠特尼定義,如果分M的元素成兩類M1和M2(都至少包含一個元素),且r(M)=r(M1)+r(M2),則稱M是分離的;否則,M不可分離(即連通)([19],518—519頁)。從此擬陣連通的理論得到了很大的發(fā)展,特別是塔特后來成功地引進擬陣高階連通度的概念之后([31],497—522頁),擬陣的連通成為研究擬陣結(jié)構(gòu)的一個重要工具。

惠特尼接著用歸納法給出了連通(不可分離劃分)擬陣的構(gòu)造方法。任意不可分離劃分擬陣M(零化度n>0)可由下面方法構(gòu)造:取一個圈M1,添加一系列元素使之與M1中 1個或多個元素形成一個圈,此時構(gòu)成一個零化度為 2(若n(M)>1)的不可分離擬陣;重復上述過程直至Mn=M([19],520頁)。這個結(jié)論連同惠特尼關(guān)于不可分圖的構(gòu)造定理 ([11],350頁),成為塔特成功構(gòu)造 3-連通圖和 3-連通擬陣的先導 ([44],16頁)。最后惠特尼用秩、圈的術(shù)語刻畫了擬陣連通分支的基本性質(zhì)。

4.2 對偶擬陣

對偶擬陣是擬陣理論中最基本最重要的概念之一?；萏啬嵩?§11中定義了對偶擬陣:

假設(shè)在擬陣M與M′的元素之間存在一個 1-1映射,若N是M的任一子陣,N′是N在M′中對應(yīng)擬陣的余補,且r(N′)=r(M′)-n(N),則M′為M的對偶。([19],521—522頁)

對偶性概念的提出使得擬陣理論沒有停留在對線性無關(guān)性的單純抽象的水平上。同時對偶擬陣的概念也推廣了許多在其他數(shù)學問題上出現(xiàn)的“對偶”結(jié)構(gòu),如圖論中的平面圖和平面圖的幾何對偶,及內(nèi)積線性空間中子空間和子空間的正交補空間。像其他代數(shù)結(jié)構(gòu)一樣,擬陣理論中也有許多從已知擬陣得到新擬陣的方法,對偶擬陣被認為是最基本的方法之一。然而,與圖論不同,圖論中只有平面圖才有對偶,對于擬陣而言,惠特尼證明,每一個擬陣都存在對偶擬陣,且M＊＊=(M＊)=M([19],522頁)。如此完整的對稱性是擬陣特有的一個重要性質(zhì)。這一特性在將擬陣應(yīng)用到組合優(yōu)化的理論時尤為重要。羅塔在談到擬陣的對偶時說,當圖不可平面時,擬陣扮演了其對偶的角色 ([44],9頁)。圖的任何不用“頂點”刻畫的性質(zhì)幾乎都存在擬陣的類似物,對這一特性的最深刻洞察是后來塔特的同倫定理[45]。

4.3 擬陣的表示問題

惠特尼在第Ⅲ部分研究了矩陣列向量的擬陣結(jié)構(gòu)。一個域 (這里是實數(shù)域,但這個假設(shè)是不必要的)上的m×n矩陣伴隨有兩種結(jié)構(gòu)。一個是列擬陣,由列向量的線性獨立所定義的n元擬陣;一個是行向量空間,由行向量生成的m-維子空間。他還進一步給出了這兩種結(jié)構(gòu)之間的關(guān)系,即d維子空間確定唯一一個秩為d的擬陣([19],526頁)。

惠特尼關(guān)于列擬陣的對偶的一個主要結(jié)論是,如果H′是子空間H的正交子空間(相對于通常的內(nèi)積 =∑xiyi),那么,H′確定的擬陣與H確定的擬陣互為對偶擬陣([19],526頁)。這個定理蘊含了線性規(guī)劃中的原規(guī)劃與對偶規(guī)劃關(guān)系的幾何本質(zhì),如多面體與它的蓋爾變換,以及線性糾錯碼與它的對偶碼。

在附錄部分,惠特尼特別地給出了僅在特征為 2的域上可以表示成列擬陣的一個重要例子,即著名的 Fano平面①法諾(Gino Fano,1871—1952年)是意大利數(shù)學家,研究領(lǐng)域為射影幾何和代數(shù)幾何。法諾平面 (Fano plane)以他的名字命名。。他的目的是刻畫二元擬陣 (即在二元有限域上可表示的擬陣)的特征,這或許正與他在引言中的那句話相呼應(yīng),“完全刻畫可矩陣表示的擬陣仍是一個有待進一步解決的問題”([19],509頁)。實質(zhì)上,這一問題最早在擬陣中引入了更廣泛的可表示性概念,擬陣的可表示性是擬陣理論中的熱門課題之一,并且這個問題至今還沒有徹底解決[46]。

另外,惠特尼的問題所涉及的是實數(shù)集合上的表示,他舉例說明了不存在矩陣表示的擬陣,即 Fano擬陣F7,而F7在GF(2)可表示。這個問題的一般形式,即確定域F并刻畫F可表示的一類擬陣的特征,大大豐富了擬陣的表示問題。這一理論后來由于塔特的工作迅速發(fā)展起來。

綜上,惠特尼不僅引入了擬陣而且使之形成了數(shù)學的一門分支。筆者認為擬陣在理論和應(yīng)用方面獲得迅速發(fā)展,與圖論、格論及組合優(yōu)化的交叉融合是分不開的。其一,圖論尤其是平面圖及其對偶的研究刺激著擬陣理論的發(fā)展。20世紀 60年代,塔特發(fā)表了《關(guān)于擬陣的演講》一文,把擬陣和圖論充分結(jié)合起來并做了大量工作,從而使擬陣論得到了長足的發(fā)展([31],439—496頁)。其二,由于有限幾何格本質(zhì)上就是擬陣,擬陣和格論的結(jié)合,形成了擬陣發(fā)展的另一個重要方向。伯克霍夫[47]、麥克萊恩 (S.Mac Lane,1909—2005)[48,49]和狄厄沃斯 (R.P.Dilworth,1914—1993年)[50]等人從格論和幾何觀點對擬陣進行了研究。擬陣發(fā)展的第三個重要方向是擬陣和組合優(yōu)化的結(jié)合。特別是在埃德蒙 (J.Edmonds)、福爾克森 (D.R.Fulkerson,1924—1976年)[51]、明蒂 (G.J.Minty)[52]等人把圖論算法推廣到擬陣之后,從此擬陣獲得了更為廣泛的應(yīng)用空間。

科學的發(fā)展具有繼承性,數(shù)學也不例外?；萏啬崴鶆?chuàng)造的數(shù)學理論對后人來說不啻是一種寶貴的數(shù)學財富。他雖未成功解決四色猜想,但在尋求解答的過程中所提出的一些概念、定理及方法是很深刻的,在圖論和擬陣后來發(fā)展中被經(jīng)常地使用,為相關(guān)理論研究提供了概念和方法基礎(chǔ)。隨著圖論的進一步發(fā)展,他涉獵的相關(guān)理論也迅速發(fā)展起來。20世紀 30年代以前,可平面圖、平面圖的哈密頓回路問題、色多項式還是冷門,少人問津,更為大多數(shù)以研究四色猜想等經(jīng)典問題為主的數(shù)學家所輕視。但是,繼惠特尼之后,這些由傳統(tǒng)的四色猜想導出的理論問題都大放異彩,成為圖論的核心部分。從圖論中開創(chuàng)擬陣論,把圖的一些概念和理論推廣到擬陣中來,并提出了擬陣論自身的問題,從而奠定了擬陣的理論基礎(chǔ)。20世紀 60年代以后,獲得長足發(fā)展的擬陣論在很大程度上是按照惠特尼的思想展開的。這毫不奇怪:他引入的擬陣概念,能夠觸及相關(guān)問題的基本結(jié)構(gòu)和概念:一方面使我們對“無關(guān)性”有更為純正的認識,揭示了不同數(shù)學領(lǐng)域之間的一種聯(lián)系;另一方面它也包含了無法列入以往理論中的新的研究對象。在研究這些理論的同時,他還論述到圖的分類問題,他也是較早討論圖的拓撲不變量的數(shù)學家之一?？傊?惠特尼對圖論乃至擬陣論做出了開拓和奠基性的貢獻,并為其后來的發(fā)展開辟了廣闊的前景。

這些成就的取得與惠特尼進行學術(shù)研究的風格不無關(guān)系。他進行數(shù)學研究的一個主要特征就是“探索現(xiàn)象內(nèi)在的原因”(search the inner reasons for phenomena,簡寫為 SI R):從所有可能的角度研究問題的情況,設(shè)想,再嘗試 ([2],309—310頁)。筆者認為,他的圖論工作源于將這種思維方式用于研究四色猜想,這些圖論工作又誘導了他對線性無關(guān)的抽象研究和擬陣論的創(chuàng)立。這充分體現(xiàn)了他對數(shù)學本質(zhì)意義與方法的深刻理解,同時也奠定了他后來研究拓撲學及其他領(lǐng)域的方法論基礎(chǔ)。此外,在他早期的圖論工作中就滲透著拓撲學的思想,這表現(xiàn)在他能借用拓撲學中的術(shù)語定義圖的一些概念。因為從總體上考察一個圖,并不要求精細入微,而是關(guān)注它的宏觀性質(zhì),所以,這門從大范圍、整體上著眼的數(shù)學分支反過來有助于他探索問題的本質(zhì)原因。這種拓撲學的思維方式,不僅對他取得圖論上的一些成就大有裨益,而且也為他后來轉(zhuǎn)向拓撲學領(lǐng)域埋下了伏筆。

惠特尼的學術(shù)興趣極其廣泛,且喜歡研究尚未發(fā)展起來的學科,并探索散布在不同理論中的聯(lián)系。確實,他并沒有在圖論這塊領(lǐng)域長期停留,而是繼續(xù)大踏步前進。如果說,從 1929年博士入學到 1935年他由擬陣為“跳板”離開圖論,算作他研究圖論的時間,也就短短 6年,但他的貢獻卻不可估量!同時,他喜歡獨創(chuàng)、擅長引入新概念以及建立新理論的學術(shù)才華也展現(xiàn)得淋漓盡致。1935年以后,惠特尼的興趣就轉(zhuǎn)向了拓撲學。那時,拓撲學的中心才開始移向美國。拓撲學是他做出最大貢獻的一門學科。大約 40年后,他又以兩篇四色猜想的文章回到圖論作了“短暫逗留”:一篇未發(fā)表的手稿,討論了四色問題的約化術(shù)[53];一篇是以合作者的身份發(fā)表的,其中指出了計算機在檢驗圖的可約性時出現(xiàn)的一個錯誤[54]。此后,惠特尼又繼續(xù)研究他的拓撲學,成為拓撲學的一代宗師。晚年的他,興趣完全轉(zhuǎn)向了數(shù)學教育?；萏啬嵊捎谪暙I非凡,獲得了很多榮譽。1945年他被當選為美國科學院院士,1976年被授予美國國家科學獎?wù)?1982年獲沃爾夫獎,1985年以其一生成就獲美國數(shù)學會斯蒂爾 (Leroy P.Steele)獎。

1 Whitney H.Collected Papers[C].Eells J,Toledo D(Eds).Boston:Birkhauser,1992.1—185.

2 Graw-hillM.Morden Scientists and Engineers[C].New York:St.Louis,San Francisco,1980.309—310.

3 胡作玄.惠特尼[A].世界著名數(shù)學家傳記 [M].下冊.北京:科學出版社,1995.1637—1646.

4 Wen-tsunWu.Selected works of W en Tsun W u[C].World Scientific,2008.

5 Whitney H.Moscow 1935:TopologyMoving TowardAmerica[A].Duren PL(Eds).A Century ofM athemAtics in America[M],Part I.Amer.Math,1985.96—117.

6 Tait P G.On the colouring ofmaps[J].Proc.Roy.Soc.Edinb,1878—1880,10:501—503.

7 Appel K,HakenW.Every PlanarMap is Four Colorable,PartⅠ, Ⅱ [J].Illinois J.Math,1977,21:429—567.

8 Whiney H.The Coloring of Graphs[J].Proc.Nat.Acad.Sci.USA,1931,17:122—125.

9 Whitney H.Non-separable and Planar Graphs[J].Proc.Nat.Acad.Sci.USA,1931,17:125—127.

10 Whitney H.A Theorem on Graphs[J].Annals of M ath,1931,32(2):378—390.

11 Whitney H.Non-separable and Planar Graphs[J].AMS Transac,1932,34:339—362.

12 Whitney H.Congruent Graphs and the Connectivity of Graphs[J].Amer.J.M ath,1932,54:150—168.

13 Whitney H.A Logical Expansion inMathematics[J].AMS Bull,1932,38:572—579.

14 Whitney H.The Coloring of Graphs[J].Annals of Math,1932,33:688—718.

15 Whitney H.A Set of Topological Invariants for Graphs[J].Amer.J.Math,1933,55:231—235.

16 Whitney H.On the Classification of Graphs[J].Amer.J.M ath,1933,55:236—244.

17 Whitney H.2-isomorphic Graphs[J].Amer.J.M ath,1933,55:245—254.

18 Whitney H.Planar Graphs[J].Fund.M ath,1933,21:73—84.

19 Whitney H.On the Abstract Properties ofLinearDependence[J].Amer.J.Math,1935,57:509—533.

20 Gross J L,Yellen J.Handbook of Graph Theory[C].Florida:CRC Press,2003.

21 Bondy J A,MurtyU S R.Graph Theory[M].Springer,2008.

22 Chartrand G,Ping Zhang.Chromatic Graph Theory[M].Boca Raton,London,New York:CRC Press,2009.

23 Veblen O.Theory on Plane Curves in Non-metricalAnalysis Situs[J].Trans.AMS,1905,6:83—98.

24 Kuratowski C.SurLes Problèmes des Courbes Gauches en Topologie[J].Fundamenta M ath,1930,15:271—283.

25 K?nigD.Uber Graphen und ihre Anwendung auf Deter minantentheorie und Mengenlehre[J].Math.Ann,1916,77:453—465.

26 BiggsN L,Lloyd E K,W ilson R J.Graph Theory1736—1936[M].Oxford:Clarendon Press,1986.134.

27 Kempe A B.On the Geographical Problem of the Four Colours[J].Amer.J.M ath,1879,(2):193—200.

28 Sarkaria K S.The TopologicalWork of Henri Poincaré[A].James IM(Eds).History of Topology[C].1th.OxfordUniversity,UK:Elsevier,1999.123—139.

29 Thomassen C.Embeddings of Graphs with no Short Noncontractible Cycles[J].J.Combin.Theory Ser.B,1990,48:155—177.

30 Mac Lane S.A Combinatorial Condition for Planar Graphs[J].Fund.Math.Ann,1937,191:21—28.

31 TutteW T.Selected papers ofW.T.Tutte[C].McCarthyD,Stanton R G(Eds).Pierre,Manitoba,Canada:The Charles Babbage Research Centre,1979.360—388.

32 Ore O.The Four Color Problem[M].London:Academic Press,1967.68—74.

33 Saaty TL.Thirteen ColorfulVariations on Guthrie's Four-color Conjecture[J].Amer.Math.Month,1972,79:2—43.

34 TutteW T.Graph Theory As I Have Known It[M].Oxford:Clarendon press,1998.

35 Grinberg E J.Plane Homogeneous Graphs of Degree Three W ithout Ham iltonian Circuits(Russian.Latvian and English summaries)[M].LatvianMath.Yearbook 4.1968.51—58.

36 Barnette D.Conjecture 5[A].TutteW T(Eds).Recent Progress in Combinatorics[C].New York:Academic Press,1969.343.

37 Birkhoff GD.A Determinantal Formula for the NumberofWaysof Colouring aMap[J].Annals ofM ath,1912,14(2):42—46.

38 Birkhoff GD,LewisD C.Chromatic Polynomials[J].Trans.Amer.M ath.Soc,1946,60:355—451.

39 W ilson R.FourColors Suffice:How TheMap Problem was Solved[M].Princeton andOxford:PrincetonUniverstiy Press,2002.164—168.

40 Read R C.An Introduciton to Chromatic Polynomials[J].Journal of Combinatorial Theory,1968,4:52—71.

41 TutteW T.Graph-polynomials[J].Advances in Applied M athematics,2004,32(1—2):5—9.

42 Rota G.Report on the Present State of Combinatorics[J].DiscreteM ath,1996,153:289—303.

43 Farr G E.Tutte-Whitney Polynomials:Some History and Generalizations[A].Grimmett G R,Mcdiarmid C J H(Eds).Combinatorics,Complexity and Chance:A Tribute toDom inicW elsh[C].Oxford:Oxford University Press.2007.28—52.

44 Kung J P S.A Source Book in M atroid Theory[M].Boston,Basel,Stuttgart:Birkhuser,1986.16.

45 TutteW T.A Homotopy Theorem forMatroids,I,II[J].Trans.Amer.M ath.Soc,1958,88:144—174.

46 Whittle G.RecentWork inMatroid Representation Theory[J].DiscreteMath,2005,302(1—3):285—296.

47 Birkhoff G.AbstractLinearDependence in Lattices[J].Amer.J.M ath,1935,57:800—804.

48 Maclane S.Some Interpretations of Abstract Linear Dependence in Terms of Projective Geometry[J].Amer.J.M ath,1936,58:236—240.

49 Mac Lane SM.A Lattice Formulation for Transcendence Degrees and P-bases[J].DukeM ath.J,1938,4:455—468.

50 Dilworth R P.Dependence Relations in a SemimodularLattice[J].DukeM ath.J,1994,11:575—587.

51 Edmonds J,Fulkerson D R.Matroids and the greedy algorithm[J].M ath Programm ing,1971,1:127—136.

52 Minty G J.The Rank For muia ofNash-W illiams as a Source of Covering and Paking Theorems[J].J.M ath AnalysisAppl,1973,4:328—347.

53 Whitney H.On Reducibility in the FourColor Problem[A].UnpublishedManuscript.1971.EellsJ,ToledoD.(Eds).Collected papers[C].Boston,Basel,Berlin:Birkhauser,1992.179—184.

54 Whitney H.,TutteW T.Kempe Chains and the Four Color Problem[J].UtilitasM athematica,1972,2:241—281.