该文主要讨论t<*>的结构特征及其在特殊条件下4度Steiner最小树的构造.全文共 分十章:第一章介绍问题提出的实际背景及讨论这个问题所需要的相关预备知识.第二章给出了4度Steniner最小树的一些重要性质,这些性质是进一步讨论4度Steiner最小树总是的 基础.第三章讨论了4度Steiner最小树长度的界,给出了点集N上的4度Steiner最淖树长度 的下界是N上的最小生成树的长度的(3-bar)1+3<1/2>倍.第四章讨论了正从边形顶点集上4度Steiner最小树的结构特征,并给出了正多边表顶点集上4度Steiner最小树的构造方法. 第五章讨论直线上的点集、T形点集、拟T形点集、L形点集和十字形点集上4度Steiner最小 树的构造,它为第六章证明4度Steiner最小树问题是NP-困难问题做准备.第六章研究人员 将4度Steiner最小树问题转化成取整形式,借助已知的NP-完全问题-三元恰当覆盖,证明了取整4度Steiner最小树问题是NP-完全问题,进而说明了4度Steiner最小树问题是NP-困难的.正是由于4度Steimer最小树问题的固有难解性,第七章研究人员考虑了在已知满4度Steiner拓扑下的最短网络问题,给出了在L<,2>度量下求这个最短网络的O(n<2>)时间算法.第 八章给出了在L<,p>(p=1+∞)度量下,由已知满4度Steiner拓扑确定的最短网络的O(n)时间 算法.第九章讨论了圆约束下的3度Steiner最小树问题,即高L是Euclidean平面上半径为r 的圆,N是在圆个的n个正则点的集合是n-1个Steiner点的集合,该问题是在L上找一点p,使联接点集N∪M∪{p}的网络最短.第十章提出了一些值得进一步研究的问题.