－－记应用数学所研究员堵丁柱
袁硕焱 刘振坤
攻克斯坦纳比难题
为了汲取西方新的知识，堵丁柱研究员1990年2月再次出国，在美国普林斯顿大学作访问学者。才一个多月，即4月10日，他就和美国贝尔实验室黄光明研究员合作攻克了吉尔伯特--波雷克猜想，即斯坦纳比难题。所以堵丁柱研究员说，这个结果是在国外做完的，但是大量研究工作实际是在国内做的。1990年10月正式公布以后，没想到会引起国际数学界那样广泛注意和强烈反响，被列为1989年-1990年度美国离散数学界和理论计算机科学界重大成果。英国大百科全书在收录这一成果时也评价说：“在过去的一年里，数学上最显著的进展包括长期、著名的猜想--一个最短网络的猜想……这个猜想就是斯坦纳比问题。”
什么是斯坦纳比问题呢？假设我们在北京、上海、西安三城市之间架设电话线，一种办法是分别联通北京--上海和北京--西安。另一种办法是选第四个点，假设郑州。由此分别向三城市架线，可能你不会想到第二种办法所用的电话线只是第一种办法的86.6%，即可取得比第一种办法节约13%的显著经济效益。这就是离散数学界30年代提出的著名的斯坦纳比问题，但一直未能得到证明。直到1967年大名鼎鼎的贝尔电话公司，遇上了一家精明的用户航空公司，竟被戳了一个大窟窿。这家用户要求在第四个点的位置上架上电话线。这样使得电话公司不仅要拉新线，增加服务网点，而且要减少收费。这件事的连锁反应迫使电话公司改变了坚持长达10年按照最少发生树长度收费的原则，并且不得不对最短网络问题进行研究。于是，贝尔实验室数学中心主任波雷克和研究员吉尔伯特对斯坦纳比问题作了许多研究，根据自己多年研究所得提出如下猜想：对欧氏平面上的任何有限点集，其最小的Steiner树同最小发生树的长度之比(称为Steiner比，即斯坦纳比)不小于√3/2。换言之，正三角形加点可以节省最多。但他们自己并没有能证明它。
由于其在运输、通信和计算机等现代经济与科技中的重要作用，近几十年来它的研究进展越来越快。1985年，格拉姆和金芳容借助于计算机进行了大量运算，证明了斯坦纳比大于0.824，虽距0.866不遥远，却始终未能达到最终目标。美国数学会主席曾感叹道：“这问题已经公开了22年，这件事总令你不安，你不能证明这样初级的东西。”也许源于猜想提出的戏剧性背景，也许源于理论意义以及贝尔实验室的学术权威，也许源于数学家对形成初等而又难解问题的爱好，人们对这个问题的研究历
