第3期 陈兴凯，等：基于0-1特征值的网络可控性优化研究 ·593· (g)=det(I-A)=0 (5) -1 -1 -01+1 … -dIN 当网络中存在孤立节点时，不妨设节点1为 -1 -1 一d1+1 -QIN 孤立节点，则det(-A)为 0 0 -1 -1 -01+l … 0 -dIN -a21 -a23 -d2N -ai+1.1-a+12 -a+1 -0+1,it2 -aNI 1 -dm -dn -aNN-1 -aN2 显然，当入=0时，dt2-A)中存在全0行，使 显然，当=-1时，det(-A)中的1到i行完 全相同，使得det(1-A)=0,因此o(-1)=0,即-1为 得det(-A)=0,因此p(O)=0,即0为A的特征值。 A的特征值。证毕。 当网络中存在不含孤立节点的独立共连结 3.3结构优化 构时，不妨设1到i点为独立共连结构，则 独立共连结构和互连共连结构是0/-1特征 detk【-A)为 结构中具有明显规律性的结构，为了提高网络的 0 -a1,+1 0 0 可控性，则可以通过消除网络中的这2种结构，减 -01+1 -41N 少0/-1特征值对应，-A矩阵的行相关性，即减 0 -01+1 -1N 少最小控制输人的节点个数，从而实现可控性的 -a+11-a41.2 -ai+l.i Ak -0i+1,i+2 -☑i+1N 优化。 本文中的优化方法主要是基于邻接矩阵A来 -aN -aN.N-1 找到两种典型的0/-1特征结构，通过对矩阵A中 显然，当=0时，det(-A)中的1到i行完全 对应元素的改变来实现节点之间的增边或减边， 相同，使得det(2-A)=0,因此o(0)=0,即0为A的 从而实现结构优化操作。由0-A=-A可知，消除 特征值。证毕。 独立共连结构的处理对象为矩阵-A(或A),消除 3.2-1特征结构 全0行则可消除孤立节点，消除相同行则可消除 在特征值一1对应的特征结构中，存在着一种 不含孤立节点的独立共连结构；由-1·-A=--A 具有明显规律性的特征结构，其具体定义如下： 可知，消除互连共连结构的处理对象为矩阵 定义2互连共连结构。互连共连结构是指 -I-A(或A+),消除相同行则可消除互连共连结 网络中存在若干节点（称为对象节点），这些节点 构。在整个结构优化过程中，设置每个步长只允 之间是互相连接的，且它们与网络中其他节点的 许对一条边进行一次增边或减边操作，则优化的 连接状况完全相同。如图2中的对象节点1、2、 主要步骤如下： 3构成了互连共连结构。 1)逐行判断矩阵A是否存在全0行。如果存 在且第i行为全0行，则随机生成一个整数，有 je(1,且j,令a=1,a=l,跳转1)继续运行；如 果不存在全0行，则跳转2)。 2)逐行对比矩阵A中的其他行是否存在相同 行。如果存在相同行，则获取对象点集CP、共连 点集SP,随机生成2个整数i和j,有i∈CP, 图2互连共连结构 j∈SP,令a=0,a,=0,跳转1)；如果不存在相同 Fig.2 The connected link structure 行，则跳转3)。 互连共连结构与特征-1的关系可由下述定 3)逐行对比矩阵A+I中的其他行是否存在相 理描述： 同行。如果存在相同行，则获取对象点集CP、共 定理4如果一个网络中存在互连共连结 连点集SP,随机生成两个整数i和j,有i∈CP, 构，则该网络的邻接矩阵A具有特征值-1。 j∈SP,令a,=0,a=0,跳转1)；如果不存在相同 证明邻接矩阵A的特征值4满足式（⑤），不 行，则完成网络可控性的优化。 妨设1到i点为互连共连结构，则det(2-A)为 上述主要步骤中，为了减小网络的复杂程度，φ(λk) = det(λk I− A) = 0 (5) 当网络中存在孤立节点时，不妨设节点 1 为 孤立节点，则 det(λkI−A) 为   λk 0 0 ··· 0 −a21 λk −a23 ··· −a2N . . . . . . . . . −aN1 −aN2 ··· λk   显然，当 λk=0 时，det(λkI−A) 中存在全 0 行，使 得 det(λkI−A)=0，因此 φ(0)=0，即 0 为 A 的特征值。 当网络中存在不含孤立节点的独立共连结 构时，不妨 设 1 到 i 点为独立共连结构，则 det(λk I−A) 为   λk 0 ··· 0 −a1,i+1 ··· −a1N 0 λk ··· 0 −a1,i+1 ··· −a1N . . . . . . . . . . . . . . . 0 0 ··· λk −a1,i+1 ··· −a1N −ai+1,1 −ai+1,2 ··· −ai+1, j λk −ai+1,i+2 −ai+1,N . . . . . . . . . . . . . . . −aN1 −aN2 −aN3 −aN4 ··· −aN,N−1 λk   显然，当 λk=0 时，det(λkI−A) 中的 1 到 i 行完全 相同，使得 det(λkI−A)=0，因此 φ(0)=0，即 0 为 A 的 特征值。证毕。 3.2 −1 特征结构 在特征值 −1 对应的特征结构中，存在着一种 具有明显规律性的特征结构，其具体定义如下： 定义 2 互连共连结构。互连共连结构是指 网络中存在若干节点 (称为对象节点)，这些节点 之间是互相连接的，且它们与网络中其他节点的 连接状况完全相同。如图 2 中的对象节点 1、2、 3 构成了互连共连结构。 1 3 2 4 5 … … … … 图 2 互连共连结构 Fig. 2 The connected link structure 互连共连结构与特征 −1 的关系可由下述定 理描述： 定理 4 如果一个网络中存在互连共连结 构，则该网络的邻接矩阵 A 具有特征值 −1。 证明 邻接矩阵 A 的特征值 λk 满足式 (5)，不 妨设 1 到 i 点为互连共连结构，则 det(λkI−A) 为   λk −1 ··· −1 −a1,i+1 ··· −a1N −1 λk ··· −1 −a1,i+1 ··· −a1N . . . . . . . . . . . . . . . . . . −1 −1 ··· λk −a1,i+1 ··· −a1N −ai+1,1 −ai+1,2 ··· −ai+1, j λk −ai+1,i+2 −ai+1,N . . . . . . . . . . . . . . . −aN1 −aN2 −aN3 −aN4 ··· −aN,N−1 λk   显然，当 λk=−1 时，det(λkI−A) 中的 1 到 i 行完 全相同，使得 det(λkI−A)=0，因此 φ(−1)=0，即−1 为 A 的特征值。证毕。 3.3 结构优化 独立共连结构和互连共连结构是 0/−1 特征 结构中具有明显规律性的结构，为了提高网络的 可控性，则可以通过消除网络中的这 2 种结构，减 少 0/−1 特征值对应 λkI−A 矩阵的行相关性，即减 少最小控制输入的节点个数，从而实现可控性的 优化。 本文中的优化方法主要是基于邻接矩阵 A 来 找到两种典型的 0/−1 特征结构，通过对矩阵 A 中 对应元素的改变来实现节点之间的增边或减边， 从而实现结构优化操作。由 0·I−A=−A 可知，消除 独立共连结构的处理对象为矩阵−A(或 A)，消除 全 0 行则可消除孤立节点，消除相同行则可消除 不含孤立节点的独立共连结构；由−1·I−A=−I−A 可知，消除互连共连结构的处理对象为矩阵 −I−A(或 A+I)，消除相同行则可消除互连共连结 构。在整个结构优化过程中，设置每个步长只允 许对一条边进行一次增边或减边操作，则优化的 主要步骤如下： 1）逐行判断矩阵 A 是否存在全 0 行。如果存 在且第 i 行为全 0 行，则随机生成一个整数 j，有 j∈(1,N) 且 j≠i，令 aij=1，aji=1，跳转 1）继续运行；如 果不存在全 0 行，则跳转 2）。 2）逐行对比矩阵 A 中的其他行是否存在相同 行。如果存在相同行，则获取对象点集 CP、共连 点 集 S P，随机生 成 2 个 整 数 i 和 j， 有 i∈C P， j∈SP，令 aij=0，aji=0，跳转 1）；如果不存在相同 行，则跳转 3）。 3）逐行对比矩阵 A+I 中的其他行是否存在相 同行。如果存在相同行，则获取对象点集 CP、共 连点集 SP，随机生成两个整数 i 和 j，有 i∈CP， j∈SP，令 aij=0，aji=0，跳转 1）；如果不存在相同 行，则完成网络可控性的优化。 上述主要步骤中，为了减小网络的复杂程度， 第 3 期 陈兴凯，等：基于 0/-1 特征值的网络可控性优化研究 ·593·