斯坦纳比难题

文化术语

为了汲取西方新的知识，堵丁柱研究员1990年2月再次出国，在美国普林斯顿大学作访问学者。才一个多月，即4月10日，他就和美国贝尔实验室研究员合作攻克了吉尔伯特--波雷克猜想，即斯坦纳比难题。所以堵丁柱研究员说，这个结果是在国外做完的，但是大量研究工作实际是在国内做的[1]。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年，堵丁柱的老师越民义在《运筹学杂志》发表论文，否定了堵丁柱和黄光明的工作[2]。

经过与Du等学者多年的讨论，2012年俄罗斯学者A. O. Ivanov和A. A. Tuzhilin正式宣布steiner ratio 猜想仍是公开问题[3]。

[1] Du, D.Z., Hwang, F.K.: A proof of Gilbert–Pollak Conjecture on the Steiner ratio[J]. Algorithmica 7,

121–135 (1992)

[2] 越民义.关于Steiner树问题.运筹学杂志，1995,01

[3] Ivanov A O, Tuzhilin A A. The steiner ratio gilbert–pollak conjecture is still open[J]. Algorithmica, 2012, 62(1-2): 630-632.

全国各地天气预报查询

上海市

市辖区

云南省

临沧市