复杂无向网络连通性的一种高效判定算法  

An Efficient Algorithm for Determining the Connectivity of Complex Undirected Networks

作　　者：王卓[1,2] 秦博东 徐雍 鲁仁全 魏庆来 WANG Zhuo;QIN Bo-Dong;XU Yong;LU Ren-Quan;WEI Qing-Lai(The Research Institute of Frontier Science,and Beijing Advanced Innovation Center for Big Data-Based Precision Medicine,Beihang University,Beijing 100191;Beijing Academy of Quantum Information Sciences,Beijing 100193;The The School of Instrumentation and Optoelectronic Engineering,Beihang University,Beijing 100191;The School of Automation,Guangdong University of Technology,and Guang-dong Provincial Key Laboratory of Intelligent Decision and Co-operative Control,Guangzhou 510006;The State Key Lab-oratory for Management and Control of Complex Systems,In-stitute of Automation,Chinese Academy of Sciences,Beijing 100190)

机构地区：[1]北京航空航天大学前沿科学技术创新研究院北航-首医大数据精准医疗高精尖创新中心,北京100191 [2]北京量子信息科学研究院,北京100193 [3]北京航空航天大学仪器科学与光电工程学院,北京100191 [4]广东工业大学自动化学院智能决策与协同控制广东省重点实验室,广州510006 [5]中国科学院自动化研究所复杂系统管理与控制国家重点实验室,北京100190

出　　处：《自动化学报》2020年第10期2129-2136,共8页Acta Automatica Sinica

基　　金：国家自然科学基金(61673041,61722312,61876041,61425009,U1611262);北京量子信息科学研究院(Y18G34)资助。

摘　　要：通信网络的拓扑结构连通性是多智能体系统一致性控制或编队控制等的理论前提.以往,各种多智能体系统一致性控制或编队控制方面的文献仅侧重于控制协议、智能体动力学模型和控制律设计,而缺乏对多智能体通信网络拓扑结构的连通性研究.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证,而且在图论、现代移动通信、计算机与交通等各种网络中有着重要和广泛的应用.针对复杂无向网络的连通性问题,本文给出了一种新的高效判定算法、以及该算法的时间复杂度和空间复杂度的上界.该算法具有非常低的时间复杂度和空间复杂度,且便于计算机实现,因而具有重要的理论意义和广泛的实用价值.The topological connectivity of communication network is the theoretical premise of consistency control or formation control of multi-agent systems. The past literature on consistency control or formation control of multi-agent systems focused only on control protocol, agent dynamics model and control law design, lacking the research on the topological connectivity of multi-agent communication network. The efficient determination algorithm of network connectivity is not only the guarantee of consistency control or formation control for the large-scale multi-agent systems, but also has important and extensive applications in graph theory and various networks such as modern mobile communication networks, computer networks and transportation networks. This paper presents a new efficient determination algorithm with the upper bounds of the time complexity and space complexity of the algorithm, for the connectivity problem of complex undirected networks. The algorithm has very low time complexity and space complexity, and can be realized easily with computer programs, which makes it have important theoretical significance and wide practicability.

关 键 词：复杂无向网络 图论 连通性 多智能体系统 高效算法 

分 类 号：O157.5[理学—数学] TP301.6[理学—基础数学]