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

代强强 等: 面向二部图的极大缺陷二团高效枚举算法 1803

等于 3 的所有顶点, 则 (A,B) 一定存在于 G v 中.
由于同一个极大 k-缺陷二团 (A,B) 同时包含在多个子图 G v 中, 从而造成了重复枚举. 为了避免该情况, 可以利
用排序进行子图划分. 设 O = {v 1 ,v 2 ,...,v n } 为二部图 G 中所有顶点 (包括 L 和 R ) 按照某种规则由低到高的排序. 令
≻2 v i 距离为 2 ≻2

N (G) 表示 G 中与顶点 且基于排序 O 比 v i 排名高的顶点集合, 即 N (G) = {v j ∈ O∧ L|i < j,N v i (G)∩
v i v i
2
2
(G) , ∅} . 设 G ≻ 表示 G 中由顶点集合 Γ (G) = N (G)∪{v i } 与 ∪ u∈Γ 2 (G) N u (G) 组成的诱导子图, 则有如下结论.
N v j
v i v i v i v i
定理 4. 给定 G 中任意极大 k-缺陷二团 (A,B) , 若 |A| ⩾ k +1 且 |B| ⩾ k +1 , 则 (A,B) 一定包含在子图 G 中, 其中
≻
v
v 为 A 中基于排序 O 排名最低的顶点.
2 A 中至少
证明: 因为 v 为 A 中基于 O 排名最低顶点, 则 Γ (G) 包含了 A 中所有的顶点. 此外, B 中任意顶点都与
v
≻ (A,B) .
某一个顶点存在邻居关系, 则子图 G 包含
v
定理 5. 给定 G 中任意极大 k-缺陷二团 (A,B) , 若 |A| ⩾ k +1 且 |B| ⩾ k +1 , 若 不是 A 中基于排序 O 排名最低
v
≻
的顶点, 则 (A,B) 一定不包含于子图 G 中.
v
2
证明: 因为 v 不是 A 中基于 O 排名最低的顶点, 则 A 一定不包含于 Γ (G) 中, 因此 A 不包含 (A,B) .
v
G 中枚举所有极大 G 中枚举所有极大 k-缺陷二
≻
基于上述结论, 从原始二部图 k-缺陷二团等价于从各个子图
v
团, 其中 v 属于 O∩ L (或者 O∩R ) 中. 本文利用传统图中广泛使用的退化排序 (degeneracy ordering) [20] 对 G 进行排
序, 其定义如下.
定义 5 (退化排序). 给定二部图 G , 退化排序为 G 中所有顶点 (包括 L 和 R ) 的一种排列 {v 1 ,v 2 ,...,v n } 使得任意
v i 在由 {v i ,v i+1 ,...,v n } 组成的诱导子图中度最小, 其中 i 为 [1,n] 中的整数.
基于一种传统的迭代删除方法 [31,32] , 退化排序可在线性时间内完成计算. 具体地, 给定二部图 G , 依次删除在
剩余顶点组成的子图中度数最小的顶点, 顶点的删除顺序组成了一种退化排序.

4.2 基于上界的剪枝技术
G 中枚举大小 (顶点数) 约束的极大 k-缺陷二团时, 其中可能存在某些顶点一定不包含于任何满足条件
≻
当从
v
的极大 ≻ (α,β) -
k-缺陷二团中. 为此, 还需要对
G 进行进一步的削减以减少不必要的计算. 下面首先介绍一种基于
v
核 [21] 的剪枝方法. |B|−q . 此外, 若
定义 6 ( (α,β) -核). 给定二部图 G , 若子图 G(A,B) 为 G 中的一个 (α,β) -核, 则对于 ∀v ∈ A (以及 ∀u ∈ B ) 均满
(
足 d v (G(A,B)) ⩾ α d u (G(A,B)) ⩾ β ).
基于 k-缺陷二团的定义, 显然有如下定理.
定理 6. 给定任意 k-缺陷二团 (A,B) G(A,B) 一定为一个 ( |B|−k |A|−k )-核.
,
,
≻ v 的极大 k-缺陷二团之前, 可以基于定理 使子图成为一个 q−k q−k )-核. 为进一步
为此从 G 中枚举包含 6 ( ,
v
v
减少冗余顶点, 本文发现, 在枚举包含 v 且大小约束的极大解时, 任何其他顶点与 至少存在 q−k 个共同邻居. 则
可以得到如下结论.
定理 7. 给定任意 k-缺陷二团 (A,B) , 对于任何两个顶点 v,u ∈ A , 一定有 |N v (G)∩ N u (G)| ⩾ |B|−q ; 若 v,u ∈ B , 同
|N v (G)∩ N u (G)| ⩾ |A|−q .
样有
证明: 因为顶点 v,u ∈ A 包含在同一个 k-缺陷二团中, 表明 (A,B) 中最多允许有 k 个顶点在 v 与 u 的非共同邻
居中. 为此 v 与 u 的共同邻居的数量一定不小于 v,u ∈ B , 也有类似结论.
基于定理 ≻ ≻ ≻ L 中删除与 共
v
≻
7, 本文设计了一种新的剪枝技术. 即给定子图
G = (L ,R v ,E v ) , 若
v
v v v ∈ L , 首先从 v
q−k 的顶点, 之后迭代重复上述操作直到所有顶点不能删除为
同邻居数量小于 q−k 的顶点, 然后从 R v 删除度数
止. 基于现有的剥离算法 [31,32] , 该剪枝技术的时间与子图的顶点数和边数成线性关系.

4.3 线性时间的更新技术
在算法 1 中, 当利用某个顶点 v 扩展当前解 (S L ,S R ) 时, 需要更新候选集和排除集以保持剩余顶点仍然可以扩展
新的当前解. 然而传统方法的时间复杂度与 (S L ,S R ) 的大小成多项式关系. 为提高更新效率, 本节介绍一种线性时间
的更新方法. 设候选集 (C L ,C R ) 中每个顶点是一个对结构, 即任何顶点 u ∈ C L (或者 u ∈ C R ) 包含了元素 id 与 nnd , 其