斯坦納二重奏

《斯坦納二重奏》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、斯坦纳二重奏斯坦纳系和斯坦纳树黄光明一、前奏斯坦纳(Steiner)是十九世纪中叶瑞士的一个几何学家。斯坦纳系是他念的系；斯坦纳树是他种的树。这样的破题虽然也说的通，却似乎没有什么数学兴味。所以让我们对主题再作一新的诠释。二、序曲我们首先要声明的即斯坦纳系(Steinersystem)和斯坦纳树(Steinertree)这两个主题在数学上毫无相关。它们的相关是文字上的，即两者都挂上了斯坦纳的商标。更巧合的是这两个问题事实上都不是斯坦纳首先提出的，他只是众多接触这两个问题中的人之一，也并没有特出贡献。这一张冠李戴的错误当然怪

2、不上斯坦纳，因为并不是他命名的。大概有名的人帽子号码大些，被人顺手牵羊戴在头上的机会也大些。我们所以选这一题目介绍在这一集组合专辑里因为这两个问题都和组合有些关系。斯坦纳系是组合设计中广受注意的一个问题，组合设计研究中的一个基本课题就是讨论什么是组合设计存在的充要条件。当然由于这个问题太大，所以要把组合设计分类讨论，而斯坦纳系就是首先获得重要突破的一个大类。斯坦纳树是最新兴起的计算几何学里的一个课题。我们知道平面几何的作图工具是圆规和直尺，到了二十世纪的今天作图的工具已改为计算器了。计算几何即讨论以计算器来作几何问题的算法

3、。由于计算器科学和组合学的亲密关系，许多领域是这两门学科的共管区，而许多学者也具双重学籍。三、斯坦纳系乐章一个(v,b,r,k,λ)设计，也称区组设计(blockdesign)，指的是v元集V上由b个k-子集（每一k-子集也称一区组）组成的一个子集族。它满足下列两条件：·(甲)V的每个元素恰出现在r个区组中。·(乙)V的每一对元素恰出现在λ个区组中。下例是一个(6,10,5,3,2)设计：元素1出现在区组2,6,7,8,10中共五次，其它元素也各出现五次，元素1和2共同出现在区组8，10中共二次，其它任二元素亦同出现二次。

4、在一个(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-子集。这两

5、种平凡情形一笔带过即可。k=3时是第一个需要研究的情形，而k=3的情形仍需一步步做。第一步是解决的问题。注意当k=3，时，(3)可简化为英国的伍尔豪斯(Woolhouse)在1844年首先提出k=3,的区组设计问题，三年后同为英籍的柯克曼(Kirkman)牧师证明了(4)式的确是(v,b,r,3,1)设计存在的充要条件。但基于「好事不出门，恶事传千里」的原则，这一发现并未传到海峡对岸的欧洲大陆。1853年斯坦纳「闭门家中坐」在研究四次曲线的二重切线问题时也遇到了k=3，的区组设计问题，他猜测了六年前柯克曼已证明了的结果，1

6、859年赖斯(Reiss)证明了斯坦纳的猜测。从此，k=3,的区组设计就被称为斯坦纳三元系(triplesystem)。一个名称一被发明后就无孔不入，因此k=3,λ一般的区组设计就叫做三元系，而k一般，的区组设计当然顺理成章的叫斯坦纳系。区组设计存在的充要条件这一问题一直到一百年后才获得了重大的突破。1961年犹太人哈纳尼(Hanani)证明了(3)式确是三元系区组设计存在的充要条件，他也证明了(3)式也是k=4时的充要条件。但当时人们早就知道有些满足(3)式的区组设计并不存在，因此提出下一猜想：「对给定的定k，除去有限对

7、数值(v,λ)之外，(3)式是区组设计存在的充要条件。」1975年美国人威尔逊(Wilson)证明了这一猜想，一百三十年来这一问题在组合学界引起的波动与震撼，至此尘埃落定。在组合学的研究上往往在解决了存在的问题后下一个要回答的问题是有多少？因此我们也可以问对于一个给定的正整数v，究竟有多少个不同的斯坦纳三元系存在？这个问题也许太难了，我们把范围收敛一点。如果在同一个v元集上的两个斯坦纳三元系没有相同的区组，则我们说这两个三元集不相交。定义d(v)为给定v后互不相交的斯坦纳三元系最大的数目，对于d(v)的探讨称为斯坦纳三元系

8、大集(largeset)问题。从斯坦纳三元系的充要条件我们只需讨论的情形，且已知。另一方面，V共有个3-子集，而每一个斯坦纳三元集含个3-子集，故知如果d(v)=v-2，我们说对于这一v值，斯坦纳三元系大集存在。大集问题的诞生几乎和斯坦纳三元系同时。1850年英国大数学家凯莱(Cayley)证明了d(7