|
|||||
|
|
| 最小树问题的全部解 | |
| 引用本文： | 林诒勋.最小树问题的全部解[J].数学的实践与认识,1985(2). |
| 作者姓名： | 林诒勋 |
| 作者单位： | 郑州大学 |
| 摘 要： | <正> 以某些实际问题(如管道设计、通讯网建设等)为背景,图论中的最小树问题引起人们的广泛兴趣.自从 Kruskal 提出三种基本的构造法以后,各种算法实现途径相继出现,使这一问题得到完满的解决.然而,实际问题往往不能满足于求出一个最小树,而希望兼顾其它目标,在若干最小树中进行再选择.这就要求我们讨论最小树问题的全部解.在已有文献中,求全部支撑树已有较成熟的算法,尤其是文献4]提供的算法可以将全部支撑树按权的大小依次列出.从理论上说,可以认为这些结果已经包含了求全部最小树问题.作为另一种途径,本文将着重讨论最小树问题全部解的性质,并由此建立求全部解的广探法(求全部支撑树的 Mayeda-Seshu 算法的推广). |
| 本文献已被 CNKI 等数据库收录！ | |