摘要
针对现有计算方法计算时间长且计算效率随着连通图的规模增大逐渐下降的问题,提出一种针对连通图的随机生成树组求解算法。首先定义简化规则,将复杂图中不涉及生成树生成过程的辐射通路删除,合并互斥支路集中的支路得到简化图,然后通过在简化图和树图间以轮盘赌的方式随机选择支路进行迁移得到简化图对应的生成树图,最后逆向用简化图和原图的支路关系得到复杂图对应的生成树组。通过算例表明,该方法能快速有效地生成对应的生成树组。
Aiming at the problems of long calculation time and the gradual decrease of calculation efficiency with the increase of graph scale,a random spanning tree group solving algorithm for connected graph is proposed.Firstly,the simplification rules are defined,the radiation paths in the complex graph that do not involve the spanning tree generation process are deleted,and the branches in the mutually exclusive branch set are combined to obtain a simplified graph.Then the spanning tree graph corresponding to the simplified graph is obtained by randomly selecting branches in a roulette way between the simplified graph and the tree graph.Finally,the spanning tree group corresponding to the complex graph is obtained by reversely using the branch relationship between the simplified graph and the original graph.The result of an example shows that this method can generate the corresponding spanning tree group quickly and effectively.
作者
董张卓
罗辉
齐洋
DONG Zhangzhuo;LUO Hui;QI Yang(College of Electronic Engineering,Xi’an Shiyou University,Xi’an,Shaanxi 710065,China;College of Electrical and Control Engineering,Xi’an University of Science and Technology,Xi’an,Shaanxi 710054,China)
出处
《西安石油大学学报(自然科学版)》
CAS
北大核心
2022年第5期115-122,共8页
Journal of Xi’an Shiyou University(Natural Science Edition)
基金
陕西省自然科学基础研究计划“含有需求响应参与的泛虚拟电厂的模型框架与优化调度研究”(2020JM-542)。
关键词
连通图
随机生成树组
辐射通路
轮盘赌
connected graph
random spanning tree group
radiation path
roulette