·488· 智能系统学报 第16卷 3 最小领航集 于是可构造二部图H=(U,V;E)如图5所 示。从该二部图中可以看出每个顶点”：只能覆盖 基于关键集的概念，本节讨论如何求出无人 一个4，于是从每个4的相邻顶点任取一个组成 机集群最小领航集的算法。 的集合就是图G的最小领航集，比如可取T= 3.1算法理论基础 ,2,4,}为最小领航集。 由性质2及关键集的定义知定理6成立。 定理6设F为跟随集，F为领航集，则双向 ● 通信无人机集群线性时不变系统（见式(1）)可控 当且仅当F中不包含关键集。 V1 V2 V3 V4 V's V5 V7 V's V9 V1o 证明由性质2知系统（见式(1）)可控当且 仅当y≠0，其中y是任意一个特征向量。由定 图5二部图 Fig.5 Bipartite graph 义1知，yF≠0当且仅当F不是关键集且不包含 任何关键集。 本算例说明如何运用关键集求出无人机集群 通信网络拓扑结构图的最小领航集。 设S1,S2,…,Sm是无人机集群通信网络拓扑 结构图的所有关键集，构造二部图H=(U,V:E), 3.3CSA算法复杂性分析 顶点集U={W,,…,4m},其中与S:对应； 般地，CSA算法的1)和3)都不是多项式时 间的算法。但是，基于本文给出的定理，求出相 V=V(G)={,2,…,}为无人机集群通信网络拓 扑结构图G的顶点集，v叫∈E(H)当且仅当∈Sj。 应特殊的关键集及领航集则是多项式时间算法， 若∈E(H则称顶点M覆盖关键集Sj。由定 具体的算法流程如图6所示。 理6可知求最小领航集等价于求覆盖所有关键集 (开始 的最小顶点集T(Ts)。 3.2最小领航集算法 输人Laplace矩阵L,n,T:=O 基于定理6，本节给出求领航集的算法(critic 找所有2关键集S al set algorithm,CSA): 谷 1)求出无人机集群通信网络拓扑结构图 任取y,∈S,T=TU{v G的所有k关键集S(i=1,2,…,m): 找所有3 2)构造二部图H=(UV;E): 领航T可控 关键集S 3)求最小顶点集T(T二V)使T中的顶点覆盖 所有关键集，则T即为最小领航集。 N 例如，图4中G来自文献[15]，由定理3知 已找3关键集 它有2关键集S1={M,%}、S2=2,、S3={v4,s、 Y S4={,;由定理4知该图没有3关键集；由于 T=0 2个悬挂点4、都与%相邻，故由引理1知% 不属于任何完美关键集；同理，考虑”1和%这 输出T 2个顶点可知0也不属于任何关键集。从而，容 易知道图4中不存在5完美关键集：对于4完美 结束 关键集只能是上述4个S:位=1,2,3,4)中每个集合 图6CSA算法流程 各取一个构成的集合，容易验证它们都不是关键 Fig.6 Flow chart of CSA 集。即上述4个S:(i=1,2,3,4)是该网络的全部最 由定理3知，在CSA算法流程图中找出所有2 小完美关键集。 关键集的算法复杂性为On)。由定理4知，找所 有3关键集的算法复杂性为0n),因此，图6所 示的CSA算法复杂性为Om)。 3.4数值实验及分析 在实验中，设无人机集群的初始位置随机，经 图4图G及其关键集 过一段时间后形成稳定的通信网络拓扑结构图， Fig.4 Graph G it's critical set 并在后续保持通信关系不变。在具体的数值实验3 最小领航集 基于关键集的概念，本节讨论如何求出无人 机集群最小领航集的算法。 3.1 算法理论基础 由性质 2 及关键集的定义知定理 6 成立。 定理 6 设 F 为跟随集， F 为领航集，则双向 通信无人机集群线性时不变系统 (见式 (1)) 可控 当且仅当 F 中不包含关键集。 yF¯ , 0 y yF¯ , 0 证明 由性质 2 知系统 (见式 (1)) 可控当且 仅当 ，其中 是任意一个特征向量。由定 义 1 知， 当且仅当 F 不是关键集且不包含 任何关键集。 S 1,S 2,··· ,S m H = (U,V;E) U = {u1,u2,··· ,um} ui S i V = V(G) = {v1, v2,··· , vn} viuj ∈ E(H) vi ∈ S j viuj ∈ E (H) vi S j T(T ⊆ V) 设 是无人机集群通信网络拓扑 结构图的所有关键集，构造二部图 ， 顶点集 ，其中 与 对应； 为无人机集群通信网络拓 扑结构图 G 的顶点集， 当且仅当 。 若 则称顶点 覆盖关键集 。由定 理 6 可知求最小领航集等价于求覆盖所有关键集 的最小顶点集 。 3.2 最小领航集算法 基于定理 6，本节给出求领航集的算法 (critic￾al set algorithm, CSA)： S i(i = 1,2,··· ,m) 1 ) 求出无人机集群通信网络拓扑结构 图 G 的所有 k 关键集 ； 2) 构造二部图 H = (U,V;E) ； 3) 求最小顶点集 T(T ⊆ V) 使 T 中的顶点覆盖 所有关键集，则 T 即为最小领航集。 S 1 = {v1, v6} S 2 = {v2, v3} S 3 = {v4, v5} S 4 = {v7, v8} v4 v5 v9 v9 v1 v6 v10 S i(i = 1,2,3,4) S i(i = 1,2,3,4) 例如，图 4 中 G 来自文献 [15]，由定理 3 知 它有 2 关键集 、 、 、 ；由定理 4 知该图没有 3 关键集；由于 2 个悬挂点 、 都与 相邻，故由引理 1 知 不属于任何完美关键集；同理，考虑 和 这 2 个顶点可知 也不属于任何关键集。从而，容 易知道图 4 中不存在 5 完美关键集；对于 4 完美 关键集只能是上述 4 个 中每个集合 各取一个构成的集合，容易验证它们都不是关键 集。即上述 4 个 是该网络的全部最 小完美关键集。 v1 v6 v10 v9 v4 v5 v2 v3 v8 v7 图 4 图 G 及其关键集 Fig. 4 Graph G it’s critical set H = (U,V;E) vi uj uj T = {v1, v2, v4, v7} 于是可构造二部图 如 图 5 所 示。从该二部图中可以看出每个顶点 只能覆盖 一个 ，于是从每个 的相邻顶点任取一个组成 的集合就是图 G 的最小领航集，比如可取 为最小领航集。 u1 u2 u3 u4 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 图 5 二部图 Fig. 5 Bipartite graph 本算例说明如何运用关键集求出无人机集群 通信网络拓扑结构图的最小领航集。 3.3 CSA 算法复杂性分析 一般地，CSA 算法的 1) 和 3) 都不是多项式时 间的算法。但是，基于本文给出的定理，求出相 应特殊的关键集及领航集则是多项式时间算法， 具体的算法流程如图 6 所示。 开始 结束 Y N Y N 输入 Laplace 矩阵 L, n, T:=Ø 任取 vi∈Si ,T:=T∪{vi } 找所有 3 领航 关键集 Si T 可控 已找 3 关键集 T:=Ø 输出 T 找所有 2 关键集 Si 图 6 CSA 算法流程 Fig. 6 Flow chart of CSA O(n 3 ) O(n 4 ) O(n 4 ) 由定理 3 知，在 CSA 算法流程图中找出所有 2 关键集的算法复杂性为 。由定理 4 知，找所 有 3 关键集的算法复杂性为 ，因此，图 6 所 示的 CSA 算法复杂性为 。 3.4 数值实验及分析 在实验中，设无人机集群的初始位置随机，经 过一段时间后形成稳定的通信网络拓扑结构图， 并在后续保持通信关系不变。在具体的数值实验 ·488· 智 能 系 统 学 报 第 16 卷