基于最小代价和生成树的算法研究  

Research on Algorithms for Minimum Cost Spanning Trees

作　　者：吴龙树[1] 王勤[1] 

机构地区：[1]中国计量学院理学院,浙江杭州310018

出　　处：《微计算机信息》2010年第12期222-223,共2页Control & Automation

基　　金：国家自然科学基金(No.10601051);浙江省自然科学基金项目资助(No.Y6090472)

摘　　要：最小生成树问题是一类经典的组合优化问题,已有许多快速有效的算法。但是在实际中更多存在这样的网络,除边有权值外,结点也有权值,并且结点的权值有多种情况,这就产生了基于代价和最小的生成树问题。根据结点权值的取值情况,对几种最小代价和生成树问题进行分类和求解,得到了一些有价值的性质和算法,有一定的实际应用背景。The minimum spanning tree problem is a classic combinatorial optimization problem and there exist many efficient algorithms to solve it.But in real network,the vertices as well as the edges may have costs,and there are many cases of the vertex weights.The minimum cost spanning tree problem with practical application background is studied in this paper.And some valuable properties and methods are presented for several kinds of minimum cost spanning tree problem based on different values of the vertex weights.

关 键 词：生成树 组合优化 多项式时间算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]