一個最短網(wǎng)絡(luò)的猜想——攻克斯坦納比難題

為了汲取西方新的知識,堵丁柱研究員1990年2月到美國普林斯頓大學(xué)作訪問學(xué)者。才一個多月,即4月10日,他就和美國貝爾實驗室黃光明研究員合作攻克了吉爾伯特--波雷克猜想,即斯坦納比難題。所以堵丁柱研究員說,這個結(jié)果是在國外做完的,但是大量研究工作實際是在國內(nèi)做的。

1990年10月正式公布以后,沒想到會引起國際數(shù)學(xué)界那樣廣泛注意和強烈反響,被列為1989年-1990年度美國離散數(shù)學(xué)界和理論計算機科學(xué)界重大成果。英國大百科全書在收錄這一成果時也評價說:“在過去的一年里,數(shù)學(xué)上最顯著的進展包括長期、著名的猜想--一個最短網(wǎng)絡(luò)的猜想……這個猜想就是斯坦納比問題! 


什么是斯坦納比問題呢?假設(shè)我們在北京、上海、西安三城市之間架設(shè)電話線,一種辦法是分別聯(lián)通北京--上海和北京--西安。另一種辦法是選第四個點,假設(shè)鄭州。由此分別向三城市架線,可能你不會想到第二種辦法所用的電話線只是第一種辦法的86.6%,即可取得比第一種辦法節(jié)約13%的顯著經(jīng)濟效益。這就是離散數(shù)學(xué)界30年代提出的著名的斯坦納比問題,但一直未能得到證明。直到1967年大名鼎鼎的貝爾電話公司,遇上了一家精明的用戶航空公司,竟被戳了一個大窟窿。這家用戶要求在第四個點的位置上架上電話線。這樣使得電話公司不僅要拉新線,增加服務(wù)網(wǎng)點,而且要減少收費。這件事的連鎖反應(yīng)迫使電話公司改變了堅持長達10年按照最少發(fā)生樹長度收費的原則,并且不得不對最短網(wǎng)絡(luò)問題進行研究。于是,貝爾實驗室數(shù)學(xué)中心主任波雷克和研究員吉爾伯特對斯坦納比問題作了許多研究,根據(jù)自己多年研究所得提出如下猜想:對歐氏平面上的任何有限點集,其最小的Steiner樹同最小發(fā)生樹的長度之比(稱為Steiner比,即斯坦納比)不小于√3/2。換言之,正三角形加點可以節(jié)省最多。但他們自己并沒有能證明它。 

由于其在運輸、通信和計算機等現(xiàn)代經(jīng)濟與科技中的重要作用,近幾十年來它的研究進展越來越快。1985年,格拉姆和金芳容借助于計算機進行了大量運算,證明了斯坦納比大于0.824,雖距0.866不遙遠,卻始終未能達到最終目標。美國數(shù)學(xué)會主席曾感嘆道:“這問題已經(jīng)公開了22年,這件事總令你不安,你不能證明這樣初級的東西!币苍S源于猜想提出的戲劇性背景,也許源于理論意義以及貝爾實驗室的學(xué)術(shù)權(quán)威,也許源于數(shù)學(xué)家對形成初等而又難解問題的愛好,人們對這個問題的研究歷久不衰。

1990年,41歲的堵丁柱因為攻克這一問題而成為世界數(shù)學(xué)界冒出的奇葩。他與貝爾實驗室黃光明研究員合作,找到了一個全新途徑,給出了吉爾伯特-波雷克猜想完整的證明。證明的核心是關(guān)于鞍點的一個定理。其主要思想是,首先在歐氏平面含n點的集合與2n-3維空間的點之間建立一一對應(yīng)的關(guān)系,使得猜想可以化為2n-3維空間上函數(shù)的極值問題。然后利用鞍點定理找出可以達到極值的臨界點應(yīng)滿足的必要條件。之后,再將此條件轉(zhuǎn)換為臨界點對應(yīng)的點集上的幾何性質(zhì)。最后,利用這幾何性質(zhì)確定幾何結(jié)構(gòu),驗證該猜想。一個重要的注釋是,為獲得較易驗證的幾何結(jié)構(gòu),他們將猜想先轉(zhuǎn)換為一個較強的形式,然后再如上法炮制。 

證明于1990年10月在會議上正式公開,《紐約時報》立刻做了報道。接著《科學(xué)》雜志、《科學(xué)新聞》《新科學(xué)論》《SLAM新聞》等報刊上出現(xiàn)了許多報道。值得提及的《SLAM新聞》在頭版上用了個有趣的“在計算機時代歐氏幾何的歐氏平面上n點的集合←→2n-3維空間的點力與運氣”。在《不列顛百科全書1992年鑒》中,該證明進一步被列為入選的6項數(shù)學(xué)成果的第一項。因此,堵丁柱也榮獲了中國科學(xué)院自然科學(xué)一等獎、國家科技進步二等獎和中國青年科學(xué)家獎等殊榮。

Stewart教授對證明的意義作了闡述。

12年前曾當(dāng)過堵丁柱的老師,12年后又配合堵丁柱攻克斯坦納比難題的貝爾實驗室研究員黃光明在興奮之余撰文記述了研究過程。他幽默地寫道:“如果要等我證出0.866的猜想才退休,那我可能要在貝爾實驗室過百歲生日了。解決這一問題的關(guān)鍵也許不在時間而在人,我能做的貢獻是找到一個比我強的人來作此問題。我找到了堵丁柱,而堵丁柱今年四月找到了答案!

每個成功者的背后,都會留下奮斗的足跡。探索一下堵丁柱的成才之路,或許對今天的青年朋友有所啟迪。