|
|||||
|
|
| 梯形波图的最小Steiner树 | |
| 引用本文： | 宋国栋,丁吉豫,赵树春.梯形波图的最小Steiner树[J].高师理科学刊,1983(2). |
| 作者姓名： | 宋国栋 丁吉豫 赵树春 |
| 作者单位： | 齐齐哈尔轻工学院 (宋国栋)，齐齐哈尔师范学院 (丁吉豫)，东北重型机械学院(赵树春) |
| 摘 要： | <正> 一、引言 设X是平面有限点集,对于任意平面点集Y(?)X,Y上总长最小的网络(显然,这个网络是树)称为集X上的最小Stener树,记为SMT(X)。X中的点称为正则点,Y-X的点称为Steiner点。已知X构造SMT(X)的问题称为Steiner问题。已知一般的Steiner问题是NP—完全问题。因此在一般图上构造SMT是一个很困难的问题。直到1961年Melzak才证明它是一个有限问题。1978年F.R.K.Chung及R.L.Graham才在梯子(Ladder)图上构造了第一个SMT的无穷类。后来,F.K.Hwang,D.Z.Du等又构造了锯齿图上 |
| 本文献已被 CNKI 等数据库收录！ | |