斯坦納比難題

為了汲取西方新的知識，堵丁柱研究員1990年2月再次出國，在美國普林斯頓大學作訪問學者。才一個多月，即4月10日，他就和美國貝爾實驗室黃光明研究員合作攻克了吉爾伯特--波雷克猜想，即斯坦納比難題。所以堵丁柱研究員說，這個結果是在國外做完的，但是大量研究工作實際是在國內做的。1990年10月正式公布以後，沒想到會引起國際數學界那樣廣泛注意和強烈反響，被列為1989年-1990年度美國離散數學界和理論計算機科學界重大成果。英國大百科全書在收錄這一成果時也評價說：“在過去的一年裡，數學上最顯著的進展包括長期、著名的猜想--一個最短網路的猜想……這個猜想就是斯坦納比問題。”
什麼是斯坦納比問題呢？假設我們在北京、上海、西安三城市之間架設電話線，一種辦法是分別聯通北京--上海和北京--西安。另一種辦法是選第四個點，假設鄭州。由此分別向三城市架線，可能你不會想到第二種辦法所用的電話線只是第一種辦法的86.6%，即可取得比第一種辦法節約13%的顯著經濟效益。這就是離散數學界30年代提出的著名的斯坦納比問題，但一直未能得到證明。直到1967年大名鼎鼎的貝爾電話公司，遇上了一家精明的用戶航空公司，竟被戳了一個大窟窿。這家用戶要求在第四個點的位置上架上電話線。這樣使得電話公司不僅要拉新線，增加服務網點，而且要減少收費。這件事的連鎖反應迫使電話公司改變了堅持長達10年按照最少發生樹長度收費的原則，並且不得不對最短網路問題進行研究。於是，貝爾實驗室數學中心主任波雷克和研究員吉爾伯特對斯坦納比問題作了許多研究，根據自己多年研究所得提出如下猜想：對歐氏平面上的任何有限點集，其最小的steiner樹同最小發生樹的長度之比(稱為Steiner比，即斯坦納比)不小於√3/2。換言之，正三角形加點可以節省最多。但他們自己並沒有能證明它。
由於其在運輸、通信和計算機等現代經濟與科技中的重要作用，近幾十年來它的研究進展越來越快。1985年，格拉姆和金芳容藉助於計算機進行了大量運算，證明了斯坦納比大於0.824，雖距0.866不遙遠，卻始終未能達到最終目標。美國數學會主席曾感嘆道：“這問題已經公開了22年，這件事總令你不安，你不能證明這樣初級的東西。”也許源於猜想提出的戲劇性背景，也許源於理論意義以及貝爾實驗室的學術權威，也許源於數學家對形成初等而又難解問題的愛好，人們對這個問題的研究歷久不衰。
1990年，41歲的堵丁柱因為攻克這一問題而成為世界數學界冒出的奇葩。他與貝爾實驗室黃光明研究員合作，找到了一個全新途徑，給出了吉爾伯特-波雷克猜想完整的證明。證明的核心是關於鞍點的一個定理。其主要思想是，首先在歐氏平面含n點的集合與2n-3維空間的點之間建立一一對應的關係，使得猜想可以化為2n-3維空間上函式的極值問題。然後利用鞍點定理找出可以達到極值的臨界點應滿足的必要條件。之後，再將此條件轉換為臨界點對應的點集上的幾何性質。最後，利用這幾何性質確定幾何結構，驗證該猜想。一個重要的注釋是，為獲得較易驗證的幾何結構，他們將猜想先轉換為一個較強的形式，然後再如上法炮製。
證明於1990年10月在會議上正式公開，《紐約時報》立刻做了報導。接著《科學》雜誌、《科學新聞》《新科學論》《SLAM新聞》等報刊上出現了許多報導。值得提及的《SLAM新聞》在頭版上用了個有趣的“在計算機時代歐氏幾何的歐氏平面上n點的集合←→2n-3維空間的點力與運氣”。在《不列顛百科全書1992年鑑》中，該證明進一步被列為入選的6項數學成果的第一項。因此，堵丁柱也榮獲了中國科學院自然科學一等獎、國家科技進步二等獎和中國青年科學家獎等殊榮。
Stewart教授對證明的意義作了闡述。12年前曾當過堵丁柱的老師，12年後又配合堵丁柱攻克斯坦納比難題的貝爾實驗室研究員黃光明在興奮之餘撰文記述了研究過程。他幽默地寫道：“如果要等我證出0.866的猜想才退休，那我可能要在貝爾實驗室過百歲生日了。解決這一問題的關鍵也許不在時間而在人，我能做的貢獻是找到一個比我強的人來作此問題。我找到了堵丁柱，而堵丁柱今年四月找到了答案。”
每個成功者的背後，都會留下奮鬥的足跡。探索一下堵丁柱的成才之路，或許對今天的青年朋友有所啟迪。
1996年，堵丁柱的老師越民義在《運籌學雜誌》發表論文，否定了堵丁柱和黃光明的工作。