王獻(xiàn)芬

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

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

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

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

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

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

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

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

(2)一些文章主要研究平面圖的哈密頓回路問(wèn)題[10,12]。惠特尼得到了四色猜想的一個(gè)等價(jià)命題,他的工作引導(dǎo)了一般意義上平面圖哈密頓回路問(wèn)題的研究。

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

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

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

1 可平面圖

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

實(shí)際上,在庫(kù)拉托夫斯基證明他的著名定理以前,人們認(rèn)為可平面圖的概念可以通過(guò)一些組合的而非拓?fù)涞男再|(zhì)來(lái)刻畫(huà)。柯尼希 (D.K?nig,1884—1944年)早在 1916年就斷言,四色猜想的進(jìn)展可能依賴于平面圖的這種刻畫(huà)[25]。盡管這個(gè)著名猜想對(duì)于庫(kù)拉托夫斯基的發(fā)現(xiàn)并無(wú)幫助,但沒(méi)過(guò)多久,它卻間接地啟發(fā)了另一位數(shù)學(xué)家的思想,這位數(shù)學(xué)家就是惠特尼。

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

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

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

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

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

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

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

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

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

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

2 平面圖的哈密頓回路問(wèn)題

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

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

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

1931年,惠特尼發(fā)表了第一篇圖論文章,題為“圖的一個(gè)定理”,該文于 1930年 2月22日提交給美國(guó)數(shù)學(xué)會(huì),刊于《數(shù)學(xué)年刊》[10]。惠特尼在開(kāi)篇的引言中就陳述了基本定理:

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

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

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

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

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

進(jìn)而他又證明,

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

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

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

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

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

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

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

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

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

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

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

3 色多項(xiàng)式

色多項(xiàng)式是現(xiàn)代圖論的一個(gè)核心概念,是代數(shù)圖論中一個(gè)重要結(jié)構(gòu),而且由此產(chǎn)生了圖著色的重要分支。色多項(xiàng)式是一個(gè)關(guān)于色數(shù)的函數(shù),用來(lái)計(jì)算圖著色的數(shù)目。它是由伯克霍夫?yàn)檠芯克纳孪胗?1912年[37]最早提出的,后來(lái)由惠特尼和塔特推廣到了塔特-惠特尼多項(xiàng)式。

伯克霍夫曾把人們關(guān)于四色猜想的研究方法分成兩類:“定性方法”和“定量方法”[38]?！岸ㄐ苑椒ā?即假定比地圖M面數(shù)少的所有地圖均可四色,再?gòu)牡玫降男畔⒅型茢郙也可四色。他認(rèn)為,色多項(xiàng)式以前,四色猜想的研究主要集中于“定性方法”。色多項(xiàng)式是作為研究四色猜想的一種“定量方法”而引入的:

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

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

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

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

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

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

惠特尼把著色多項(xiàng)式推廣到一般的圖上后,他又運(yùn)用“邏輯推理”方法,導(dǎo)出了一個(gè)與伯克霍夫的色多項(xiàng)式類似的公式,且更加簡(jiǎn)單:“

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 擬陣?yán)碚?/h2>

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

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

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

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

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

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

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

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

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

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

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

(I1)一個(gè)獨(dú)立集的任意子集是獨(dú)立的。

(I2)如果N=e1+…+ep,N′=e′1+…+e′p+1,分別是獨(dú)立的,那么對(duì)于某個(gè)i,e′i,不在N中,N+e′i是獨(dú)立的。”([19],513頁(yè) )

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

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

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

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

4.1 擬陣的連通

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

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

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

4.2 對(duì)偶擬陣

對(duì)偶擬陣是擬陣?yán)碚撝凶罨咀钪匾母拍钪??；萏啬嵩?§11中定義了對(duì)偶擬陣:

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

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

4.3 擬陣的表示問(wèn)題

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

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

在附錄部分,惠特尼特別地給出了僅在特征為 2的域上可以表示成列擬陣的一個(gè)重要例子,即著名的 Fano平面①法諾(Gino Fano,1871—1952年)是意大利數(shù)學(xué)家,研究領(lǐng)域?yàn)樯溆皫缀魏痛鷶?shù)幾何。法諾平面 (Fano plane)以他的名字命名。。他的目的是刻畫(huà)二元擬陣 (即在二元有限域上可表示的擬陣)的特征,這或許正與他在引言中的那句話相呼應(yīng),“完全刻畫(huà)可矩陣表示的擬陣仍是一個(gè)有待進(jìn)一步解決的問(wèn)題”([19],509頁(yè))。實(shí)質(zhì)上,這一問(wèn)題最早在擬陣中引入了更廣泛的可表示性概念,擬陣的可表示性是擬陣?yán)碚撝械臒衢T課題之一,并且這個(gè)問(wèn)題至今還沒(méi)有徹底解決[46]。

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

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

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

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

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

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ù)學(xué)家傳記 [M].下冊(cè).北京:科學(xué)出版社,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.