基于可拓层次分析法求解最佳生成树

摘要：

针对最小生树不唯一,如何选择最优的最小生成树的问题,提出了将破圈法和可拓层次分析法相结合的方法.首先,用破圈法求出一个最小生成树;其次,对连通图进行约化,得出约化图,标记固定边,求出换入边,用破圈法的思想求出全部的最小生成树;因最小生成树的结构不相同,节点之间的连接方式也不相同,最小生成树的选取就有了区别,最后,采用可拓层次分析法对全部最小生成树进行评价,从最小生成树的节点度为1的节点比例、聚类系数、平均路径长度、网络效率构造可拓判断矩阵,计算权重向量,进行层次单排序和层次总排序.以一个连通图为例,说明了该方法的步骤和可行性,得到了得分最高的最小生成树即为最佳生成树.

关键词：可拓层次分析法、最小生成树、最佳生成树、约化图、破圈法

所属期刊栏目：40

分类号：TP181(自动化基础理论)

资助基金：辽宁省自然科学基金资助项目;大连海事大学骨干基金资助项目

在线出版日期：2020-08-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：132-135