Page 394 - 《软件学报》2025年第4期

1800 软件学报 2025 年第 36 卷第 4 期

基于 C L 中的顶点可以将分支 Br 划分为如下 |C L |+1 个子分支:
Br i = ⟨S L ∪ D i−1 ,S R ,C L \D i ,C L \{v i },C R ⟩ , 其中 D i = {v 1 ,...,v i } 且 i ∈ [1,n+1] .
C R 扩展当前解. 为了进一
上述针对 Br 的分支过程称之为对称集合枚举. 值得注意的是, 同样可以利用候选集
步阐述对称集合枚举的思想, 图 2 展示了使用候选集 C = {v 1 ,v 2 ,...,v n } 来扩展当前解的枚举树.

{v 1 , v 2 , …, v n }

…
−v 1 ; −v 2 ; −v 3 ; −v i ; − ;
+ +{v 1 } +{v 1 , v 2 } +{v 1 , v 2 , …, v i−1 } +{v 1 , v 2 , …, v n }
图 2 对称集合枚举树
然而直接利用上述方法, 递归分支 Br 的子分支数量仍然与 C L 的大小相关. 考虑到 k-缺陷二团最多允许缺陷
C L \N(S R ) 中最多允许 S R 的共同邻居, 即
k 条边的限制, 则候选集 k 个顶点同时扩展当前解, 其中 N(S R ) 表示顶点
N(S R ) = {u ∈ L|S R ⊆ N u (G)} . 为此可以得到如下针对 k-缺陷二团枚举的扩展方式.
v 4
定理 1. 给定递归分支 Br = ⟨S L ,S R ,C L ,C R ,X L ,X R ⟩ , 设 D = C L \N(S R ) = {v 1 ,v 2 ,...,v d } , 其中 d = |C L \N(S R )| . 若
|D| > k , 则如下 k+1 个子分支可用于枚举所有包含 (S L ,S R ) 的极大 k-缺陷二团:
● 第 1 个子分支为 Br 1 = ⟨S L ,S R ,C L \{v 1 },C L \{v 1 },C R ⟩ ;
● 第 i 个子分支为 Br i = ⟨S L ∪{v 1 ,...,v i−1 },S R ,C L \{v 1 ,...,v i },C L \{v i },C R ⟩ , 其中 i 为 2 到 k 的整数;
● 第 k+1 个分支为 Br k+1 = ⟨S L ∪{v 1 ,...,v k },S R ,C L \{v 1 ,...,v d },C L ,C R ⟩ .
由定理 1 可知, 若候选集中存在至少 k+1 个当前解的非共同邻居时, 递归分支 Br 的子分支个数仅与 k 的大小
有关与候选集的大小无关. 在实际应用中, k 通常取值较小, 为此该分支方法相较于基本的对称集合枚举具有更高
的效率. 下面的例子进一步阐明了定理 1 相较于基本的对称集合枚举的优势.
为了阐述定理 1 从图 3 的二部图 G 中枚举包含 (S L ,S R ) 的极大 k-缺陷二团的分支过程, 其中 k = 2 S L = {u 1 }
,
以及 S R = {v 1 } , 图 4 展示了一个具体的实例, 其中黑色部分的子分支由定理 1 得到, 子分支数量为 3; 灰色部分的
子分支为冗余分支. 在递归分支之前, 需要计算 S L 在候选集 C R 中的非共同邻居, 即 C R \N(S L ) = {v 3 ,v 4 ,v 5 ,v 6 } .
由于 C R \N(S L ) 的大小大于 k, 为此可以选择 C R \N(S L ) 中前 k 个顶点执行定理 1 的分支过程. 具体地, 第 1 个子分
v 3 的极大 k-缺陷二团; 第 2 v 4 的极大 k-缺陷二团; 第 3 个子分
支为枚举不包含 个子分支为枚举包含 v 3 但是不包含
支为枚举包含 {v 3 ,v 4 } 的极大 k-缺陷二团. 值得注意的是, 基于 k-缺陷二团的定义, C R \N(S L ) 中最多允许 k 个顶点
C R \N(S L ) 中不存在大
加入当前 (S L ,S R ) 中, 为此在枚举包含 {v 3 ,v 4 } 的子分支中, 候选集一定不包含 {v 5 ,v 6 } . 此外,
于 k 个的顶点加入当前解中, 因此该分支方法的子分支数量仅为 k +1 = 3 个, 与候选集 C L (或者 C R ) 的大小无关.
表明该方法可以极大地减少冗余分支的数量.

u 1 u 2 u 3 u 4 u 5

v 1 v 2 v 3 v 5 v 6
图 3 二部图例图

C R \N(S )={v 3 , v 4 , v 5 , v 6 }
L

−v 3 ; −v 4 ; −v 5 ; −v 6 ; − ;
+ +{v 3 } +{v 3 , v 4 } +{v 3 , v 4 , v 5 } +{v 3 , v 4 , v 5 , v 6 }
图 4 当 k = 2 时枚举包含 (S L = {u 1 },S R = {v 1 }) 的对称集合枚举树