控制科学的发展表明，可控性概念是对系统进行分析与综合的基础，是系统的重要结构性质。20世纪60年代，卡尔曼(R.E.Kalman)^[1]首先提出状态可控性的概念。其后的研究表明，可控性的概念是判别被控系统是否可控的重要途径。近年来，网络系统的可控性研究成为当前的一个热点研究领域，该问题的研究受到了国内外科研工作者的广泛关注^{[2, 3, 4, 5, 6]}。

本文致力于研究复杂网络系统的能控性，该研究可促进包括系统的镇定控制^{[7, 8]}、编队控制^{[9, 10]}、入侵检测^{[11, 12]}和分布式估计^{[13, 14, 15, 16]}等诸多问题的理解。和传统控制不同，网络系统是建立在个体间信息的传递之上的。自然地，信息关系图的拓扑结构在系统行为的动态演化中起到了关键性作用，不同拓扑结构下的系统性能可能截然不同。因此，许多科研工作者尝试探讨与能控性相关的图论刻画。例如，系统能控的图论特征，这些特征使得直接从图的拓扑结构出发判断系统的能控性成为可能；再如，能控性中领航者的选取问题，如何确定领航者的位置和数量使得系统能控，这也是网络系统能控性中的典型问题。

复杂网络的研究已渗透到数理学科、生命学科和工程学科等众多不同的领域，对复杂网络可控性的研究具有挑战性^{[17, 18]}。即便是最简单的路形拓扑结构，和其可控性相关的研究也不简单^[19]。文献^[19]研究的是基于Laplacian矩阵的路图的能控性，与该问题相关的研究成果在文献^{[4, 6, 20]}中也报道过。此外，还有基于邻接矩阵的网络系统可控性问题^{[17, 18]}，本文即是研究基于邻接矩阵的路图拓扑的可控性。

本文研究的是控制节点的选取，这不同于文献^{[17, 18]}中驱动节点个数的选取问题。在基于邻接矩阵的可控性问题研究，文献^[17]中表述，网络中节点的度的大小影响驱动节点个数的选取，在选取驱动节点时，选取度数小的驱动节点更有利于系统可控性的实现。但针对更复杂的拓扑结构，控制节点的选取比驱动节点的选取更为复杂，相应的结果也更少。文献^[18]提出了对于特定的链接与加权网络，使系统可控的最少数目控制节点的判别方法。然而，以上两篇文章都没有给出针对网络拓扑图中，通过控制某一个或几个节点，来具体判断系统是否可控的方法。该问题涉及到控制节点的选取，这通常是更为复杂的研究方面，也是本文着力解决的内容。

本文将针对路形拓扑结构，对每个节点展开分析，通过建立充要条件，来判断相应系统的可控性。更具体地，通过对路图的邻接矩阵及其子矩阵进行分析，发现其特征值之间的相互关系，从而得到路图可控性的充分必要条件，该结果的一个显著特征是建立了所提出的代数条件与拓扑图中每个节点的联系。

文中为自然数集，e_r为第r个元素为1，其他元素均为0的列向量，r∈，例如e₁=[1 0 … 0]^T。记G(b₁,b₂,…,b_d)为d个自然数b₁,b₂,…,b_d的最大公约数，d∈。G(b₁,b₂,…,b_d)>1表示b₁,b₂,…,b_d有除了1之外的其他公约数。Rⁿ表示n维实向量空间，R^m×n表示实m×n矩阵的集合。对于一个有n个节点的无向图G，所有的节点被标记为1,2,…,n。顶点集和边集分别记为V={1,2,…,n}与ε={(i,j)}∈V×V，i和j邻接。图G是由顶点集V和边集ε构成的二元组，记为G=(V,ε)。与顶点v相关联的边的总数称为顶点v的度。一个有n个节点的图G，若其顶点可以标号成(或重新标号成)1,2,…,n,使得它的边集是ε={(1,2),(2,3),…,(n－1,n)}，则称图G为路图^[21]。由此可知，除了第一个节点1与最后一个节点n的度为1之外，其他所有节点的度都为2。节点1与节点n称为外节点，其他的节点称为内节点。设图G的邻接矩阵A=(a_ij)_n×n，则a_ij定义为

在已有文献中，通常把由外部输入控制的节点称为控制节点，由I_c={i₁,i₂,…,i_m}⊂{1,2,…,n}表示被控的节点集。考虑如下一个有n个节点的线性系统：

式中：x=[x₁ x₂…x_n]^T表示系统的状态，A∈R^n×n是系统的邻接矩阵，B∈R^n×m是控制矩阵，u∈R^m×n是输入矩阵。由于讨论的是无向图，所以A是对称矩阵。对任一给定的初始状态，如果存在一个控制输入u，使式(1)能在有限时间间隔内，从初始状态转移到任意指定的终端状态，则称该系统是可控的。目前，有许多判别线性系统可控的方法，例如Gram矩阵判据、PBH判据^[22]、秩判据等。本文从PBH判据出发，分析系统的可控性，进而得到系统可控的充要条件。

引理1 系统(1)可控的充要条件是不存在非零的向量v满足以下等式：

