第10卷第4期 智能系统学报 Vol.10 No.4 2015年8月 CAAI Transactions on Intelligent Systems Aug.2015 D0:10.3969/j.issn.1673-4785.201411031 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150716.0943.005.html 复杂网络在路形拓扑结构下可控的充要条件 晁永翠，纪志坚，王耀威，董洁 青岛大学自动化工程学院，山东青岛266071 摘要：分析了在路形拓扑结构下复杂网络的可控性问题。把系统的邻接矩阵进行适当分解，找到邻接矩阵的各子 矩阵之间在特征值和特征向量上的关系，进而基于PBH(Popov-.Belevitch--Hautus)判据，得到了复杂网络在路形拓扑 结构下系统可控的充要条件。特别地，当控制节点为任意的某一个或多个节点时，给出了路图可控的判别方法。此 外，文中提出了不可控特征值的概念，并给出了相应特征值的具体表达形式。文中2个主要定理通过算例进行验证， 算例结果与定理结论一致。 关键词：复杂网络；可控性；图论；拓扑：线性定常系统；特征值；特征向量：控制系统 中图分类号：TP18文献标志码：A文章编号：1673-4785(2015)04-0577-06 中文引用格式：晁永翠，纪志坚，王耀威，等.复杂网络在路形拓扑结构下可控的充要条件[J].智能系统学报，2015,10(4)：577 582. 英文引用格式：CHAO Yongcui,JI Zhijian,WANG Yaowei,etal.Necessary and sufficient conditions for the controllability of com- plex networks with path topology[J].CAAI Transactions on Intelligent Systems,2015,10(4):577-582. Necessary and sufficient conditions for the controllability of complex networks with path topology CHAO Yongcui,JI Zhijian,WANG Yaowei,DONG Jie (School of Automation Engineering,Qingdao University,Qingdao 266071,China) Abstract:The controllability of complex networks is analyzed in the paper for path topology.With adjacency matrix of the system being decomposed into submatrices,the relationship between eigenvalues and eigenvectors is revealed for the partitioned submatrices.Furthermore,necessary and sufficient conditions are derived by taking advantage of the PBH(Popov-Belevitch-Hautus)criteria.In particular,a method is proposed to determine path controllability when the controlled nodes are any single or multiple nodes,as well as the concept of uncontrollable eigenvalues is presented.The expressions for uncontrollable eigenvalues are provided as well.Two theorems in this paper is veri- fied by examples and the results of examples are in agreement with the conclusion of the theorems. Keywords:complex networks;controllability;graph theory;topology;linear time-invariant systems;eigenvalue; eigenvectors;control system 控制科学的发展表明，可控性概念是对系统进 是判别被控系统是否可控的重要途径。近年来，网 行分析与综合的基础，是系统的重要结构性质。20 络系统的可控性研究成为当前的一个热点研究领 世纪60年代，卡尔曼(R.E.Kalman))首先提出状 域，该问题的研究受到了国内外科研工作者的广泛 态可控性的概念。其后的研究表明，可控性的概念 关注2-6) 本文致力于研究复杂网络系统的能控性，该研 收稿日期：2014-11-25.网络出版日期：2015-07-16. 究可促进包括系统的镇定控制[8】、编队控制910 基金项目：国家自然科学基金资助项目(61374062). 入侵检测[.2]和分布式估计[316]等诸多问题的理 通信作者：纪志坚.E-mail:jizhijian@(pku.org.cn. 解。和传统控制不同，网络系统是建立在个体间信
第 １０ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．４ ２０１５ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４１１０３１ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０７１６．０９４３．００５．ｈｔｍｌ 复杂网络在路形拓扑结构下可控的充要条件 晁永翠，纪志坚，王耀威，董洁 青岛大学 自动化工程学院，山东 青岛 ２６６０７１ 摘 要：分析了在路形拓扑结构下复杂网络的可控性问题。 把系统的邻接矩阵进行适当分解，找到邻接矩阵的各子 矩阵之间在特征值和特征向量上的关系，进而基于 ＰＢＨ（Ｐｏｐｏｖ⁃Ｂｅｌｅｖｉｔｃｈ⁃Ｈａｕｔｕｓ）判据，得到了复杂网络在路形拓扑 结构下系统可控的充要条件。 特别地，当控制节点为任意的某一个或多个节点时，给出了路图可控的判别方法。 此 外，文中提出了不可控特征值的概念，并给出了相应特征值的具体表达形式。 文中 ２ 个主要定理通过算例进行验证， 算例结果与定理结论一致。 关键词：复杂网络；可控性；图论；拓扑；线性定常系统；特征值；特征向量；控制系统 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０４⁃０５７７⁃０６ 中文引用格式：晁永翠，纪志坚，王耀威，等． 复杂网络在路形拓扑结构下可控的充要条件［ Ｊ］． 智能系统学报， ２０１５， １０（ ４）： ５７７⁃ ５８２． 英文引用格式：ＣＨＡＯ Ｙｏｎｇｃｕｉ， ＪＩ Ｚｈｉｊｉａｎ， ＷＡＮＧ Ｙａｏｗｅｉ， ｅｔ ａｌ． Ｎｅｃｅｓｓａｒｙ ａｎｄ ｓｕｆｆｉｃｉｅｎｔ ｃｏｎｄｉｔｉｏｎｓ ｆｏｒ ｔｈｅ ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｏｆ ｃｏｍ⁃ ｐｌｅｘ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ｐａｔｈ ｔｏｐｏｌｏｇｙ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（４）： ５７７⁃５８２． Ｎｅｃｅｓｓａｒｙ ａｎｄ ｓｕｆｆｉｃｉｅｎｔ ｃｏｎｄｉｔｉｏｎｓ ｆｏｒ ｔｈｅ ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ｐａｔｈ ｔｏｐｏｌｏｇｙ ＣＨＡＯ Ｙｏｎｇｃｕｉ， ＪＩ Ｚｈｉｊｉａｎ， ＷＡＮＧ Ｙａｏｗｅｉ， ＤＯＮＧ Ｊｉｅ （Ｓｃｈｏｏｌ ｏｆ Ａｕｔｏｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｑｉｎｇｄａｏ Ｕｎｉｖｅｒｓｉｔｙ， Ｑｉｎｇｄａｏ ２６６０７１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｉｓ ａｎａｌｙｚｅｄ ｉｎ ｔｈｅ ｐａｐｅｒ ｆｏｒ ｐａｔｈ ｔｏｐｏｌｏｇｙ． Ｗｉｔｈ ａｄｊａｃｅｎｃｙ ｍａｔｒｉｘ ｏｆ ｔｈｅ ｓｙｓｔｅｍ ｂｅｉｎｇ ｄｅｃｏｍｐｏｓｅｄ ｉｎｔｏ ｓｕｂｍａｔｒｉｃｅｓ， ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｅｉｇｅｎｖａｌｕｅｓ ａｎｄ ｅｉｇｅｎｖｅｃｔｏｒｓ ｉｓ ｒｅｖｅａｌｅｄ ｆｏｒ ｔｈｅ ｐａｒｔｉｔｉｏｎｅｄ ｓｕｂｍａｔｒｉｃｅｓ． Ｆｕｒｔｈｅｒｍｏｒｅ， ｎｅｃｅｓｓａｒｙ ａｎｄ ｓｕｆｆｉｃｉｅｎｔ ｃｏｎｄｉｔｉｏｎｓ ａｒｅ ｄｅｒｉｖｅｄ ｂｙ ｔａｋｉｎｇ ａｄｖａｎｔａｇｅ ｏｆ ｔｈｅ ＰＢＨ（Ｐｏｐｏｖ⁃Ｂｅｌｅｖｉｔｃｈ⁃Ｈａｕｔｕｓ） ｃｒｉｔｅｒｉａ． Ｉｎ ｐａｒｔｉｃｕｌａｒ， ａ ｍｅｔｈｏｄ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｄｅｔｅｒｍｉｎｅ ｐａｔｈ ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｗｈｅｎ ｔｈｅ ｃｏｎｔｒｏｌｌｅｄ ｎｏｄｅｓ ａｒｅ ａｎｙ ｓｉｎｇｌｅ ｏｒ ｍｕｌｔｉｐｌｅ ｎｏｄｅｓ， ａｓ ｗｅｌｌ ａｓ ｔｈｅ ｃｏｎｃｅｐｔ ｏｆ ｕｎｃｏｎｔｒｏｌｌａｂｌｅ ｅｉｇｅｎｖａｌｕｅｓ ｉｓ ｐｒｅｓｅｎｔｅｄ． Ｔｈｅ ｅｘｐｒｅｓｓｉｏｎｓ ｆｏｒ ｕｎｃｏｎｔｒｏｌｌａｂｌｅ ｅｉｇｅｎｖａｌｕｅｓ ａｒｅ ｐｒｏｖｉｄｅｄ ａｓ ｗｅｌｌ． Ｔｗｏ ｔｈｅｏｒｅｍｓ ｉｎ ｔｈｉｓ ｐａｐｅｒ ｉｓ ｖｅｒｉ⁃ ｆｉｅｄ ｂｙ ｅｘａｍｐｌｅｓ ａｎｄ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｅｘａｍｐｌｅｓ ａｒｅ ｉｎ ａｇｒｅｅｍｅｎｔ ｗｉｔｈ ｔｈｅ ｃｏｎｃｌｕｓｉｏｎ ｏｆ ｔｈｅ ｔｈｅｏｒｅｍｓ． Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ； ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ； ｇｒａｐｈ ｔｈｅｏｒｙ； ｔｏｐｏｌｏｇｙ； ｌｉｎｅａｒ ｔｉｍｅ⁃ｉｎｖａｒｉａｎｔ ｓｙｓｔｅｍｓ； ｅｉｇｅｎｖａｌｕｅ； ｅｉｇｅｎｖｅｃｔｏｒｓ； ｃｏｎｔｒｏｌ ｓｙｓｔｅｍ 收稿日期：２０１４⁃１１⁃２５． 网络出版日期：２０１５⁃０７⁃１６． 基金项目：国家自然科学基金资助项目（６１３７４０６２） 控制科学的发展表明，可控性概念是对系统进 行分析与综合的基础，是系统的重 通信作者：纪志坚． Ｅ⁃ｍａｉｌ：ｊｉｚｈｉｊｉａｎ＠ ｐｋｕ．ｏｒｇ．ｃｎ． 要结构性质。 ２０ 世纪 ６０ 年代，卡尔曼（Ｒ．Ｅ．Ｋａｌｍａｎ） ［１］ 首先提出状 态可控性的概念。 其后的研究表明，可控性的概念 是判别被控系统是否可控的重要途径。 近年来，网 络系统的可控性研究成为当前的一个热点研究领 域，该问题的研究受到了国内外科研工作者的广泛 关注［２–６］ 。 本文致力于研究复杂网络系统的能控性，该研 究可促进包括系统的镇定控制［７⁃８］ 、编队控制［９⁃１０］ 、 入侵检测［１１⁃１２］ 和分布式估计［１３⁃１６］ 等诸多问题的理 解。 和传统控制不同，网络系统是建立在个体间信 ．
·578 智能系统学报 第10卷 息的传递之上的。自然地，信息关系图的拓扑结构 集合。对于一个有n个节点的无向图G,所有的节 在系统行为的动态演化中起到了关键性作用，不同 点被标记为1,2，…，n。顶点集和边集分别记为 拓扑结构下的系统性能可能截然不同。因此，许多 V={1,2,…,n}与e={(i,)eV×V},i和j邻 科研工作者尝试探讨与能控性相关的图论刻画。例 接。图G是由顶点集V和边集ε构成的二元组，记 如，系统能控的图论特征，这些特征使得直接从图的 为G=(V,s)。与顶点v相关联的边的总数称为顶 拓扑结构出发判断系统的能控性成为可能：再如，能 点v的度。一个有n个节点的图G,若其顶点可以 控性中领航者的选取问题，如何确定领航者的位置 标号成（或重新标号成）1,2，…，n,使得它的边集 和数量使得系统能控，这也是网络系统能控性中的 是6={(1,2)，(2,3)，…，(n-1,n)},则称图G 典型问题。 为路图2。由此可知，除了第一个节点1与最后一 复杂网络的研究已渗透到数理学科、生命学科 个节点n的度为1之外，其他所有节点的度都为2。 和工程学科等众多不同的领域，对复杂网络可控性 节点1与节点n称为外节点，其他的节点称为内节 的研究具有挑战性1]。即便是最简单的路形拓 点。设图G的邻接矩阵A=(a;)nk,则ag定义为 扑结构，和其可控性相关的研究也不简单。文献 1,(i,)∈e或0，i)∈e [I9]研究的是基于Laplacian矩阵的路图的能控性， ag=0,其他8 与该问题相关的研究成果在文献[4,6,20]中也报 在已有文献中，通常把由外部输入控制的节点 道过。此外，还有基于邻接矩阵的网络系统可控性 称为控制节点，由1。={i,i2,…,m}C 问题1】，本文即是研究基于邻接矩阵的路图拓扑 {1,2,…,n}表示被控的节点集。考虑如下一个有 的可控性。 n个节点的线性系统： 本文研究的是控制节点的选取，这不同于文献 x=Ax Bu (1) [17-18]中驱动节点个数的选取问题。在基于邻接 式中：x=[x1x2xn]I表示系统的状态，A∈R“是 矩阵的可控性问题研究，文献[17]中表述，网络中节 系统的邻接矩阵，B∈Rmxm是控制矩阵，u∈Rmx“是输 点的度的大小影响驱动节点个数的选取，在选取驱动 入矩阵。由于讨论的是无向图，所以A是对称矩 节点时，选取度数小的驱动节点更有利于系统可控性 阵。对任一给定的初始状态，如果存在一个控制输 的实现。但针对更复杂的拓扑结构，控制节点的选取 入“，使式(1)能在有限时间间隔内，从初始状态转 比驱动节点的选取更为复杂，相应的结果也更少。文 移到任意指定的终端状态，则称该系统是可控的。 献[18]提出了对于特定的链接与加权网络，使系统可 目前，有许多判别线性系统可控的方法，例如Gram 控的最少数目控制节点的判别方法。然而，以上两篇 矩阵判据、PBH判据2)、秩判据等。本文从PBH判 文章都没有给出针对网络拓扑图中，通过控制某一个 据出发，分析系统的可控性，进而得到系统可控的充 或几个节点，来具体判断系统是否可控的方法。该问 要条件。 题涉及到控制节点的选取，这通常是更为复杂的研究 引理1系统(1)可控的充要条件是不存在非 方面，也是本文着力解决的内容。 零的向量v满足以下等式： 本文将针对路形拓扑结构，对每个节点展开分 Av=入v 析，通过建立充要条件，来判断相应系统的可控性。 BTy=0 更具体地，通过对路图的邻接矩阵及其子矩阵进行分 若存在向量v使得上面的等式成立，则称相应 析，发现其特征值之间的相互关系，从而得到路图可 的入是系统不可控的特征值。 控性的充分必要条件，该结果的一个显著特征是建立 证明根据PBH判据并结合A的对称性即知 了所提出的代数条件与拓扑图中每个节点的联系。 结论成立。 1预备知识 2 主要结论 文中N为自然数集，e,为第r个元素为1，其他 本节将首先对邻接矩阵进行分解，基于此给出 元素均为0的列向量，r∈N,例如e1= 子矩阵特征值的表达形式，然后，通过所提出的矩阵 [10…0]。记G(b,b2,…,ba)为d个自然数b1, 特征值之间的关系，得出相应的引理与定理。 b2,…,b的最大公约数，deN。G(b1,b2,…,b)> 2.1邻接矩阵的分解 1表示b,b2,…,ba有除了1之外的其他公约数。 B矩阵的具体表达与一系列的控制节点相对 R”表示n维实向量空间，Rxa表示实m×n矩阵的 应，如果I={ii,2,…,im},则B=[e,e2…enJ
息的传递之上的。 自然地，信息关系图的拓扑结构 在系统行为的动态演化中起到了关键性作用，不同 拓扑结构下的系统性能可能截然不同。 因此，许多 科研工作者尝试探讨与能控性相关的图论刻画。 例 如，系统能控的图论特征，这些特征使得直接从图的 拓扑结构出发判断系统的能控性成为可能；再如，能 控性中领航者的选取问题，如何确定领航者的位置 和数量使得系统能控，这也是网络系统能控性中的 典型问题。 复杂网络的研究已渗透到数理学科、生命学科 和工程学科等众多不同的领域，对复杂网络可控性 的研究具有挑战性［１７⁃１８］ 。 即便是最简单的路形拓 扑结构，和其可控性相关的研究也不简单［１９］ 。 文献 ［１９］研究的是基于 Ｌａｐｌａｃｉａｎ 矩阵的路图的能控性， 与该问题相关的研究成果在文献［４， ６， ２０］中也报 道过。 此外，还有基于邻接矩阵的网络系统可控性 问题［１７⁃１８］ ，本文即是研究基于邻接矩阵的路图拓扑 的可控性。 本文研究的是控制节点的选取，这不同于文献 ［１７－１８］中驱动节点个数的选取问题。 在基于邻接 矩阵的可控性问题研究，文献［１７］中表述，网络中节 点的度的大小影响驱动节点个数的选取，在选取驱动 节点时，选取度数小的驱动节点更有利于系统可控性 的实现。 但针对更复杂的拓扑结构，控制节点的选取 比驱动节点的选取更为复杂，相应的结果也更少。 文 献［１８］提出了对于特定的链接与加权网络，使系统可 控的最少数目控制节点的判别方法。 然而，以上两篇 文章都没有给出针对网络拓扑图中，通过控制某一个 或几个节点，来具体判断系统是否可控的方法。 该问 题涉及到控制节点的选取，这通常是更为复杂的研究 方面，也是本文着力解决的内容。 本文将针对路形拓扑结构，对每个节点展开分 析，通过建立充要条件，来判断相应系统的可控性。 更具体地，通过对路图的邻接矩阵及其子矩阵进行分 析，发现其特征值之间的相互关系，从而得到路图可 控性的充分必要条件，该结果的一个显著特征是建立 了所提出的代数条件与拓扑图中每个节点的联系。 １ 预备知识 文中ℕ 为自然数集，ｅｒ 为第 ｒ 个元素为 １，其他 元素 均 为 ０ 的 列 向 量， ｒ ∈ ℕ ， 例 如 ｅ１ ＝ ［１ ０ … ０］ Ｔ 。 记 Ｇ ｂ１ ，ｂ２ ，…，ｂｄ ( ) 为 ｄ 个自然数 ｂ１ ， ｂ２ ，…，ｂｄ 的最大公约数， ｄ ∈ℕ 。 Ｇ ｂ１ ，ｂ２ ，…，ｂｄ ( ) ＞ １ 表示 ｂ１ ，ｂ２ ，…，ｂｄ 有除了 １ 之外的其他公约数。 Ｒ ｎ 表示 ｎ 维实向量空间，Ｒ ｍ×ｎ表示实 ｍ × ｎ 矩阵的 集合。 对于一个有 ｎ 个节点的无向图 Ｇ ，所有的节 点被标记为 １，２，…，ｎ 。 顶点集和边集分别记为 Ｖ ＝{１，２，…，ｎ} 与 ε ＝ { (ｉ，ｊ) ∈ Ｖ × Ｖ} ， ｉ 和 ｊ 邻 接。 图 Ｇ 是由顶点集 Ｖ 和边集 ε 构成的二元组，记 为 Ｇ ＝(Ｖ，ε) 。 与顶点 ｖ 相关联的边的总数称为顶 点 ｖ 的度。 一个有 ｎ 个节点的图 Ｇ ，若其顶点可以 标号成（或重新标号成） １，２，…，ｎ， 使得它的边集 是 ε ＝ { (１，２) ，(２，３) ，…，(ｎ － １，ｎ) } ，则称图 Ｇ 为路图［２１］ 。 由此可知，除了第一个节点 １ 与最后一 个节点 ｎ 的度为 １ 之外，其他所有节点的度都为 ２。 节点 １ 与节点 ｎ 称为外节点，其他的节点称为内节 点。 设图 Ｇ 的邻接矩阵 Ａ＝ ａｉｊ ( ) ｎ×ｎ ，则 ａｉｊ 定义为 ａｉｊ ＝ １，(ｉ，ｊ) ∈ ε 或 (ｊ，ｉ) ∈ ε ０，其他 ε { 在已有文献中，通常把由外部输入控制的节点 称 为 控 制 节 点， 由 Ｉｃ ＝ ｉ １ ，ｉ ２ ，…，ｉｍ { } ⊂ {１，２，…，ｎ} 表示被控的节点集。 考虑如下一个有 ｎ 个节点的线性系统： ｘ · ＝ Ａｘ ＋ Ｂｕ （１） 式中：ｘ ＝ ｘ１ ｘ２…ｘｎ [ ] Ｔ 表示系统的状态，Ａ∈Ｒ ｎ×ｎ是 系统的邻接矩阵，Ｂ∈Ｒ ｎ×ｍ是控制矩阵，ｕ∈Ｒ ｍ×ｎ是输 入矩阵。 由于讨论的是无向图，所以 Ａ 是对称矩 阵。 对任一给定的初始状态，如果存在一个控制输 入 ｕ ，使式（１）能在有限时间间隔内，从初始状态转 移到任意指定的终端状态，则称该系统是可控的。 目前，有许多判别线性系统可控的方法，例如 Ｇｒａｍ 矩阵判据、ＰＢＨ 判据［２２］ 、秩判据等。 本文从 ＰＢＨ 判 据出发，分析系统的可控性，进而得到系统可控的充 要条件。 引理 １ 系统（１）可控的充要条件是不存在非 零的向量 ｖ 满足以下等式： Ａｖ ＝ λｖ Ｂ Ｔ ｖ ＝ ０ { 若存在向量 ｖ 使得上面的等式成立，则称相应 的 λ 是系统不可控的特征值。 证明 根据 ＰＢＨ 判据并结合 Ａ 的对称性即知 结论成立。 ２ 主要结论 本节将首先对邻接矩阵进行分解，基于此给出 子矩阵特征值的表达形式，然后，通过所提出的矩阵 特征值之间的关系，得出相应的引理与定理。 ２．１ 邻接矩阵的分解 Ｂ 矩阵的具体表达与一系列的控制节点相对 应，如果 Ｉｃ ＝ ｉ １ ，ｉ ２ ，…，ｉｍ { } ，则 Ｂ ＝ ｅｉ１ ｅｉ２… ｅｉｍ [ ] 。 ·５７８· 智 能 系 统 学 报 第 １０ 卷
第4期 晁永翠，等：复杂网络在路形拓扑结构下可控的充要条件 .579. 由引理1可知，路图不可控意味着存在非零向量y 入51-52=0 满足Ay=Ay,且B'v=0。矩阵M,定义如下： -5-1+入5，-5+1=0， 2≤l≤n-1 「01 -5m-1+入5n=0 10 当，=0时，52=专3=…=专n=0,即专为零向量，这 M, 与专是特征向量矛盾。同理可证专。≠0。矩阵M, 0 的情况同样证明。 10 引理3对于矩阵M,有 式中v是矩阵的维数。 1)矩阵M.的特征值的形式为 因为B=[e,e…e],由Bv=0可得向量v 0+19=1,2,…,y λ=2c0 qT 的第i个向量元素为零，即()，=0，i.e1。因 此，在Av=入v中，A可分解为 2)矩阵M,的特征值必是矩阵M。1的特征 0 值，其中a∈N。 证明1)可由文献[18]附加材料中关于路图 M-1 0 0 的例子得到。2)可由矩阵M,特征值的表达形式 1 得到。 0…01010 …00 2.2路图的可控性 1 将引理1与引理2结合可知，路图的每一个外 0 节点为控制节点时，路图是可控的)。然而，当控 0…0 M21 制节点为路图的内节点时，其能控性如何，是更值得 0 探讨的问题，这也是本节欲解决的问题。首先给出 以下两个引理，其中，第一个引理是关于单个控制节 0…0 0 00 M 点的情况。 向量v可分解为 引理4对控制节点为r∈{2,3，…，n-1}的 (1)1 长度为n的路图，当且仅当矩阵M,-与Mn-没有相 同的特征值时，路图是可控的。此外，矩阵M-1与 (1)-1 M,相同的特征值为矩阵A在控制节点为r时，系 统不可控的特征值。 0 证明为了简便，证其逆否命题。由PBH判 y= (2)1 据，当且仅当 Ay=λv (2) (w2)2-i- 且e,v=0时，路图是不可控的。由e,v=0得 v=[0]T (m+i)n-im」 式中：y1∈R-1,y2∈R。代入式(2)得 由Av=Ay可得 M,-1y1=Av1 M-1·V1=Ay1 ()-1+(2)1=0 (u1),-1+(2)1=0 M-,v2=Av2 (3) M2--l·v2=A 所以，系统不能控当且仅当不存在A的一个特征向 量v使得式(3)成立。 (a）a-a-1+(uai）1=0 充分性若入。为M-,与M.-,的共同特征值，且 Mn-n·va+1=Ava+l 对应的特征向量分别为与0。令 式中：v。是向量y的第σ个分块向量，σ∈N。 v=[vo 0 pv]T 引理2矩阵A与矩阵M,的特征向量的第一 式中：p∈R,(vo)-1+(pv20)1=0,则可验证v满足式 个元素与最后一个元素都不为0。 (3),其中入=入。所以系统不能控。 证明设入为A的一个特征值，对应的特征向 必要性假设系统不能控，则由式(3)且"1≠ 量为专=[店，专2…专]，由A5=入5可得 0,2≠0得，入为矩阵M-与Mn-的共同特征值
由引理 １ 可知，路图不可控意味着存在非零向量 ｖ 满足 Ａｖ ＝λｖ，且 Ｂ Ｔ ｖ ＝ ０。 矩阵 Ｍν 定义如下： Ｍν ＝ ０ １ １ ０ １ ⋱ ⋱ ⋱ １ ０ １ １ ０ é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú 式中 ν 是矩阵的维数。 因为 Ｂ ＝ ｅｉ１ ｅｉ２… ｅｉｍ [ ] ，由 Ｂ Ｔ ｖ ＝ ０ 可得向量 ｖ 的第 ｉ ｃ 个向量元素为零，即 （ｖ）ｉ ｃ ＝ ０， ｉ ｃ ∈ Ｉｃ 。 因 此，在 Ａｖ ＝λｖ 中，Ａ 可分解为 Ｍｉ１ －１ ０ ︙ ０ １ … ０ ０ … ０ １ ０ １ ０ … ０ ０ ０ … ０ １ ０ ︙ ０ Ｍｉ２ －１ ︙ ︙ ︙ ⋱ ︙ ０ … ０ ０ ０ … ０ Ｍｎ－ｉｍ é ë ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ù û ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú 向量 ｖ 可分解为 ｖ ＝ ｖ１ ( ) １ ︙ ｖ１ ( ) ｉ１ －１ ０ ｖ２ ( ) １ ︙ ｖ２ ( ) ｉ２ －ｉ１ －１ ︙ ｖｍ＋１ ( ) ｎ－ｉｍ é ë ê ê ê ê ê ê ê ê ê ê ê ê ê ê ù û ú ú ú ú ú ú ú ú ú ú ú ú ú ú 由 Ａｖ ＝λｖ 可得 Ｍｉ１ －１·ｖ１ ＝ λｖ１ ｖ１ ( ) ｉ１ －１ ＋ ｖ２ ( ) １ ＝ ０ Ｍｉ２ －ｉ１ －１·ｖ２ ＝ λｖ２ ︙ ｖｍ ( ) ｉｍ －ｉｍ－１ －１ ＋ ｖｍ＋１ ( ) １ ＝ ０ Ｍｎ－ｉｍ·ｖｍ＋１ ＝ λｖｍ＋１ 式中：ｖσ 是向量 ｖ 的第 σ 个分块向量， σ ∈ℕ 。 引理 ２ 矩阵 Ａ 与矩阵 Ｍν 的特征向量的第一 个元素与最后一个元素都不为 ０。 证明 设 λ 为 Ａ 的一个特征值，对应的特征向 量为 ξ ＝ ξ１ ξ２… ξｎ [ ] Ｔ ，由 Ａξ ＝λξ 可得 λξ１ － ξ２ ＝ ０ － ξｌ－１ ＋ λξｌ － ξｌ＋１ ＝ ０， ２ ≤ ｌ ≤ ｎ － １ － ξｎ－１ ＋ λξｎ ＝ ０ 当 ξ１ ＝ ０ 时， ξ２ ＝ ξ３ ＝ … ＝ ξｎ ＝ ０，即 ξ 为零向量，这 与 ξ 是特征向量矛盾。 同理可证 ξｎ≠０。 矩阵 Ｍν 的情况同样证明。 引理 ３ 对于矩阵 Ｍν，有 １）矩阵 Ｍν 的特征值的形式为 λ ＝ ２ｃｏｓ ｑπ ν ＋ １ ，ｑ ＝ １，２，…，ν ２） 矩阵 Ｍν 的特征值必是矩阵 Ｍαν＋α－１的特征 值，其中 α∈ℕ 。 证明 １）可由文献［１８］附加材料中关于路图 的例子得到。 ２） 可由矩阵 Ｍν 特征值的表达形式 得到。 ２．２ 路图的可控性 将引理 １ 与引理 ２ 结合可知，路图的每一个外 节点为控制节点时，路图是可控的［２３］ 。 然而，当控 制节点为路图的内节点时，其能控性如何，是更值得 探讨的问题，这也是本节欲解决的问题。 首先给出 以下两个引理，其中，第一个引理是关于单个控制节 点的情况。 引理 ４ 对控制节点为 ｒ ∈ {２，３，…，ｎ － １} 的 长度为 ｎ 的路图，当且仅当矩阵 Ｍｒ－１与 Ｍｎ－ｒ没有相 同的特征值时，路图是可控的。 此外，矩阵 Ｍｒ－１ 与 Ｍｎ－ｒ相同的特征值为矩阵 Ａ 在控制节点为 ｒ 时，系 统不可控的特征值。 证明 为了简便，证其逆否命题。 由 ＰＢＨ 判 据，当且仅当 Ａｖ ＝ λｖ （２） 且 ｅ Ｔ ｒ ｖ ＝ ０ 时，路图是不可控的。 由 ｅ Ｔ ｒ ｖ ＝ ０ 得 ｖ ＝ ［ｖ Ｔ １ ０ ｖ Ｔ ２ ］ Ｔ 式中：ｖ１∈Ｒ ｒ－１ ，ｖ２∈Ｒ ｎ－ｒ 。 代入式（２）得 Ｍｒ－１ ｖ１ ＝ λｖ１ ｖ１ ( ) ｒ－１ ＋ ｖ２ ( ) １ ＝ ０ Ｍｎ－ｒ ｖ２ ＝ λｖ２ （３） 所以，系统不能控当且仅当不存在 Ａ 的一个特征向 量 ｖ 使得式（３）成立。 充分性 若 λ０ 为 Ｍｒ－１与 Ｍｎ－ｒ的共同特征值，且 对应的特征向量分别为 ｖ１０与 ｖ２０ 。 令 ｖ ＝ ［ｖ Ｔ １０ ０ ρｖ Ｔ ２０ ］ Ｔ 式中：ρ∈Ｒ， ｖ１０ ( ) ｒ－１ ＋ ρｖ２０ ( ) １ ＝ ０，则可验证 ｖ 满足式 （３），其中 λ ＝ λ０ 。 所以系统不能控。 必要性 假设系统不能控，则由式（３）且 ｖ１≠ ０，ｖ２≠０ 得， λ 为矩阵 Ｍｒ－１与 Ｍｎ－ｒ的共同特征值。 第 ４ 期 晁永翠，等：复杂网络在路形拓扑结构下可控的充要条件 ·５７９·
·580· 智能系统学报 第10卷 此外，假设入1是M,与M,共同的特征值，则 存在一个如上的非零向量v=[v。0p]T满足Av= 91=41,9=4,时，等式4-2成立，即为式(5)的形 ch ct2 Av,e,v=0。因此入1是系统不可控的特征值。 式，则式(4)成立。即矩阵M,,与M,有相同的特 引理4回答了控制节点为一个时，路图可控的 征值。所以路图是不可控的。 充要条件，以下这个引理则给出了受控节点为多个 对陈述2)，证其逆否命题。引理5与引理3结 时，路图可控的充要条件。 合，取子矩阵的特征值。接下来的证明与陈述1)中 引理5控制节点1。={i,i2,…,im}C 的相似。最后即可得到陈述2)中的结论。 {1,2,…,n}长度为n的路图，当且仅当矩阵M-1, 由定理1中陈述1)同样也可得到当控制节点 M--1,…,Mn没有相同的特征值时，路图是可控 为外节点时路图是可控的这一结论。具体如下：控 的。此外，矩阵共同的特征值为邻接矩阵A在控制 制节点r=1或n时，根据陈述1)可得G(1,n)=1或 节点为1时，系统不可控的特征值。 G(n,1)=1,因为1与任何数都互质，可得当控制节 引理5的证明与引理4类似，此处不再赘述。 点为外节点时路图是可控的。当控制节点？=2或 为了更清晰地表达以上关于可控性的条件，下 n-2时，由陈述1)可知，需判断2与n-1是否互 面利用特征值的特殊形式与最大公约数理论，进一 质。当n-1奇数，即n为偶数时，2与n-1互质， 步给出路图可控的充分必要条件。 路图可控：反之，路图不可控。可表述为以下推论。 定理1对于一个长度为n的路图，有以下 推论1对于一个长度为n的路图，当控制节 点r为外节点的邻接点时，若n为偶数时，则路图是 陈述： 1)当控制节点为r∈{2,3，…，n-1}时，路图 可控的：若n为奇数时，则路图不可控。 由定理1中陈述1)还可推出一些简便的判别 可控的充分必要条件为 路图可控性的方法。例如，当控制节点r=n/2(r= G(r,n-r+1)=1 2)当控制节点集I。={i1,i2,…,in}C (n+2)/2)且n为偶数时，路图是可控的。这是因 {1,2,…,n}时，路图可控的充分必要条件为 为当r=n/2,n-r+1=n/2+1(r=(n+2)/2, n-r+1=n/2),整数r与n-r+1为相邻的2个 G(i1,i2-i1,…,im-im-1,n-im+1)=1 数。我们知道，相邻的2个数肯定是互质的，所以路 证明 图是可控的。当n为奇数且r为偶数时，路图不可 充分性证其逆否命题，由引理4可知，当矩 控。因为当n为奇数r为偶数时，n-r+1为偶数 阵M-,与M,有相同的特征值时，路图不完全可 即G(r,n-r+1)>1,路图不可控。 控。结合引理3可得 定理2对于一个长度为n的路图，若n可分 91T 92T 2co-1）+1=2co87 解为n=mp+m+p,其中m,p∈N,则当控制节点 (n-r)+1 (4) 集为={kp+1))x,m;时，路图是不可控 式中：91∈{1,2，…，(r-1)},92∈ 的，其中K∈{1,2，…，m}。此外，假设K的取值从 {1,2,…,(n-r)}。由于q1与92取自这2个特定 小到大依次为b,b2,…,b,(s≤m),则系统有以下 集合，式(4)等式两边余弦内的数值都小于π，得 不可控的特征值 91T 92T (r-1)+1(n-r)+1 λ=2c0s p+1)9∈1,2，…，即+B-1) 化简为 (6) (5) 式中：B=min{b1,bk-b-1,m-b,+1},k∈ r n-r+l {2,3,…,s}。 又由于9，与92的取值限制，使得式(5)成立的条件 证明当n=mp+m+p时，控制节点集为= 是整数r与n-r+1不互质，即 {x+1)}x1,2,m;,即为定理1陈述2)中所有 G(r,n-r+1)>1 不可控的控制节点的集合。当整数p的取值不同 必要性证其逆否命题，当G(r,n-r+1)> 时，即可得到不同的不可控的控制节点集。当B= 1时，则存在正整数c,t1,t2,使得ct1=r,ct2=n- min{b1,be-bk-1,m-b,+1},k∈{2,3，，s}, r+1,其中t1<r,t2<n-r+1。又有91∈ 邻接矩阵A被分解为2种形式的子矩阵，即 {1,2,…,(-1)},92∈{1,2，…，(n-)},则当Mg+)-与Me)o+-1u∈N)。子矩阵的共同
此外，假设 λ１ 是 Ｍｒ－１与 Ｍｎ－ｒ共同的特征值，则 存在一个如上的非零向量 ｖ ＝ ［ｖ Ｔ １０ ０ ρｖ Ｔ ２０ ］ Ｔ 满足Ａｖ ＝ λｖ，ｅ Ｔ ｒ ｖ ＝ ０。 因此 λ１ 是系统不可控的特征值。 引理 ４ 回答了控制节点为一个时，路图可控的 充要条件，以下这个引理则给出了受控节点为多个 时，路图可控的充要条件。 引 理 ５ 控 制 节 点 Ｉｃ ＝ ｉ １ ，ｉ ２ ，…，ｉｍ { } ⊂ {１，２，…，ｎ}长度为 ｎ 的路图，当且仅当矩阵 Ｍｉ１ －１ ， Ｍｉ２ －ｉ１ －１ ，…，Ｍｎ－ｉｍ没有相同的特征值时，路图是可控 的。 此外，矩阵共同的特征值为邻接矩阵 Ａ 在控制 节点为 Ｉｃ 时，系统不可控的特征值。 引理 ５ 的证明与引理 ４ 类似，此处不再赘述。 为了更清晰地表达以上关于可控性的条件，下 面利用特征值的特殊形式与最大公约数理论，进一 步给出路图可控的充分必要条件。 定理 １ 对于一个长度为 ｎ 的路图，有以下 陈述： １）当控制节点为 ｒ ∈ {２，３，…，ｎ － １} 时，路图 可控的充分必要条件为 Ｇ(ｒ，ｎ － ｒ ＋ １) ＝ １ ２ ） 当 控 制 节 点 集 Ｉｃ ＝ ｉ １ ，ｉ ２ ，…，ｉｍ { } ⊂ {１，２，…，ｎ} 时，路图可控的充分必要条件为 Ｇ ｉ １ ，ｉ ２ － ｉ １ ，…，ｉｍ － ｉｍ－１ ，ｎ － ｉｍ ( ＋ １) ＝ １ 证明 充分性 证其逆否命题，由引理 ４ 可知，当矩 阵 Ｍｒ－１与 Ｍｎ－ｒ 有相同的特征值时，路图不完全可 控。 结合引理 ３ 可得 ２ｃｏｓ ｑ１π (ｒ － １) ＋ １ ＝ ２ｃｏｓ ｑ２π (ｎ － ｒ) ＋ １ （４） 式 中： ｑ１ ∈ {１，２，…，(ｒ － １) } ， ｑ２ ∈ {１，２，…，(ｎ － ｒ) } 。 由于 ｑ１ 与 ｑ２ 取自这 ２ 个特定 集合，式（４）等式两边余弦内的数值都小于 π，得 ｑ１π (ｒ － １) ＋ １ ＝ ｑ２π (ｎ － ｒ) ＋ １ 化简为 ｑ１ ｒ ＝ ｑ２ ｎ － ｒ ＋ １ （５） 又由于 ｑ１ 与 ｑ２ 的取值限制，使得式（５）成立的条件 是整数 ｒ 与 ｎ － ｒ ＋ １ 不互质，即 Ｇ(ｒ，ｎ － ｒ ＋ １) ＞ １ 必要性 证其逆否命题，当 Ｇ(ｒ，ｎ － ｒ ＋ １) ＞ １ 时，则存在正整数 ｃ ， ｔ １ ， ｔ ２ ，使得 ｃｔ １ ＝ ｒ ， ｃｔ ２ ＝ ｎ － ｒ ＋ １，其中 ｔ １ ＜ ｒ ， ｔ ２ ＜ ｎ － ｒ ＋ １。 又有 ｑ１ ∈ {１，２，…，(ｒ － １) } ， ｑ２ ∈ {１，２，…，(ｎ － ｒ) } ，则当 ｑ１ ＝ ｔ １ ， ｑ２ ＝ ｔ ２ 时，等式 ｑ１ ｃｔ １ ＝ ｑ２ ｃｔ ２ 成立，即为式（５）的形 式，则式（４）成立。 即矩阵 Ｍｒ－１与 Ｍｎ－ｒ有相同的特 征值。 所以路图是不可控的。 对陈述 ２），证其逆否命题。 引理 ５ 与引理 ３ 结 合，取子矩阵的特征值。 接下来的证明与陈述 １）中 的相似。 最后即可得到陈述 ２）中的结论。 由定理 １ 中陈述 １）同样也可得到当控制节点 为外节点时路图是可控的这一结论。 具体如下：控 制节点 ｒ ＝ １ 或 ｎ 时，根据陈述 １）可得 Ｇ(１，ｎ) ＝ １ 或 Ｇ(ｎ，１) ＝ １，因为 １ 与任何数都互质，可得当控制节 点为外节点时路图是可控的。 当控制节点 ｒ ＝ ２ 或 ｎ －２ 时，由陈述 １）可知，需判断 ２ 与 ｎ － １ 是否互 质。 当 ｎ － １ 奇数，即 ｎ 为偶数时，２ 与 ｎ － １ 互质， 路图可控；反之，路图不可控。 可表述为以下推论。 推论 １ 对于一个长度为 ｎ 的路图，当控制节 点 ｒ 为外节点的邻接点时，若 ｎ 为偶数时，则路图是 可控的；若 ｎ 为奇数时，则路图不可控。 由定理 １ 中陈述 １）还可推出一些简便的判别 路图可控性的方法。 例如，当控制节点 ｒ ＝ ｎ ／ ２（ ｒ ＝ （ｎ ＋ ２） ／ ２）且 ｎ 为偶数时，路图是可控的。 这是因 为当 ｒ ＝ ｎ ／ ２， ｎ － ｒ ＋ １ ＝ ｎ ／ ２ ＋ １（ ｒ ＝ （ｎ ＋ ２） ／ ２， ｎ － ｒ ＋ １ ＝ ｎ ／ ２），整数 ｒ 与 ｎ － ｒ ＋ １ 为相邻的 ２ 个 数。 我们知道，相邻的 ２ 个数肯定是互质的，所以路 图是可控的。 当 ｎ 为奇数且 ｒ 为偶数时，路图不可 控。 因为当 ｎ 为奇数 ｒ 为偶数时， ｎ － ｒ ＋ １ 为偶数， 即 Ｇ(ｒ，ｎ － ｒ ＋ １) ＞ １，路图不可控。 定理 ２ 对于一个长度为 ｎ 的路图，若 ｎ 可分 解为 ｎ ＝ ｍｐ ＋ ｍ ＋ ｐ ，其中 ｍ，ｐ ∈ℕ ，则当控制节点 集为 Ｉ ｐｍ ｃ ＝ {κ(ｐ ＋ １) } κ∈{１，…，ｍ} 时，路图是不可控 的，其中 κ ∈ {１，２，…，ｍ} 。 此外，假设 κ 的取值从 小到大依次为 ｂ１ ，ｂ２ ，…，ｂｓ (ｓ ≤ ｍ) ，则系统有以下 不可控的特征值 λ ＝ ２ｃｏｓ ｑπ β(ｐ ＋ １) ，ｑ ∈ {１，２，…，βｐ ＋ β － １} （６） 式 中： β ＝ ｍｉｎ ｂ１ ，ｂｋ － ｂｋ－１ ，ｍ － ｂｓ { ＋ １ } ， ｋ ∈ {２，３，…，ｓ} 。 证明 当 ｎ ＝ ｍｐ ＋ ｍ ＋ ｐ 时，控制节点集为 Ｉ ｐｍ ｃ ＝ {κ(ｐ ＋ １) } κ∈{１，２，…，ｍ} ，即为定理 １ 陈述 ２）中所有 不可控的控制节点的集合。 当整数 ｐ 的取值不同 时，即可得到不同的不可控的控制节点集。 当 β ＝ ｍｉｎ ｂ１ ，ｂｋ － ｂｋ－１ ，ｍ － ｂｓ { ＋ １ } ， ｋ ∈ {２，３，…，ｓ} ， 邻接 矩 阵 Ａ 被 分 解 为 ２ 种 形 式 的 子 矩 阵， 即 Ｍβ (ｐ＋１ ) －１与 Ｍ(β＋μ ) (ｐ＋１ ) －１ (μ∈ℕ ) 。 子矩阵的共同 ·５８０· 智 能 系 统 学 报 第 １０ 卷
第4期 晁永翠，等：复杂网络在路形拓扑结构下可控的充要条件 ·581. 特征值即为最小的子矩阵M(p1)-特征值的部分 部特征值。若控制节点为节点6时，A可被分解为 或全部。即为式(6)表达的形式。若存在一个正整 M与Ms两种形式的子矩阵，矩阵M,与M。的共 数y使以=B,则不可控的特征值为最小的子矩阵 同特征值即为矩阵M,的部分特征值。 M+D-的全部特征值，即 3结束语 B0+1)9={1,2,…,+B-1} qT λ=2c0 本文给出了判断复杂网络系统中路图可控性的 为了更清晰地理解定理2，以下给出一个较为 方法，把PBH判据与对称的邻接矩阵相结合，得到 直观的解释。当p与m固定时，对控制节点集m中 了路图可控的充要条件，并应用数学中的简单理论， 的节点给与相同的标记。把全部的节点用m个控 对于路图可控性的充要条件进行了更为数字化的表 制节点分为m+1份，每份的节点数为p个（除控制 示。在此基础上，提出了系统不可控的特征值的表 节点外)。但事实上，在选取控制节点时未必选择 达形式。同理，可推出环图可控性的充要条件。本 集合内的所有的节点为控制节点，所以有定理2 文通过对路图的每个节点进行分析，进而判断可控 中所述，不可控的特征值为邻接矩阵A中被分解的 性，使得直接从图的结构形式判断能控性成为可能。 最小的子矩阵Ma1)-1的特征值的部分或全部。 本文对于路图可控性的研究方法和结果，为以后研 2.3实例分析 究更为复杂的图拓扑结构的可控性提供了一个方向 以下给出2个例子。n=11与n=14的路图，分 和基础。 别如图1中与图2所示。 参考文献： [1]KAMLAN R E.Mathematical description of linear dynamical systems[J].Journal of the Society for Industrial and Ap- 6 plied Mathematics Series A:Control,1963,1(2):152- 192. [2]NOTARSTEFANO G,PARLANGELI G.Controllability and observability of grid graphs via reduction and symmetries 10 9 [J].IEEE Transactions on Automatic Control,2013,58 图1n=11的路图 (7):1719-1731. Fig.1 The path graph with n=11 3]JI Zhijian,LIN Hai,YU Haisheng.Protocols design and 在图1中，横线标记的节点是控制节点为 uncontrollable topologies construction for multi-agent net- 的集合，其中P1=1,m1=5。竖线标记的节点是控 works[J].IEEE Transactions on Automatic Control,2014, 制节点为22的集合，其中P2=2,m2=3。当控制 60(3):781-786. 节点为时，系统有相同的不可控的特征值 [4]JI Zhijian,LIN Hai,YU Haisheng.Leaders in multi-agent 入=0，而1与-1为系统在控制节点集为？时2 controllability under consensus algorithm and tree topology 个不可控的特征值。 [J].Systems Control Letters,2012,61(9):918-925. [5]JI Zhijian,WANG Zidong,LIN Hai,et al.Interconnection topologies for multi-agent coordination under leader-follower framework[J].Automatica,2009,45(12):2857-2863. [6]RAHMANI A,JI Meng,MESBAHI M,et al.Controllability of multi-agent systems from a graph-theoretic perspective [J].SIAM Journal on Control and Optimization,2009,48 (1):162-186. [7]GUAN Yongqiang,JI Zhijian,ZHANG Lin,et al.Decen- 图2n=14的路图 tralized stabilizability of multi-agent systems under fixed and Fig.2 The path graph with n=14 switching topologies[J].Systems Control Letters,2013, 在图2中，斜线标记的节点是控制节点为 62(5):438-446. 的集合，其中p=2,m=4。当控制节点为节点3和 [8]KIM H,SHIM H,BACK J,et al.Stabilizability of a group of single integrators and its application to decentralized for- 节点9时，A可被分解为M2与M,两种形式的子矩 mation problem[C]/Proceedings of the 50th IEEE Con- 阵，矩阵M2与M的共同特征值即为矩阵M2的全 ference on Decision and Control and European Control Con-
特征值即为最小的子矩阵 Ｍβ (ｐ＋１ ) －１特征值的部分 或全部。 即为式（６）表达的形式。 若存在一个正整 数 ｙ 使 μ ＝ ｙβ ，则不可控的特征值为最小的子矩阵 Ｍβ (ｐ＋１ ) －１的全部特征值，即 λ ＝ ２ｃｏｓ ｑπ β(ｐ ＋ １) ，ｑ ＝ {１，２，…，βｐ ＋ β － １} 为了更清晰地理解定理 ２，以下给出一个较为 直观的解释。 当 ｐ 与 ｍ 固定时，对控制节点集 Ｉ ｐｍ ｃ 中 的节点给与相同的标记。 把全部的节点用 ｍ 个控 制节点分为 ｍ ＋ １ 份，每份的节点数为 ｐ 个（除控制 节点外）。 但事实上，在选取控制节点时未必选择 集合 Ｉ ｐｍ ｃ 内的所有的节点为控制节点，所以有定理 ２ 中所述，不可控的特征值为邻接矩阵 Ａ 中被分解的 最小的子矩阵 Ｍβ (ｐ＋１ ) －１的特征值的部分或全部。 ２．３ 实例分析 以下给出 ２ 个例子。 ｎ ＝ １１ 与 ｎ ＝ １４ 的路图，分 别如图 １ 中与图 ２ 所示。 图 １ ｎ ＝ １１ 的路图 Ｆｉｇ．１ Ｔｈｅ ｐａｔｈ ｇｒａｐｈ ｗｉｔｈ ｎ ＝ １１ 在图 １ 中，横线标记的节点是控制节点为 Ｉ ｐ１ｍ１ ｃ 的集合，其中 ｐ１ ＝ １，ｍ１ ＝ ５。 竖线标记的节点是控 制节点为 Ｉ ｐ２ｍ２ ｃ 的集合，其中 ｐ２ ＝ ２，ｍ２ ＝ ３。 当控制 节点为 Ｉ ｐ１ｍ１ ｃ 时， 系 统 有 相 同 的 不 可 控 的 特 征 值 λ ＝ ０， 而 １ 与－１ 为系统在控制节点集为 Ｉ ｐ２ｍ２ ｃ 时 ２ 个不可控的特征值。 图 ２ ｎ ＝ １４ 的路图 Ｆｉｇ．２ Ｔｈｅ ｐａｔｈ ｇｒａｐｈ ｗｉｔｈ ｎ ＝ １４ 在图 ２ 中，斜线标记的节点是控制节点为 Ｉ ｐｍ ｃ 的集合，其中 ｐ ＝ ２，ｍ ＝ ４。 当控制节点为节点 ３ 和 节点 ９ 时，Ａ 可被分解为 Ｍ２ 与 Ｍ５ 两种形式的子矩 阵，矩阵 Ｍ２ 与 Ｍ５ 的共同特征值即为矩阵 Ｍ２ 的全 部特征值。 若控制节点为节点 ６ 时，Ａ 可被分解为 Ｍ５ 与 Ｍ８ 两种形式的子矩阵，矩阵 Ｍ５ 与 Ｍ８ 的共 同特征值即为矩阵 Ｍ５ 的部分特征值。 ３ 结束语 本文给出了判断复杂网络系统中路图可控性的 方法，把 ＰＢＨ 判据与对称的邻接矩阵相结合，得到 了路图可控的充要条件，并应用数学中的简单理论， 对于路图可控性的充要条件进行了更为数字化的表 示。 在此基础上，提出了系统不可控的特征值的表 达形式。 同理，可推出环图可控性的充要条件。 本 文通过对路图的每个节点进行分析，进而判断可控 性，使得直接从图的结构形式判断能控性成为可能。 本文对于路图可控性的研究方法和结果，为以后研 究更为复杂的图拓扑结构的可控性提供了一个方向 和基础。 参考文献： ［１］ＫＡＭＬＡＮ Ｒ Ｅ． Ｍａｔｈｅｍａｔｉｃａｌ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｌｉｎｅａｒ ｄｙｎａｍｉｃａｌ ｓｙｓｔｅｍｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ｓｏｃｉｅｔｙ ｆｏｒ Ｉｎｄｕｓｔｒｉａｌ ａｎｄ Ａｐ⁃ ｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ Ｓｅｒｉｅｓ Ａ： Ｃｏｎｔｒｏｌ， １９６３， １ （ ２）： １５２⁃ １９２． ［２］ＮＯＴＡＲＳＴＥＦＡＮＯ Ｇ， ＰＡＲＬＡＮＧＥＬＩ Ｇ． Ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ａｎｄ ｏｂｓｅｒｖａｂｉｌｉｔｙ ｏｆ ｇｒｉｄ ｇｒａｐｈｓ ｖｉａ ｒｅｄｕｃｔｉｏｎ ａｎｄ ｓｙｍｍｅｔｒｉｅｓ ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ， ２０１３， ５８ （７）： １７１９⁃１７３１． ［３］ ＪＩ Ｚｈｉｊｉａｎ， ＬＩＮ Ｈａｉ， ＹＵ Ｈａｉｓｈｅｎｇ． Ｐｒｏｔｏｃｏｌｓ ｄｅｓｉｇｎ ａｎｄ ｕｎｃｏｎｔｒｏｌｌａｂｌｅ ｔｏｐｏｌｏｇｉｅｓ ｃｏｎｓｔｒｕｃｔｉｏｎ ｆｏｒ ｍｕｌｔｉ⁃ａｇｅｎｔ ｎｅｔ⁃ ｗｏｒｋｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ， ２０１４， ６０（３）： ７８１⁃７８６． ［４］ＪＩ Ｚｈｉｊｉａｎ， ＬＩＮ Ｈａｉ， ＹＵ Ｈａｉｓｈｅｎｇ． Ｌｅａｄｅｒｓ ｉｎ ｍｕｌｔｉ⁃ａｇｅｎｔ ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｕｎｄｅｒ ｃｏｎｓｅｎｓｕｓ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｒｅｅ ｔｏｐｏｌｏｇｙ ［Ｊ］． Ｓｙｓｔｅｍｓ ＆ Ｃｏｎｔｒｏｌ Ｌｅｔｔｅｒｓ， ２０１２， ６１（９）： ９１８⁃９２５． ［５］ＪＩ Ｚｈｉｊｉａｎ， ＷＡＮＧ Ｚｉｄｏｎｇ， ＬＩＮ Ｈａｉ， ｅｔ ａｌ． Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ ｔｏｐｏｌｏｇｉｅｓ ｆｏｒ ｍｕｌｔｉ⁃ａｇｅｎｔ ｃｏｏｒｄｉｎａｔｉｏｎ ｕｎｄｅｒ ｌｅａｄｅｒ⁃ｆｏｌｌｏｗｅｒ ｆｒａｍｅｗｏｒｋ［Ｊ］． Ａｕｔｏｍａｔｉｃａ， ２００９， ４５（１２）： ２８５７⁃２８６３． ［６］ＲＡＨＭＡＮＩ Ａ， ＪＩ Ｍｅｎｇ， ＭＥＳＢＡＨＩ Ｍ， ｅｔ ａｌ． Ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｏｆ ｍｕｌｔｉ⁃ａｇｅｎｔ ｓｙｓｔｅｍｓ ｆｒｏｍ ａ ｇｒａｐｈ⁃ｔｈｅｏｒｅｔｉｃ ｐｅｒｓｐｅｃｔｉｖｅ ［Ｊ］． ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｎｔｒｏｌ ａｎｄ Ｏｐｔｉｍｉｚａｔｉｏｎ， ２００９， ４８ （１）： １６２⁃１８６． ［７］ＧＵＡＮ Ｙｏｎｇｑｉａｎｇ， ＪＩ Ｚｈｉｊｉａｎ， ＺＨＡＮＧ Ｌｉｎ， ｅｔ ａｌ． Ｄｅｃｅｎ⁃ ｔｒａｌｉｚｅｄ ｓｔａｂｉｌｉｚａｂｉｌｉｔｙ ｏｆ ｍｕｌｔｉ⁃ａｇｅｎｔ ｓｙｓｔｅｍｓ ｕｎｄｅｒ ｆｉｘｅｄ ａｎｄ ｓｗｉｔｃｈｉｎｇ ｔｏｐｏｌｏｇｉｅｓ［Ｊ］． Ｓｙｓｔｅｍｓ ＆ Ｃｏｎｔｒｏｌ Ｌｅｔｔｅｒｓ， ２０１３， ６２（５）： ４３８⁃４４６． ［８］ＫＩＭ Ｈ， ＳＨＩＭ Ｈ， ＢＡＣＫ Ｊ， ｅｔ ａｌ． Ｓｔａｂｉｌｉｚａｂｉｌｉｔｙ ｏｆ ａ ｇｒｏｕｐ ｏｆ ｓｉｎｇｌｅ ｉｎｔｅｇｒａｔｏｒｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｄｅｃｅｎｔｒａｌｉｚｅｄ ｆｏｒ⁃ ｍａｔｉｏｎ ｐｒｏｂｌｅｍ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５０ｔｈ ＩＥＥＥ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ ｏｎ Ｄｅｃｉｓｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ ａｎｄ Ｅｕｒｏｐｅａｎ Ｃｏｎｔｒｏｌ Ｃｏｎ⁃ 第 ４ 期 晁永翠，等：复杂网络在路形拓扑结构下可控的充要条件 ·５８１·
.582. 智能系统学报 第10卷 ference.Orlando,USA,2011:4829-4834. IEEE Transactions on Automatie Control,2012,57(3): [9]SABATTINI L,SECCHI C,FANTNZZI C.Controllability 743-748.20]PARLANGELI G,NOTARSTEFANO G. and observability preservation for networked systems with On the observability of path and cycle time varying topologies [C]//Proceedings of the 19th graphs C]//Proceedings of the 49th World Congress on the International Federation of Automatic IEEE Conference on Decision and Control. Control.Cape Town,South Africa,2014:1837-1842. Atlanta,USA,2010:1492-1497. [10]MESBAHI M,EGERSTEDT M.Graph Theoretie Methods [21]CHARTRAND G,ZHANG Ping.图论导引[M.范益政， in Multiagent Networks[M].Princeton:Princeton Univer- 等译.北京：人民邮电出版社，2007：1-17. 8 sity Pres8s,2010:117-151. [22]TANNER H G.On the controllability of nearest neighbor [11]SUNDARAM S,HADJICOSTIS C N.Distributed function interconnections[C]//Proceedings of the 43rd IEEE calculation via linear iterative strategies in the presence of Conference on Decision and Control.Nassau,Bahamas, malicious agents [J].IEEE Transactions on Automatic 2004:2467-2472. Control,2011,56(7):1495-1508. [23]PARLANGELI G.NOTARSTEFANO G.Graph reduction [12]PASQUALETTI F,BICCHI A,BULLO F.Consensus com- based observability conditions for network systems running putation in unreliable networks:A system theoretic ap- average consensus algorithms [C]//Proceedings of the proach[J].IEEE Transactions on Automatic Control, 18th Mediterranean Conference on Control and Automation 2012,57(1):90-104. Marrakesh,Morocco,2010:689-694. [13]LI Zhongkui,REN Wei,LIU Xiangdong,et al.Distribu- 作者简介： ted containment control of multi-agent systems with general 晁永翠，女，1990年生，硕士研究生， linear dynamies in the presence of multiple leaders[J.In- 主要研究方向为复杂网络的可控性。 ternational Journal of Robust and Nonlinear Control,2013, 23(5):534-547. [14]FARINA M,FERRARI-TRECATE G.SCATTOLINI R.A moving horizon scheme for distributed state estimation [C]//Proceedings of the 48th IEEE Conference on Deci- 纪志坚，男，1973年生，教授，博士 sion and Control.Shanghai,China,2009:1818-1823. 生导师，博士，主要研究方向为群体系 [15]JI Zhijian,WANG Zidong,LIN Hai,et al.Controllability 统动力学与协调控制、复杂网络、切换 of multi-agent system with time-delay in state and switching 动力系统的分析与控制、系统生物以及 topology[J].International Journal of Control,2010,83 基于网络的控制系统等。主持国家 (2):371-386. 然科学基金项目3项，发表学术论文70 [16]LIU Bo,CHU Tianguang,WANG Long,et al.Controlla- 余篇，其中SCI收录23篇，EI收录50余篇。 bility of leader-follower dynamic network with switching to- pology [J].IEEE Transactions on Automatic Control, 王耀威，男.1989年生，硕士研究 2008,53(4):1009-1013. 生，主要研究方向为多智能体系统。 [17]LIU Yangyu,SLOTINE JJ,BARABASI A L.Controllabil- ity of complex networks[J].Nature,2011,473(7346): 167-173. [18]YUAN Zhengzhong,ZHAO Chen,DI Zengru,et al.Exact controllability of complex networks[J].Nature Communi- cations,2013,4:Aricle number 2447. [19]PARLANGELI G,NOTARSTEFANO G.On the reach- [责任编辑：刘畅] ability and observability of path and cycle graphs[]
ｆｅｒｅｎｃｅ． Ｏｒｌａｎｄｏ， ＵＳＡ， ２０１１： ４８２９⁃４８３４． ［９］ ＳＡＢＡＴＴＩＮＩ Ｌ， ＳＥＣＣＨＩ Ｃ， ＦＡＮＴＮＺＺＩ Ｃ． Ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ａｎｄ ｏｂｓｅｒｖａｂｉｌｉｔｙ ｐｒｅｓｅｒｖａｔｉｏｎ ｆｏｒ ｎｅｔｗｏｒｋｅｄ ｓｙｓｔｅｍｓ ｗｉｔｈ ｔｉｍｅ ｖａｒｙｉｎｇ ｔｏｐｏｌｏｇｉｅｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９ｔｈ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｆｅｄｅｒａｔｉｏｎ ｏｆ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ． Ｃａｐｅ Ｔｏｗｎ， Ｓｏｕｔｈ Ａｆｒｉｃａ， ２０１４： １８３７⁃１８４２． ［１０］ＭＥＳＢＡＨＩ Ｍ， ＥＧＥＲＳＴＥＤＴ Ｍ． Ｇｒａｐｈ Ｔｈｅｏｒｅｔｉｃ Ｍｅｔｈｏｄｓ ｉｎ Ｍｕｌｔｉａｇｅｎｔ Ｎｅｔｗｏｒｋｓ［Ｍ］． Ｐｒｉｎｃｅｔｏｎ： Ｐｒｉｎｃｅｔｏｎ Ｕｎｉｖｅｒ⁃ ｓｉｔｙ Ｐｒｅｓｓ， ２０１０： １１７⁃１５１． ［１１］ＳＵＮＤＡＲＡＭ Ｓ， ＨＡＤＪＩＣＯＳＴＩＳ Ｃ Ｎ． Ｄｉｓｔｒｉｂｕｔｅｄ ｆｕｎｃｔｉｏｎ ｃａｌｃｕｌａｔｉｏｎ ｖｉａ ｌｉｎｅａｒ ｉｔｅｒａｔｉｖｅ ｓｔｒａｔｅｇｉｅｓ ｉｎ ｔｈｅ ｐｒｅｓｅｎｃｅ ｏｆ ｍａｌｉｃｉｏｕｓ ａｇｅｎｔｓ ［ Ｊ ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ， ２０１１， ５６（７）： １４９５⁃１５０８． ［１２］ＰＡＳＱＵＡＬＥＴＴＩ Ｆ， ＢＩＣＣＨＩ Ａ， ＢＵＬＬＯ Ｆ． Ｃｏｎｓｅｎｓｕｓ ｃｏｍ⁃ ｐｕｔａｔｉｏｎ ｉｎ ｕｎｒｅｌｉａｂｌｅ ｎｅｔｗｏｒｋｓ： Ａ ｓｙｓｔｅｍ ｔｈｅｏｒｅｔｉｃ ａｐ⁃ ｐｒｏａｃｈ ［ Ｊ ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ， ２０１２， ５７（１）： ９０⁃１０４． ［１３］ＬＩ Ｚｈｏｎｇｋｕｉ， ＲＥＮ Ｗｅｉ， ＬＩＵ Ｘｉａｎｇｄｏｎｇ， ｅｔ ａｌ． Ｄｉｓｔｒｉｂｕ⁃ ｔｅｄ ｃｏｎｔａｉｎｍｅｎｔ ｃｏｎｔｒｏｌ ｏｆ ｍｕｌｔｉ⁃ａｇｅｎｔ ｓｙｓｔｅｍｓ ｗｉｔｈ ｇｅｎｅｒａｌ ｌｉｎｅａｒ ｄｙｎａｍｉｃｓ ｉｎ ｔｈｅ ｐｒｅｓｅｎｃｅ ｏｆ ｍｕｌｔｉｐｌｅ ｌｅａｄｅｒｓ［Ｊ］． Ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｒｏｂｕｓｔ ａｎｄ Ｎｏｎｌｉｎｅａｒ Ｃｏｎｔｒｏｌ， ２０１３， ２３（５）： ５３４⁃５４７． ［１４］ＦＡＲＩＮＡ Ｍ， ＦＥＲＲＡＲＩ⁃ＴＲＥＣＡＴＥ Ｇ， ＳＣＡＴＴＯＬＩＮＩ Ｒ． Ａ ｍｏｖｉｎｇ ｈｏｒｉｚｏｎ ｓｃｈｅｍｅ ｆｏｒ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔａｔｅ ｅｓｔｉｍａｔｉｏｎ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４８ｔｈ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｅｃｉ⁃ ｓｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ． Ｓｈａｎｇｈａｉ， Ｃｈｉｎａ， ２００９： １８１８⁃１８２３． ［１５］ＪＩ Ｚｈｉｊｉａｎ， ＷＡＮＧ Ｚｉｄｏｎｇ， ＬＩＮ Ｈａｉ， ｅｔ ａｌ． Ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｏｆ ｍｕｌｔｉ⁃ａｇｅｎｔ ｓｙｓｔｅｍ ｗｉｔｈ ｔｉｍｅ⁃ｄｅｌａｙ ｉｎ ｓｔａｔｅ ａｎｄ ｓｗｉｔｃｈｉｎｇ ｔｏｐｏｌｏｇｙ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｎｔｒｏｌ， ２０１０， ８３ （２）： ３７１⁃３８６． ［１６］ＬＩＵ Ｂｏ， ＣＨＵ Ｔｉａｎｇｕａｎｇ， ＷＡＮＧ Ｌｏｎｇ， ｅｔ ａｌ． Ｃｏｎｔｒｏｌｌａ⁃ ｂｉｌｉｔｙ ｏｆ ｌｅａｄｅｒ⁃ｆｏｌｌｏｗｅｒ ｄｙｎａｍｉｃ ｎｅｔｗｏｒｋ ｗｉｔｈ ｓｗｉｔｃｈｉｎｇ ｔｏ⁃ ２００８， ５３（４）： １００９⁃１０１３． ［１７］ＬＩＵ Ｙａｎｇｙｕ， ＳＬＯＴＩＮＥ Ｊ Ｊ， ＢＡＲＡＢÁＳＩ Ａ Ｌ． Ｃｏｎｔｒｏｌｌａｂｉｌ⁃ ｉｔｙ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｎａｔｕｒｅ， ２０１１， ４７３（ ７３４６）： １６７⁃１７３． ［１８］ＹＵＡＮ Ｚｈｅｎｇｚｈｏｎｇ， ＺＨＡＯ Ｃｈｅｎ， ＤＩ Ｚｅｎｇｒｕ， ｅｔ ａｌ． Ｅｘａｃｔ ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｎａｔｕｒｅ Ｃｏｍｍｕｎｉ⁃ ｃａｔｉｏｎｓ， ２０１３， ４： Ａｒｉｃｌｅ ｎｕｍｂｅｒ ２４４７． ［１９］ ＰＡＲＬＡＮＧＥＬＩ Ｇ， ＮＯＴＡＲＳＴＥＦＡＮＯ Ｇ． Ｏｎ ｔｈｅ ｒｅａｃｈ⁃ ａｂｉｌｉｔｙ ａｎｄ ｏｂｓｅｒｖａｂｉｌｉｔｙ ｏｆ ｐａｔｈ ａｎｄ ｃｙｃｌｅ ｇｒａｐｈｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ， ２０１２， ５７（３）： ７４３⁃７４８． ［ ２０］ ＰＡＲＬＡＮＧＥＬＩ Ｇ， ＮＯＴＡＲＳＴＥＦＡＮＯ Ｇ． Ｏｎ ｔｈｅ ｏｂｓｅｒｖａｂｉｌｉｔｙ ｏｆ ｐａｔｈ ａｎｄ ｃｙｃｌｅ ｇｒａｐｈｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４９ｔｈ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｅｃｉｓｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ． Ａｔｌａｎｔａ， ＵＳＡ， ２０１０： １４９２⁃１４９７． ［２１］ＣＨＡＲＴＲＡＮＤ Ｇ， ＺＨＡＮＧ Ｐｉｎｇ． 图论导引［Ｍ］． 范益政， 等译． 北京： 人民邮电出版社， ２００７： １⁃１７． ［２２］ＴＡＮＮＥＲ Ｈ Ｇ． Ｏｎ ｔｈｅ ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ｏｆ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４３ｒｄ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｅｃｉｓｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ． Ｎａｓｓａｕ， Ｂａｈａｍａｓ， ２００４： ２４６７⁃２４７２． ［２３］ ＰＡＲＬＡＮＧＥＬＩ Ｇ， ＮＯＴＡＲＳＴＥＦＡＮＯ Ｇ． Ｇｒａｐｈ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｂｓｅｒｖａｂｉｌｉｔｙ ｃｏｎｄｉｔｉｏｎｓ ｆｏｒ ｎｅｔｗｏｒｋ ｓｙｓｔｅｍｓ ｒｕｎｎｉｎｇ ａｖｅｒａｇｅ ｃｏｎｓｅｎｓｕｓ ａｌｇｏｒｉｔｈｍｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １８ｔｈ Ｍｅｄｉｔｅｒｒａｎｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｎｔｒｏｌ ａｎｄ Ａｕｔｏｍａｔｉｏｎ． Ｍａｒｒａｋｅｓｈ， Ｍｏｒｏｃｃｏ， ２０１０： ６８９⁃６９４． 作者简介： 晁永翠，女，１９９０ 年生，硕士研究生， 主要研究方向为复杂网络的可控性。 纪志坚，男，１９７３ 年生，教授，博士 生导师，博士，主要研究方向为群体系 统动力学与协调控制、复杂网络、切换 动力系统的分析与控制、系统生物以及 基于网络的控制系统等。 主持国家自 然科学基金项目 ３ 项，发表学术论文７０ ｐｏｌｏｇｙ ［ Ｊ ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ， ［责任编辑：刘畅 王耀威，男， １９８９ 年生，硕士研究 生，主要研究方向为多智能体系统。 ］ ·５８２· 智 能 系 统 学 报 第 １０ 卷 余篇，其中 ＳＣＩ 收录 ２３ 篇，ＥＩ 收录 ５０ 余篇