第3期 戴丽：双向通信无人机集群领航顶点选取方法 ·487· 2最小完美关键集。 Lta-vy dc(vi)y:=Ayi,i=1.2.....k 定理3设ScV且S=2,则S为2关键集 即dc()=dc(2)=…=dc()=。亦即当S为独立 当且仅当对y∈5，v要么与S中所有顶点都相 集时，完美关键集S中顶点度均相等。基于此，定 邻，要么与S中所有顶点都不相邻。 理5给出了独立集成为关键集的一个充分条件。 证明由定理2知充分性成立。只须证明必 定理5设S为独立集，Gs为关于顶点集 要性。 S的简化图。若S中所有顶点在图G中的度相 设S为2关键集，由引理1知[{v以，S]≠1v∈S), 等，且Sc中所有顶点在Gs中的度均为偶数，则 因此，vv以，S]I=2或v,S]I=0,即要么v与S中 S为关键集。 所有顶点都相邻，要么ⅴ与S中所有顶点都不相邻。 证明不防设S={y,2,…,}且S中所有顶 定理4设ScV且S1=3,则S为3关键集 点在图G中的度均为d。若简化图Gs为空图，则 当且仅当v∈S,v要么与S中所有顶点都相邻， 由定理2知结论成立，下设Gs非空图。 要么与S中所有顶点都不相邻。 v∈Sc,由v在图Gs中的度为偶数知行向量 证明由定理2知充分性成立。只须证明必 L-s的所有分量求和为零（模2），于是子矩阵 要性。 Ls。,一s的列向量组线性相关，所以齐次线性方程 设S为3关键集，由引理1知[w以，S]‖≠1且 组L5,-sx=0有非零解x=[x…。 I[wh,S]1≠2y∈S),因此，要么v以，S]=3,要么 [v以，S]1=0,即要么v与S中所有顶点都相邻，要 我们断言∑x=0,事实上，由S中所有顶点 么v与S中所有顶点都不相邻。 在图G中的度均为d及简化图G的构造过程可 由定理3可知，2关键集实际上就是文献26] 知顶点(i=1,2,…,k)在简化图Gs中的度也相 给出的twins顶点对，由此可见，2关键集是 等，设为≠0（因Gs非空图），于是 twins顶点对的推广。但与文献[17刀中所提出的 DCD顶点对不同，DCD顶点对考虑的是在跟随 1abs=Wd…dr=d=0 集中的2个顶点，而2关键集考虑的对象则是所 有顶点。 即有克5=0。 另外，定理3和定理4表明顶点集S能否成 取y=[x2…x0…0,A=d,则有 为2关键集或3关键集与S中的顶点是否相邻无关。 但是，当S中顶点数更多时，该结论不一定成立。 Ls-vy=[Ls-s Ls-s10 =Ls-sx= 如图2中4个深色顶点构成的顶点集S,当S [dxdx2…dx]T=x 中顶点的相邻关系如图(a)时，它是4关键集；但 对∈5，若v与S中顶点都相邻，则由 当S中顶点的相邻关系如图⑥)时，它不再是4关键集。 方与=0知L=0:若与S中顶点都不相邻。 则有L-y=0;若w∈G,则有 (a)S是4关键集 (b)S不是4关键集 L-y=-Lm-s]=0 图24关键集与GS的关系 综上可知Ly=dy,即向量y为Laplace矩阵的 Fig.2 Relationship between four critical set an GS] 特征向量，由于ys=0,故由定义1知S为关键集。 2.3独立关键集的图特征 例如，图3中的独立集S,考虑其简化图Gs, 对于顶点集S,按照定理2，删除5中与S顶 在5c中的所有顶点的度都为偶数2，由定理5知 点都相邻或都不相邻的顶点，同时也删除顶点导 S为4关键集。 出子图G⑤中所有边，称这样得到的图为关于顶 点集S的简化图，记作Gs。当S是独立集时，Gs 是二部图。记Sc,为S在简化图Gs中的补集。 若S={y,y2,…,}为独立集且为k完美关键 集，则Laplace矩阵L有一个特征向量： G Gs y=y12…g0…0]T (a)原图 (b)简化图 》≠0，i=1,2,…,k 图3简化图及其关键集 由S为独立集知v:∈S有： Fig.3 Simplification of graph G and its CS2 最小完美关键集。 S ⊂ V |S | = 2 ∀v ∈ S¯ 定理 3 设 且 ，则 S 为 2 关键集 当且仅当对 ，v 要么与 S 中所有顶点都相 邻，要么与 S 中所有顶点都不相邻。 证明 由定理 2 知充分性成立。只须证明必 要性。 |[{v},S ]| , 1(∀v ∈ S¯) |[{v},S ]| = 2 |[{v},S ]| = 0 设 S 为 2 关键集，由引理 1 知 ， 因此，v 或 ，即要么 v 与 S 中 所有顶点都相邻，要么 v 与 S 中所有顶点都不相邻。 S ⊂ V |S | = 3 ∀v ∈ S¯ 定理 4 设 且 ，则 S 为 3 关键集 当且仅当 ，v 要么与 S 中所有顶点都相邻， 要么与 S 中所有顶点都不相邻。 证明 由定理 2 知充分性成立。只须证明必 要性。 |[{v},S ]| , 1 |[{v},S ]| , 2(∀v ∈ S¯) |[{v},S ]| = 3 |[{v},S ]| = 0 设 S 为 3 关键集，由引理 1 知 且 ，因此，要么 ，要么 ，即要么 v 与 S 中所有顶点都相邻，要 么 v 与 S 中所有顶点都不相邻。 由定理 3 可知，2 关键集实际上就是文献 [26] 给 出 的 twin s 顶点对，由此可见， 2 关键集 是 twins 顶点对的推广。但与文献 [17] 中所提出的 DCD 顶点对不同，DCD 顶点对考虑的是在跟随 集中的 2 个顶点，而 2 关键集考虑的对象则是所 有顶点。 另外，定理 3 和定理 4 表明顶点集 S 能否成 为 2 关键集或 3 关键集与 S 中的顶点是否相邻无关。 但是，当 S 中顶点数更多时，该结论不一定成立。 如 图 2 中 4 个深色顶点构成的顶点 集 S， 当 S 中顶点的相邻关系如图 (a) 时，它是 4 关键集；但 当S中顶点的相邻关系如图(b)时，它不再是4关键集。 S S (a) S 是 4 关键集 (b) S 不是 4 关键集 图 2 4 关键集与 G[S] 的关系 Fig. 2 Relationship between four critical set an G[S] 2.3 独立关键集的图特征 S¯ G [ S¯ ] GS GS S¯ GS GS 对于顶点集 S，按照定理 2，删除 中与 S 顶 点都相邻或都不相邻的顶点，同时也删除顶点导 出子图 中所有边，称这样得到的图为关于顶 点集 S 的简化图，记作 。当 S 是独立集时， 是二部图。记 为 S 在简化图 中的补集。 S = {v1, v2,··· , vk} L 若 为独立集且为 k 完美关键 集，则 Laplace 矩阵 有一个特征向量： y = [y1 y2 ··· yk 0 ··· 0]T yi , 0, i = 1,2,··· , k 由 S 为独立集知 ∀vi ∈ S 有： L{vi}→V y = dG(vi)yi = λyi , i = 1,2,··· , k 即 dG(v1) = dG(v2) = ··· = dG(vk) = λ 。亦即当 S 为独立 集时，完美关键集 S 中顶点度均相等。基于此，定 理 5 给出了独立集成为关键集的一个充分条件。 GS S¯ GS GS 定理 5 设 S 为独立集， 为关于顶点集 S 的简化图。若 S 中所有顶点在图 G 中的度相 等，且 中所有顶点在 中的度均为偶数，则 S 为关键集。 S = {v1, v2,··· , vk} GS GS 证明 不防设 且 S 中所有顶 点在图 G 中的度均为 d。若简化图 为空图，则 由定理 2 知结论成立，下设 非空图。 ∀v ∈ S¯ GS GS Lv→S LS GS →S LS¯ Gs →S x = 0 x = [x1 x2 ··· xk] T ，由 v 在图 中的度为偶数知行向量 的所有分量求和为零 (模 2)，于是子矩阵 的列向量组线性相关，所以齐次线性方程 组 有非零解 。 ∑k i=1 xi = 0 GS vi(i = 1,2,··· , k) GS d ′ , 0 GS 我们断言 ，事实上，由 S 中所有顶点 在图 G 中的度均为 d 及简化图 的构造过程可 知顶点 在简化图 中的度也相 等，设为 (因 非空图)，于是 1 T 1×|S¯ Gs |LS¯ GS →S x = [d ′ d ′ ··· d ′ ]x = d ′∑k i=1 xi = 0 ∑k i=1 即有 xi = 0。 y = [x1 x2 ··· xk 0 ··· 0]T 取 ，λ = d ，则有 LS→V y = [LS→S LS→S¯ ] [ x 0 ] = LS→S x = [dx1 dx2 ··· dxk] T = λx ∀v ∈ S¯ ∑k i=1 xi = 0 L{v}→V y = 0 L{v}→V y = 0 ∀v ∈ S¯ Gs 对 ， 若 v 与 S 中顶点都相邻，则由 知 ；若 v 与 S 中顶点都不相邻， 则有 ；若 ，则有 L{v}→V y = [L{v}→S L{v}→S¯ ] [ x 0 ] = L{v}→S x = 0 Ly = λy y yS¯ = 0 综上可知 ，即向量 为 Laplace 矩阵的 特征向量，由于 ，故由定义 1 知 S 为关键集。 GS S¯ GS 2 例如，图 3 中的独立集 S，考虑其简化图 ， 在 中的所有顶点的度都为偶数 ，由定理 5 知 S 为 4 关键集。 简化图 S G S S GS S (a) 原图 (b) 简化图 GS 图 3 简化图及其关键集 Fig. 3 Simplification of graph G and its CS 第 3 期 戴丽：双向通信无人机集群领航顶点选取方法 ·487·