若存在向量v使得上面的等式成立，则称相应的λ是系统不可控的特征值。

证明 根据PBH判据并结合A的对称性即知结论成立。

本节将首先对邻接矩阵进行分解，基于此给出子矩阵特征值的表达形式，然后，通过所提出的矩阵特征值之间的关系，得出相应的引理与定理。

B矩阵的具体表达与一系列的控制节点相对应，如果I_c={i₁,i₂,…,i_m}，则B=[e_i1 e_i2… e_im]。由引理1可知，路图不可控意味着存在非零向量v满足Av=λv，且B^Tv=0。矩阵Mν定义如下：

式中ν是矩阵的维数。

因为B=[e_i1 e_i2… e_im]，由B^Tv=0可得向量v的第i_c个向量元素为零，即(v)_ic=0，i_c∈I_c。因此，在Av=λv中，A可分解为

向量v可分解为

由Av=λv可得

式中：v_σ是向量v的第σ个分块向量，σ∈。

引理2 矩阵A与矩阵M_ν的特征向量的第一个元素与最后一个元素都不为0。

证明 设λ为A的一个特征值，对应的特征向量为ξ=[ξ₁ ξ₂… ξ_n]^T，由Aξ=λξ可得

当ξ₁=0时，ξ₂=ξ₃=…=ξ_n=0，即ξ为零向量，这与ξ是特征向量矛盾。同理可证ξ_n≠0。矩阵M_ν的情况同样证明。

引理3 对于矩阵M_ν，有

1)矩阵M_ν的特征值的形式为

2)矩阵M_ν的特征值必是矩阵M_αν+α－1的特征值，其中α∈。

证明 1)可由文献^[18]附加材料中关于路图的例子得到。2)可由矩阵M_ν特征值的表达形式得到。

将引理1与引理2结合可知，路图的每一个外节点为控制节点时，路图是可控的^[23]。然而，当控制节点为路图的内节点时，其能控性如何，是更值得探讨的问题，这也是本节欲解决的问题。首先给出以下两个引理，其中，第一个引理是关于单个控制节点的情况。

引理4 对控制节点为r∈{2,3,…,n－1}的长度为n的路图，当且仅当矩阵M_r－1与M_n－r没有相同的特征值时，路图是可控的。此外，矩阵M_{r－1与Mn－r相同的特征值为矩阵A在控制节点为r时，系统不可控的特征值。}

证明 为了简便，证其逆否命题。由PBH判据，当且仅当

且e_r^Tv=0时，路图是不可控的。由e_r^Tv=0得

式中：v₁∈R^r－1，v₂∈R^n－r。代入式(2)得

所以，系统不能控当且仅当不存在A的一个特征向量v使得式(3)成立。

充分性 若λ₀为M_r－1与M_n－r的共同特征值，且对应的特征向量分别为v₁₀与v₂₀。令

式中：ρ∈R，(v₁₀)_r－1+(ρv₂₀)₁=0，则可验证v满足式(3)，其中λ=λ₀。所以系统不能控。

必要性 假设系统不能控，则由式(3)且v₁≠0，v₂≠0得，λ为矩阵M_r－1与M_n－r的共同特征值。

此外，假设λ₁是M_r－1与M_n－r共同的特征值，则存在一个如上的非零向量v=[v₁₀^T 0 ρv₂₀^T]^T满足Av=λv，e_r^Tv=0。因此λ₁是系统不可控的特征值。

引理4回答了控制节点为一个时，路图可控的充要条件，以下这个引理则给出了受控节点为多个时，路图可控的充要条件。

引理5 控制节点I_c={i₁,i₂,…,i_m}⊂{1,2,…,n}长度为n的路图，当且仅当矩阵M_i1－1，M_i2－i1－1，…，M_n－im没有相同的特征值时，路图是可控的。此外，矩阵共同的特征值为邻接矩阵A在控制节点为I_c时，系统不可控的特征值。

引理5的证明与引理4类似，此处不再赘述。

为了更清晰地表达以上关于可控性的条件，下面利用特征值的特殊形式与最大公约数理论，进一步给出路图可控的充分必要条件。

定理1 对于一个长度为n的路图，有以下陈述：

1)当控制节点为r∈{2,3,…,n－1}时，路图可控的充分必要条件为

G(r,n－r+1)=1

2)当控制节点集I_c={i₁,i₂,…,i_m}⊂{1,2,…,n}时，路图可控的充分必要条件为

G(i₁,i₂－i₁,…,i_m－i_m－1,n－i_m+1)=1

证明

充分性 证其逆否命题，由引理4可知，当矩阵M_r－1与M_n－r有相同的特征值时，路图不完全可控。结合引理3可得

式中：q₁∈{1,2,…,(r－1)}，q₂∈{1,2,…,(n－r)}。由于q₁与q₂取自这2个特定集合，式(4)等式两边余弦内的数值都小于π，得

化简为

又由于q₁与q₂的取值限制，使得式(5)成立的条件是整数r与n－r+1不互质，即

G(r,n－r+1)>1

