摘要: 为了提高计算机的运算速度和集成电路的集成度,对大规模集成电路芯片连线优化问题的一个重要数学模型-Steiner最小树结构的研究从60年代起便引起人们的关注.设X是平面任一有限点集内接于X的最小网络称为X上的Steiner最小树,记作SMT(X).其上不仅有属于X的结点,还有不属于X的结点(Steiner点).已知在一般平面点集X上构造Steiner最小树的问题是NP-完全问题.自1978年以来,仅有少数在特殊点集上构造Steiner最小树的工作.我们在一种分布在两条平行直线上的点集上构造出Steiner最小树的无穷类.