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

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

E (A,B) = {(u,v) ∈ E|u ∈ A,v ∈ B} . 为了方便描述, 本文所述的子图在未特别说明情况下
(A,B) 组成的诱导子图, 其中
均为顶点集合组成的诱导子图. 此外, 本文用 d v (A) 或者 d v (B) 表示顶点 v 在集合 A 或者 B 中的邻居个数, 即
d v (A) = |{u ∈ A|(u,v) ∈ E}| d v (B) = |{u ∈ B|(u,v) ∈ E}| ). 下文正式定义了 k-缺陷二团的概念.
(
定义 1 (k-缺陷二团). 给定一个二部图 G 以及一个正整数 k, 若子图 G(A,B) 中至少存在 |A|×|B|−k 条边, 则称
G 中的一个 k-缺陷二团.
G(A,B) 为
基于定义 1, 若 G 中不存在其他满足 A ⊆ A 和 B ⊆ B 的子图 G(A ,B ) 也是一个 k-缺陷二团, 则称 G(A,B) 为 G
′
′
′
′
中的极大 k-缺陷二团. 可以看出, 当 k = 0 时, k-缺陷二团等价于二团. 因此二团可以看作是 k-缺陷二团的一种特殊
情况. 下面将介绍两个关于 k-缺陷二团的重要性质, 其为设计具体的算法提供了方便. 为了叙述方便, 下文将直接
(A,B) 表示
使用 k-缺陷二团 G(A,B) .
性质 1. k-缺陷二团满足继承性, 即对于给定的任意 k-缺陷二团 (A,B) , 其每个子图 H 仍然是一个 k-缺陷二团.
证明: 假设 H 不为 k-缺陷二团, 则 H 中至少存在 k +1 条缺失的边. 当将 G(A,B) 中 H 之外的边加入 H 时, 子图
G(A,B) 不是一个 k-缺陷二团. 因此, 造成矛盾.
H 中缺失的边数不变, 表明
在二部图 G 中, 设 dis(G,u,v) 为顶点 u 与 v 在 G 中的最短距离. 本文用顶点间最长的最短距离表示该图的直
(X L ,X R ) , 候选集中已经用于扩展过当前解
max ∀u,v∈G (dis(G,u,v)) , 则对 k-缺陷二团, 有如下性质.
径, 即
性质 2. 给定任意的 k-缺陷二团 (A,B) , 若 |A| ⩾ k +1 且 |B| ⩾ k +1 , 则 G(A,B) 的直径最大为 3.
证明: 基于 k-缺陷二团 (A,B) 的定义, 对于集合 A 中任意两个顶点 u 1 与 u 2 , 满足 d u 1 (B)+d u 2 (B) ⩾ 2|B|−k , 其中
G(A,B) 的直径为 2|B|−k ⩾ |B|+1 . 因
(B) 表示 u 1 在 B 中的邻居个数. 此外, 若 3, u 1 与 u 2 一定存在共同邻居, 则有
d u 1
此, 可以推出 |B| ⩾ k +1 . 类似地, 基于集合 B 中任意两个顶点 v 1 与 v 2 之间的邻居关系也可以推出 |A| ⩾ k +1 . 因此, 得证.
基于性质 1, 可以容易判断给定的 k-缺陷二团 (A,B) 在 G 中是否是极大的, 即当 G 中存在其他顶点 加入
v
(A,B) 组成更大的 k-缺陷团, 则 (A,B) 是非极大的; 否则, (A,B) 是非极大的. 基于性质 2 可以看出, 对于任何
|A| ⩾ k +1 且 |B| ⩾ k +1 的极大 k-缺陷二团, 其一定是紧密连接的. 表明较大的 k-缺陷二团可以作为二部图中的稠密
子图. 因此本文将重点研究枚举顶点数满足一定阈值的极大 k-缺陷二团, 其正式的问题定义如下.
G 以及两个正整数 k G 中枚举所有顶点数量满足
问题定义. 给定二部图 和 q ⩾ k +1 , 本文的目标是从图
|B| ⩾ q 的极大 (A,B) .
|A| ⩾ q 和 k-缺陷二团
基于文献 [25], 从二部图中搜索满足继承性的最大子图是一个 NP-难问题, 则枚举所有极大 k-缺陷二团的问
题也是一个 NP-难问题. 接下来, 本文将介绍一种高效的算法以解决该问题.

3 极大缺陷二团枚举算法

本节将介绍一种新的极大 k-缺陷二团枚举算法, 其主要思想是基于一种对称集合技术. 该技术与传统的集合
枚举形成对称关系, 并且具有更强的冗余分支剪枝能力, 从而具有更高的计算性能.

3.1 对称集合枚举技术

在介绍具体的枚举技术之前, 首先介绍几种频繁使用的概念.
定义 2 (当前解). 集合 (S L ,S R ) , 满足 k-缺陷二团的定义, 但不一定是极大的.
定义 3 (候选集). 集合 (C L ,C R ) , 其中任何顶点均可加入当前解 (S L ,S R ) 组成更大的解.
定义 4 (排除集). 集合 (S L ,S R ) 的顶点集合.
基于上述定义, 一种最基本的极大 k-缺陷二团的方法是: 首先设置当前解为空集, 并设置候选集为 (L,R) , 然
后递归地从候选集中选择顶点来扩展当前解以枚举候选集中的所有子集. 可以看出每次递归一定存在与候选集大
小相等的子分支数量, 所以具有非常低的性能. 为此, 下面将介绍一种对称集合枚举的方法来减少子分支的数量.
给定当前解 (S L ,S R ) 与候选集 (C L ,C R ) , 可以发现集合 S L ∪C L 中任何包含 S L 的子集一定满足如下情况之一,
i
即包含 C L 的前 i−1 个顶点但不包含第 个顶点, 其中 i ∈ [1,n+1] 的整数. 基于该思想, 可以设计一种递归方法以
枚举给定二部图 G 中所有极大的 k-缺陷二团. 令 Br = ⟨S L ,S R ,C L ,C R ,X L ,X R ⟩ 为某个递归分支. 设 C L = {v 1 ,...,v n } , 则