必要性 证其逆否命题，当G(r,n－r+1)>1时，则存在正整数c，t₁，t₂，使得ct₁=r，ct₂=n－r+1，其中t₁<r，t₂<n－r+1。又有q₁∈{1,2,…,r－1}，q₂∈{1,2,…,n－r}，则当q₁=t₁，q₂=t₂时，等式成立，即为式(5)的形式，则式(4)成立。即矩阵M_r－1与M_n－r有相同的特征值。所以路图是不可控的。

对陈述2)，证其逆否命题。引理5与引理3结合，取子矩阵的特征值。接下来的证明与陈述1)中的相似。最后即可得到陈述2)中的结论。

由定理1中陈述1)同样也可得到当控制节点为外节点时路图是可控的这一结论。具体如下：控制节点r=1或n时，根据陈述1)可得G(1,n)=1或G(n,1)=1，因为1与任何数都互质，可得当控制节点为外节点时路图是可控的。当控制节点r=2或n－2时，由陈述1)可知，需判断2与n－1是否互质。当n－1奇数，即n为偶数时，2与n－1互质，路图可控；反之，路图不可控。可表述为以下推论。

推论1 对于一个长度为n的路图，当控制节点r为外节点的邻接点时，若n为偶数时，则路图是可控的；若n为奇数时，则路图不可控。

由定理1中陈述1)还可推出一些简便的判别路图可控性的方法。例如，当控制节点r=n/2(r= (n+2)/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个数。我们知道，相邻的2个数肯定是互质的，所以路图是可控的。当n为奇数且r为偶数时，路图不可控。因为当n为奇数r为偶数时，n－r+1为偶数，即G(r,n－r+1)>1，路图不可控。

定理2 对于一个长度为n的路图，若n可分解为n=mp+m+p，其中m,p∈，则当控制节点集为I_c^pm={κ(p+1)}_κ∈1,…,m时，路图是不可控的，其中κ∈{1,2,…,m}。此外，假设κ的取值从小到大依次为b₁,b₂,…,b_s(s≤m)，则系统有以下不可控的特征值

式中：β=min{b₁,b_k－b_k－1,m－b_s+1}，k∈{2,3,…,s}。

证明 当n=mp+m+p时，控制节点集为I_c^pm=κ(p+1)_{κ∈{1,2,…,m}}，即为定理1陈述2)中所有不可控的控制节点的集合。当整数p的取值不同时，即可得到不同的不可控的控制节点集。当β=min{b₁,b_k－b_k－1,m－b_s+1}，k∈{2,3,…,s}，邻接矩阵A被分解为2种形式的子矩阵，即M_β(p+1)－1与M_{(β+μ)(p+1)－1}(μ∈。子矩阵的共同特征值即为最小的子矩阵M_β(p+1)－1特征值的部分或全部。即为式(6)表达的形式。若存在一个正整数y使μ=yβ，则不可控的特征值为最小的子矩阵M_β(p+1)－1的全部特征值，即

为了更清晰地理解定理2，以下给出一个较为直观的解释。当p与m固定时，对控制节点集I_c^pm中的节点给与相同的标记。把全部的节点用m个控制节点分为m+1份，每份的节点数为p个(除控制节点外)。但事实上，在选取控制节点时未必选择集合I_c^pm内的所有的节点为控制节点，所以有定理2中所述，不可控的特征值为邻接矩阵A中被分解的最小的子矩阵M_β(p+1)－1的特征值的部分或全部。

以下给出2个例子。n=11与n=14的路图，分别如图 1中与图 2所示。

图 1 n=11的路图 Fig. 1 The path graph with n=11

图选项

在图 1中，横线标记的节点是控制节点为I_c^p₁m₁的集合，其中p₁=1,m₁=5。竖线标记的节点是控制节点为I_c^p₂m₂的集合，其中p₂=2,m₂=3。当控制节点为I_c^p₁m₁时，系统有相同的不可控的特征值λ=0，而1与-1为系统在控制节点集为I_c^p₂m₂时2个不可控的特征值。

图 2 n=14的路图 Fig. 2 The path graph with n=14

图选项

在图 2中，斜线标记的节点是控制节点为I_c^pm的集合，其中p=2,m=4。当控制节点为节点3和节点9时，A可被分解为M₂与M₅两种形式的子矩阵，矩阵M₂与M₅的共同特征值即为矩阵M₂的全部特征值。若控制节点为节点6时，A可被分解为M₅与M₈两种形式的子矩阵，矩阵M₅与M₈的共同特征值即为矩阵M₅的部分特征值。

本文给出了判断复杂网络系统中路图可控性的方法，把PBH判据与对称的邻接矩阵相结合，得到了路图可控的充要条件，并应用数学中的简单理论，对于路图可控性的充要条件进行了更为数字化的表示。在此基础上，提出了系统不可控的特征值的表达形式。同理，可推出环图可控性的充要条件。本文通过对路图的每个节点进行分析，进而判断可控性，使得直接从图的结构形式判断能控性成为可能。本文对于路图可控性的研究方法和结果，为以后研究更为复杂的图拓扑结构的可控性提供了一个方向和基础。