赋权连通图最小生成树分析研究  

An Analysis on the Minimum Spanning Tree of Weighted Connected Graph

作　　者：索红军[1] 

机构地区：[1]渭南师范学院数学与信息科学学院,陕西渭南714099

出　　处：《渭南师范学院学报》2015年第14期44-47,共4页Journal of Weinan Normal University

基　　金：渭南师范学院科研计划项目:自动机理论在航天测控设备故障诊断专家系统中的应用研究(14YKF003);渭南师范学院特色学科建设项目:数学方法在秦东经济社会发展中的应用(14TSXK02)

摘　　要：结合克鲁斯卡尔算法,提出通过增加辅助边集合,在应用克鲁斯卡尔算法构造赋权连通图最小生成树的过程中,同时保留权值较小的、非最小生成树的边的方法对克鲁斯卡尔算法进行补充,最终得到两个边集,一个为原来克鲁斯卡尔算法构造的最小生成树的边集,另一个为考虑工程修改变化而保留的辅助边集,两个边集互不影响.应用最小生成树解决工程问题时,若不考虑工程后续修改变化,则仅需要考虑原克鲁斯卡尔算法构造的最小生成树的边集;当需要考虑工程后续修改变化时,则需要同时考虑原克鲁斯卡尔算法构造的边集和现在提出的辅助边集,才能保证根据工程实际情况发生修改变化后构造的生成树总权值仍然能够保持最小.This paper analyzes the weighted connected graph of the minimum spanning tree of the prim algorithm and Kruskal algorithm and puts forward the defects in practical engineering applications in the field of engineering, with the application as the background. This method needs to consider the follow-up project when the structure changes under the condition of minimum span- ning tree. Combined with Kruskal algorithm, the paper proposed by adding auxiliary edge set, in the process of application of Kruskal constructing minimum spanning tree method, while retaining the non-minimum spanning tree, the edges of the smaller weight of Kruskal algorithm. Finally it got two edge sets, a minimum spanning tree to the original Cruise Carle algorithm to construct the edge the other set, an auxiliary and reserve changes to consider engineering edge set. The two sets of edges do not influence each other, the application of minimum spanning tree to solve engineering problems can be considered at the same time. The two sets of edges achieve weighted connected graph according to the actual situation of engineering change after revision. Total weight can be kept to the minimum spanning tree and can only consider the original Cruise Carle algorithm to get the edge set and the application does not consider the original engineering changing the minimum spanning tree.

关 键 词：赋权 最小 生成树 分析 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]