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

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

′
′ ′ (S ,S R ) ;
,
25. 更新 C , C R X , X R 使其中任意顶点均可用于扩展当前解
L L L
,
26. Branch( S ′ , S R C L \{v} C R X L X R );
,
,
,
L
,
,
,
,
27. Branch( S L S R C L C R X L \{v} X R );
,
28. end if
算法 1 主要调用 Branch 函数来给定二部图 G 中所有的极大 k-缺陷二团, 该函数需要调用 6 个参数, 分别为:
S L 、 S R 、 C L 、 C R 、 X L 以及 X R . 其中 (S L ,S R ) 表示当前解, (C L ,C R ) 表示候选集以及 (X L ,X R ) 表示排除集. 初始阶
R (第 1 行). 函数 Branch 在递归调用之
段, 参数 S L 、 S R 、 X L 和 X R 均设置为空集, 而 C L 和 C R 分别设置为 L 与
前, 首先需要判断 (C L ,C R ) 和 (X L ,X R ) 是否为空集, 若 (C L ,C R ) 为空集则表示没有顶点可用于扩展当前解, 该递归调
用终止迭代 (第 3、7 行). 与此同时, 若 (X L ,X R ) 也为空集, 则当前解 (S L ,S R ) 在 G 中一定是一个极大解, 可作为结果
输出 (第 4、5 行), 因为二部图 G 中在 (C L ,C R ) 与 (X L ,X R ) 之外的顶点一定无法扩展 (C L ,C R ) .
然后, 函数 Branch 计算 (S L ,S R ) 在候选集 (C L ,C R ) 中的非共同邻居集合 D L 与 D R (第 9 行). 若 D L 与 D R 中存在
一个集合满足定理 1 中用于扩展当前解的条件, 则算法利用其中之一来执行对称集合枚举技术 (第 10 或 21 行).
上界的剪枝技术, 线性时间的更新技术以及分支优化技术.
¯
值得注意的是, 当前解 (S L ,S R ) 中可能已经存在一些边缺失, D L 或 D R 中最多有 k −d(S L ,S R ) 个顶点加入 (S L ,S R )
¯
¯ s k −d(S L ,S R ) (第 9 行), 基于定理 s+1 个子
中, 其中 d(S L ,S R ) 表示子图 (S L ,S R ) 中缺失的边数. 令 为 1, 最多可产生
} , 函数 Branch 首先调用子递归枚举不包含
分支. 假设函数是从 D L 中选择顶点执行子递归调用, 设 D L = {v 1 ,...,v d L
v 1 的极大 k-缺陷二团 (第 11 行), 其次枚举包含 {v 1 ,...,v i−1 } 但不包含 v i 的极大 k-缺陷二团 (第 12–17 行), 最后枚举
{v 1 ,...,v s } 的极大 k-缺二团 (第 18–20 D R 的大小都不满足条件时 s ), 函数将从候
包含 行). 此外, 当 D L 与 (大于等于
v
v
选集 (C L ,C R ) 中随机选择一个顶点分别枚举包含 与不包含 的极大 k-缺陷团以保证递归的继续执行 (第
23–28 行).
(S L ,S R ) 之后, 候选集中可能存在某些顶点不再能够用于
需要注意的是, 当某个顶点 v 或者集合 {v 1 ,...,v i } 加入
′ (C L ,C R ) (以及排除集
扩展新的当前解 (S ,S R ) 了. 为了删除这些顶点, 最直接的方法是, 算法依次遍历候选集
L
′
(X L ,X R ) ) 中每个顶点, 然后尝试加入 (S ,S R ) 中, 并判断是否能够组成更大的 k-缺陷二团. 如果不能, 则该顶点从候
L
选集 (或者排除集) 中删除, 剩余的每个顶点均可用于扩展新的当前解.
定理 2. 算法 1 正确并唯一地输出了二部图 G 中所有满足给定阈值条件的极大 k-缺陷二团.
G 中任意的极大 (A,B) 能够
证明: 设 (A,B) 为 k-缺陷二团, 其中 A = {v 1 ,...,v A } 以及 B = {u 1 ,...,u B } , 则只需证明
被算法 1 唯一枚举. 定理 1 证明了算法 1 一定会输出极大解 (A,B) , 则只需证明当 (A,B) 被枚举后, 包含 (A,B) 的非
极大解不会被输出. 由于算法是基于深度优先的方式扩展当前解 (S L ,S R ) , 因此算法一旦输出 (A,B) 则顶点 v A 或者
u B 将被放入到排除集中. 那么对于其他满足 S L ⊆ A 且 S R ⊆ B 的子递归分支, v A 或者 u B 一定存在于当前的排除集
合中, 则任何包含 (A,B) 的非极大解都不会输出. 因此, 得证.

4 优化技术
为了进一步提高所提出算法的性能, 本节将介绍一系列的优化方法. 主要包括基于排序的子图划分技术, 基于

4.1 基于排序的子图划分技术
2 v 距离为 2
给定 L 中的一个顶点 v , 令 N (G) 表示 G 中与顶点 2 的顶点集合, 即 N (G)={u∈L\{v}|N v (G)∩ N u (G),∅} .
v
v
2 2 u 同样有如
本文用 G v 表示 G 中由顶点集合 Γ (G) = N (G)∪{v} 与 ∪ u∈Γ 2 (G) N u (G) 组成的诱导子图. 对于 R 中的顶点
v
v
v
上定义, 则可以得到如下结论.
定理 3. 给定 G 中任意极大 k-缺陷二团 (A,B) , 若 |A| ⩾ k +1 且 |B| ⩾ k +1 , 则 (A,B) 一定包含在子图 G v 中, 其中
(A,B) 中的任意顶点.
v 为
证明: 基于性质 2, 若 |A| ⩾ k +1 且 |B| ⩾ k +1 , 则 G(A,B) 的直径一定不大于 3. 又因为 G v 包含了与 距离小于
v