| 约束最小支撑树问题 |
| |
| 引用本文： | 李淑君,唐恒永. 约束最小支撑树问题[J]. 沈阳师范大学学报(自然科学版), 2006, 24(1): 13-15 |
| |
| 作者姓名： | 李淑君 唐恒永 |
| |
| 作者单位： | 沈阳师范大学,数学与系统科学学院,辽宁,沈阳,110034 |
| |
| 摘 要： | 主要研究两类约束最小支撑树问题,即点约束和边约束最小支撑树问题.点约束最小支撑树问题主要研究了点v不是叶子和点v是叶子两个具体约束问题,边约束最小支撑树问题的约束条件分别为包含给定边e0和不包含给定边e0,对上述问题分别给出了一些基本定理和算法.
|
| 关 键 词： | 支撑树 约束最小支撑树 多项式算法 算法复杂性 |
| 文章编号： | 1008-374X(2006)01-0013-03 |
| 收稿时间： | 2005-02-23 |
| 修稿时间： | 2005-02-23 |
The Minimum Weight Spanning Tree with Constraints |
| |
| LI Shu-jun,TANG Heng-yong. The Minimum Weight Spanning Tree with Constraints[J]. Journal of Shenyang Normal University(Natural Science Edition), 2006, 24(1): 13-15 |
| |
| Authors: | LI Shu-jun TANG Heng-yong |
| |
| Affiliation: | College of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110004, China |
| |
| Abstract: | In this paper,two types of the minimum weight spanning tree with constraints are investigated.They are the minimum weight spanning trees with vertex constraints and with edge constraints.In the first type,two problems conserning point v which is a leaf and is not a leaf are considered.In the second type,two problems of the given edge is in and not in the minimum weight spanning tree are considered.Some basic theorems and corresponding algorithms are given. |
| |
| Keywords: | the spanning tree the minimum weight spanning tree with constraints polynomial algorithm complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
