斯坦納二重奏.doc

斯坦纳二重奏斯坦纳系和斯坦纳树黄光明 一、前奏斯坦纳 (Steiner) 是十九世纪中叶瑞士的一个几何学家。斯坦纳系是他念的系；斯坦纳树是他种的树。这样的破题虽然也说的通，却似乎没有什么数学兴味。所以让我们对主题再作一新的诠释。二、序曲我们首先要声明的即斯坦纳系 (Steiner system) 和斯坦纳树 (Steiner tree) 这两个主题在数学上毫无相关。它们的相关是文字上的，即两者都挂上了斯坦纳的商标。更巧合的是这两个问题事实上都不是斯坦纳首先提出的，他只是众多接触这两个问题中的人之一，也并没有特出贡献。这一张冠李戴的错误当然怪不上斯坦纳，因为并不是他命名的。大概有名的人帽子号码大些，被人顺手牵羊戴在头上的机会也大些。 我们所以选这一题目介绍在这一集组合专辑里因为这两个问题都和组合有些关系。斯坦纳系是组合设计中广受注意的一个问题，组合设计研究中的一个基本课题就是讨论什么是组合设计存在的充要条件。当然由于这个问题太大，所以要把组合设计分类讨论，而斯坦纳系就是首先获得重要突破的一个大类。斯坦纳树是最新兴起的计算几何学里的一个课题。我们知道平面几何的作图工具是圆规和直尺，到了二十世纪的今天作图的工具已改为计算器了。计算几何即讨论以计算器来作几何问题的算法。由于计算器科学和组合学的亲密关系，许多领域是这两门学科的共管区，而许多学者也具双重学籍。 三、斯坦纳系乐章一个 (v,b,r,k,) 设计，也称区组设计 (block design)，指的是 v 元集 V 上由 b 个 k-子集（每一 k-子集也称一区组）组成的一个子集族。它满足下列两条件： (甲) V 的每个元素恰出现在 r 个区组中。 (乙) V 的每一对元素恰出现在 个区组中。 下例是一个 (6,10,5,3,2) 设计： 元素 1 出现在区组 2,6,7,8,10 中共五次，其它元素也各出现五次，元素 1 和 2 共同出现在区组 8，10中共二次，其它任二元素亦同出现二次。 在一个 (v,b,r,k,) 设计中，v 个元素每个出现 r 次，所以共出现 vr 次。另一方面，b 个区组每一个中有 k 个元素出现，所以共出现 bk 次，因此 v 个元素共有 对，每对出现 次，所以共出现 对次。另一方面 b 个区组每一个中有 对出现，所以共出现 对次。因此 所以 v,b,r,k, 五个参数中事实上只有三个独立参数，设为 v,k,。由(1)和(2)解得 及 由于 r 和 b 必须是整数，故知 是 (v,b,r,k,) 设计存在的必要条件。问题是(3)是否也是充分条件？ 读者很容易自行检验当 k=1 和 2 时，唯一的区组设计分别是 V 的全部 1-子集和 V 的全部 2-子集。这两种平凡情形一笔带过即可。 k=3 时是第一个需要研究的情形，而 k=3 的情形仍需一步步做。第一步是解决 的问题。注意当 k=3， 时，(3)可简化为 英国的伍尔豪斯 (Woolhouse) 在1844年首先提出 k=3, 的区组设计问题，三年后同为英籍的柯克曼 (Kirkman) 牧师证明了(4)式的确是 (v,b,r,3,1) 设计存在的充要条件。但基于好事不出门，恶事传千里的原则，这一发现并未传到海峡对岸的欧洲大陆。 1853年斯坦纳闭门家中坐在研究四次曲线的二重切线问题时也遇到了 k=3， 的区组设计问题，他猜测了六年前柯克曼已证明了的结果，1859年赖斯 (Reiss) 证明了斯坦纳的猜测。从此，k=3, 的区组设计就被称为斯坦纳三元系 (triple system)。一个名称一被发明后就无孔不入，因此 k=3, 一般的区组设计就叫做三元系，而 k 一般， 的区组设计当然顺理成章的叫斯坦纳系。 区组设计存在的充要条件这一问题一直到一百年后才获得了重大的突破。 1961年犹太人哈纳尼 (Hanani) 证明了(3)式确是三元系区组设计存在的充要条件，他也证明了(3)式也是 k=4 时的充要条件。但当 时人们早就知道有些满足(3)式的区组设计并不存在，因此提出下一猜想：对给定的定 k，除去有限对数值 (v,) 之外， (3)式是区组设计存在的充要条件。 1975年美国人威尔逊 (Wilson) 证明了这一猜想，一百三十年来这一问题在组合学界引起的波动与震撼，至此尘埃落定。 在组合学的研究上往往在解决了存在的问题后下一个要回答的问题是有多少？因此我们也可以问对于一个给定的正整数 v，究竟有多少个不同的斯坦纳三元系存在？这个问题也许太难了，我们把范围收敛一点。如果在同一个 v 元集上的两个斯坦纳三元系没有相同的区组，则我们说这两个三元集不相交。定义 d(v) 为给定 v 后互不相交的斯坦纳三元系最大的数目，对于 d(v) 的探讨称为斯坦纳三元系大集 (large set) 问题。从斯坦纳三元系的充要条件我们只需讨论 的情形，且已知 。另一方面，V 共有 个 3-子集，而每一个斯坦纳三元集含 个 3-子集，故知 如果 d(v)=v-2，我们说对于这一 v 值，斯坦纳三元系大集存在。 大集问题的诞生几乎和斯坦纳三元系同时。 1850年英国大数学家凯莱 (Cayley) 证明了 d(7)=2，即大系只包含 D1 和 D2 两设计： 同年柯克曼证明了 d(9)=7。但不像斯坦纳三元系在数年内即分别被柯克曼和赖斯解决，大集问题在下一百年内几乎毫无进展，由此可以看出它的难度。一直到1972年始，多延 (Doyen)，考席 (Kotzig)等从寻求 d(v) 的下界入手，引进递归方法，才使这个问题有了新的进展。 1973年和1974年丹尼斯顿 (Denniston)，施赖伯 (Schreiber) 和威尔逊陆续对 205 以内，满足 的大部份 v 值给出了斯坦纳三元系大集。此外泰尔林克 (Teirlinck) 和罗莎 (Rosa) 分别给出了 v 到 3v 和 v 到 2v+1 的递归结果。但是总而言之到1980年止，关于斯坦纳三元系大集的存在问题只有零碎的结果而无全面破案之计。 我们现在把镜头自北美大陆迅速拉开，越过太平洋，越过山东半岛，越过华北平原而到达内蒙古境内，可以听到黄河，可以望见长城的包头市。在这儿的包头九中一位年轻的物理老师陆家羲，在六十年代初期即在繁忙的物理教学课后，埋头从事他业余兴趣，组合设计研究。六十年代初期正是组合学的辉煌时代，1960年玻色 (Bose)、血汗 (Shrikhande)，派克 (Parker) 粉碎了欧勒 (Euler) 在拉丁方阵上的猜想，第一次把数学带上了纽约时报的头版。 1961年哈纳尼获得了 k=3,4 时区组设计的充要条件，这些都是组合学上百年来的大事。陆家羲1961年解决了在组合学上号称三大疑案之一的柯克曼女学生问题，他的文章投寄给中国的数学杂志，却遭到屡投屡退的命运，现在他的原稿已经遗失，只留下了投稿退稿的记录，及1965年的修正稿。这份修正稿的正确性现已由苏州大学的吴利生教授肯定，当年却仍不能受到审稿者的青睐。在中国明珠被藏的时候，国外的学者却在生气勃勃的叩关攻坚。 1971年美国俄亥俄州大的博士生威尔逊和他的导师印籍雷小杜里 (Ray-Chaudhuri) 终于接受着大家的恭贺成为柯克曼女学生问题的法定征服者。 然后是四人帮的混沌时期，学校关闭，教师下放，除了少数亲朋外全世界大概没有人知道陆家羲的下落也没有人会关心。像中国众多的年轻科学家，有发光的潜能，有发热的内涵，却因命运的播弄而含苞未放，像天际一颗遥远的星星在人们还来不及注意它时已被厚黑的云层吞没。 吞没了吗？在下一个浪潮中陆家羲却又平地一声雷的站了起来。随着中国大陆的对外开放政策，陆家羲这次越过了中国的障碍而把研究成果投寄到美国颇有权威性的组合论杂志。从1981到1983年，该杂志先后发表了陆家羲六篇论文，宣布了斯坦纳三元系大集问题的彻底解决。他证明了当 且 v7 时除了 六个数外，d(v) 恒等于 v-2。这一颗曾被柯克曼、凯莱、西尔威斯特 (Silvester) 等数学界大贤灌溉过的铁树，终于百年后在陆家羲的手上开了花。 对于六个没有答案的 v 值，陆家羲也在1983年的数学会议上宣布了他已明珠在握，将写成第七篇论文。可惜同年十月陆家羲在写下了二十四页的纲领后，即突然去世了，留待后人来举起他苦撑四分之一世纪积成疾放下的火炬。 四、斯坦纳树乐章十七世纪初期的某一天，法国大数学家费玛 (Fermat) 正结束了一个有名的关于求最大最小值的演讲，演讲中他介绍了一个在各种曲线上不用微积分求切线的办法。他雄辩的向听众挑战说：谁不信我的办法，就解这个问题给我看：给定平面上三点，找出第四点使得它和给定三点的距离之和为最小。当费玛丢出一个问题后，自然四方都有回响。 1640年意大利的托里切里 (Torricelli) 用几何方法证出第四点应是正三角形 ABD、BCE、CAF 的外接圆交点（图一点 O，ABC 是三给定点）称为托点。 1674年卡伐利立 (Cavalieri) 在他的几何演习一书中指出 。 1750年辛普生(Simpson)证明托点也是 AE、BF、CD 三线的交点，这些线都叫做辛线。 1834年海能 (Heinen) 指出了以上结果都只有在 内角都不大于 时成立。当有一角 ，则托点即和此角之顶点重和。 图一托点的求法 他也证明了辛线长等于托点到 A、B、C 的总距离。 这一费玛问题也有另一种提法，即给定平面上三点，找到一个把这三点连结起来最短的网络。这时可证最短网络即是托点和三给定点的联机。当我们把平面上三点推广到平面上 n 点，这两种提法却形成了不同的问题。如果我们要找到一个托点使得该点和给定 n 点的总距离最短，这问题称为广义费玛问题，非本文讨论范围。另一个问题是给定 n 点后找出连接该 n 点的最短网络。这时连接一个托点到每个给定点不一定是最短的连法。譬如给定的四点是正方形的四顶点，则最短网络是图二(甲)而非(乙)。 图二正方形四顶点的最短网络 为了和广义费玛问题区别，上述之最短网络问题被称为斯坦纳问题（据考证斯坦纳虽曾参与此问题但无显著贡献）。网络中所含给定点（称原点）之外的点叫做斯点。 我们首先看看最短的网络应该具有那些性质。所谓一个网络的拓朴即指点与点间连接的关系。因此在一个拓扑中斯点的位置并不固定，边的长度也非所计，一个拓扑只规定了那些点间有边相连。 (甲) 拓扑必须是树形：所谓树形即指没有圈。因为如有圈，则我们可以去掉圈中任一条边来缩短网络而不影响任何点的连接。 (乙) 令 S 为网络中的一斯点，则 S 的度数（即与 S 相交的边数）至少为三：如果S的度数为一，则去掉S上的边不影响任何点的连接；如果S的度数为二，设计二边分别连接U和V，则以线UV代替线 SU和线SV，缩短了网络而不影响任何点的连接。 (丙) 与 S 相交的任两边其夹角不小于 120 度；不然的话可在其两夹边上取 U,V 两点使得 的内角皆小于 120 度。根据费玛问题的结论，S、U、V 三点间的最短连接并非 SU 和 SV 两边，因之现有网络并非最短。 注意(甲)和(乙)合并考虑时，可导致n点的最短网络至多含n-2斯点的结论； (乙)和(丙)合并考虑时，可导致每一斯点恰交三边，且夹角都是120度的结论。 一个连接n原点的网络如满足(甲)(乙)(丙)三条件则称为斯树。显然的，最短网络必须是斯树，所以也可称为最短斯树。有n-2个斯点的斯树称为满斯树。（满）斯树的拓扑称为（满）斯拓扑。 梅尔扎克 (Melzak) 给了一个从一个满拓扑造出它的满斯树的算法，这个算法即成为造n原点上的最短斯树的基础。首先注意任何一个非满的拓扑都可以分解成一些较小的满拓扑。每一个满拓扑上的点集合都是非满拓扑上的点集合的一个子集，每一条非满拓扑的边都属于且仅属于一个满拓扑。下图中显示一个五点的非满拓扑分解成一个四点和一个两点（虚线）的满拓扑。 图三非满拓扑的分解 在每一个满拓扑上用梅尔扎克算法造出它的斯树，这些斯树的联合即为原来非满拓扑的斯树。 现在我们可以叙述造最短斯树的算法：历举所有的斯拓扑（即每一斯点只有三条边的拓扑），对应于每一斯拓扑用Melzak算法造出它的斯树（有时不存在），这些斯树中最短的一个即最短斯树。 尚未明述的一步是梅尔扎克造满斯树的算法。令T为给定的斯拓扑。在n=3时梅尔扎克算法即同于托里切里对费玛问题的解法。当时梅尔扎克算法可以分成两步。第一步是递归的将两原点换为一新原点，且新拓扑的斯点也减少一个，所以仍为满拓扑，直至只剩下两原点为止。细言之，令A、B为连接于同一斯点S的两原点（总有如此两点），设S连接的第三点为C。令D为正三角形ABD的第三点且D与S分在AB线两侧。新的满拓扑T由T去掉AS、BS、CS三边再加上DC边而得。注意D点的位置是固定的，所以可视为一新的原点。第二步是把第一步的顺序倒过来，由两原点的满斯树逐步还原成n原点的满斯树。我们举例说明。 图四梅尔札克造满斯树的算法 设 A、B、C、D 为给定四原点。给定的拓扑T包含下列诸边AS1、BS1、 S1S2、DS2、CS2。梅尔扎克算法第一步（图四A）将E代替A和B，新的拓扑T包含ES2、DS2、CS2三边，再将F代替E和C。剩下一个两点F和D的拓扑包含边FD，第二步（图四B）先作正三角形CEF的外接圆和边FD交于S2，再作正三角形ABE的外接圆与边ES2交于S1。令 t 为含边 AS1、BS1、S1S2、DS2、CS2 的树。连续使用费玛问题的结论，可知 t 为 T 的斯树（即证 S1 和 S2 的边的夹角都是120度）。 我们来检查一下以上法造最短斯树的复杂度 (complexity) 首先我们看看梅尔扎克造满斯树算法的复杂度。注意当我们把两原点换成新点时，我们只知道这三点应构成一正三角形，且新点应和 A、B 点共同连结的斯点分在边 AB 的两侧。但因一般说来在第一步操作时我们并不知道斯点的位置，因此新点的位置有两个可能（分别在边 AB 两侧）。同理下一次换点时又有两个可能，如此推论，则第一步的操作原则上要考虑 2n-2 个可能。当然在点数少时或在其它的几何性质可以利用时，往往可正确的判断新点的位置，但我们无法严格的计算这些可遇而不可求的机运来修正2n-2这一数量。 另一个严重的计算问题是斯拓扑的数目太多。用归纳法可以算出当原点数为 n、斯点数为 s 时，共有 个斯拓扑。当 n=7, s=5 时，这个数目是 945，但在 n=7 时我们需考虑所有 的拓扑。这个总数达到 62370。 这是否意味以上这一造最短斯树的算法太差而应另起炉灶呢？事实上有一个理论上的结果显示只能有量的改进而不会有质的变化了。盖瑞 (Garey)、葛立翰 (Graham) 和强生 (Johnson) 在1977年证明了造最短斯树是一个计算科学上称为 NP-complete 的问题。简言之，即这类问题最佳算法的复杂是 n 的一个幂数函数而非多项式函数。当我们警觉到 2n 当 n=100 时已是一个有 30 个零的数字，就知道造最短斯树只有在 n 很小时才有可行性。用我们介绍的这一算法， n 的上限大约在 10 到 15 之间。 最近有一个已发现的改进和一个可能的改进可以将 n 的上限再往上推展一些。已发现的是梅尔扎克造满斯树的算法可以改进到线性复杂度。细言之，当拓扑含 s 斯点时，如果适当的选择二原点，则新点应在二原点的那一侧永远可以确定，因此 2n-2 种可能就减成只有一个可能。这个结果笔者即将发表于O.R. Letters这一杂志上。 另一个尚未完成，但若成功时其影响将远大于前段所述之改进是，要证明造最短斯树只需考满斯拓扑即可。当最短斯树的拓扑 T 非满时，必定有一个满斯拓扑的斯树会蜕化成 T 的斯树，因此也就是最短斯树。如果上述构想为真，则在 n=7 时，我们只需考虑 s=5 的 945 种拓扑而非 的 62370 种拓扑。 谈到斯坦纳树问题，不可不提一下斯率 (Steiner ratio)。最短生成树的定义是不许有斯点时连接原点的最短网络。斯率的定义是在任何原点集合下最短斯树