Page 430 - 《软件学报》2024年第6期

3006 软件学报 2024 年第 35 卷第 6 期

剩一条边. 如算法 3 的第 12, 13 行所示, 若它的所有邻接超边的 size 全部大于 1, 则所有邻接超边都不只包含超点
v, 则可应用剪枝 2, 删除遍历 N v 中的所有超边, 从这些超边的包含点中删除超点 v, 并更新这些超边的 size. 如算
法 1 的第 14–16 行所示, 若它的所有邻接边的 size 中有部分为 1, 则部分邻接超边只包含超点 v 这一个超点, 则可
应用剪枝 2, 删除 N v 中的所有 size 为 1 超边, 之后更新超点 v 的度, 同时更新超点 v 在 T G 中的位置. 当所有剩余
的超点的 degree 都不大于 1 时, 遍历所有剩余的超边, 此时所有剩余的超边彼此之间没有邻接关系, 都是由若干
度为 1 的超点组成的. 则此时在每条剩余超边中选取一个点加入超图独立集, 与应用剪枝 1 时已加入超图独立集
的点合并, 得到最终的超图最大独立集.
算法 3. 超图独立集改进算法.

G = (V,E) ;
输入: 超图
输出: 超图 G 的最大独立集.

N u = {e ⊆ E | u ∈ e},H = ∅
1.
2. T G 是 v ∈ G 的按 degree 降序序列
v ∈ V do //剪枝 1
3. for
4. if degree[v] = 1 then
5. 从 E 中删除 N u
6. H = H ∪{v}
,
7. while ∃v ∈ V degree[v] > 1 do
8. 从 T G 中取最高度超点 v
,
9. if ∀e ∈ N v size(e) = 1 then //剪枝 4
10. 从 E 中删除 N u , 但要留一条超边
11. degree(v) = 1 并更新 T G
∀e ∈ N v size(e) > 1 then //剪枝 2
12. else if , 个, 分别为超点
13. 删掉 v 并更新 N v 中边的 size
14. else //剪枝 3

15. degree(v)− = N v&size(e)=1
16. 删除 N v&size(e)=1 更新 T G
17. for e ∈ E do //遍历剩余超边
e 中的一个超点
18. u 为
19. H = H ∪{u}
20. return H
以图 8 为例, 图中超图共有 10 个超点, 8 条超边. 度为 1 的超点有 3 个, 分别为超点 2, 4, 6; 度为 2 的超点有
4 个, 分别为超点 3, 5, 9, 0; 度为 3 的超点有 4 3, 5, 9, 10. 若使用算法 3 处理该图, 首先枚举图中的
度为 1 的超点, 即 3 个红色超点. 根据 one-degree 点精确剪枝规则, 可将 2, 4, 6 这 3 个点加入超图独立集, 同时删
除这 3 个超点所在的边. 这个操作会导致图中 4 个绿色超点, 即 1, 3, 5, 7 被删除. 上述操作完成后, 原图中还剩下
8, 9, 0 这 3 个点. 按照 degree 由高到低次序访问, 首先访问度为 3 的蓝色超点 8. 超点 8 有 3 条邻接超边, 其中 1
条 size 为 1, 2 条 size 为 2, 则可应用 one-size 边精确剪枝 a, 将超点 8 的 size 为 1 的邻接超边删除. 此时原图中依
然还剩下 8, 9, 0 这 3 个点, 但 3 个点的 degree 都是 2. 若再次取最高度节点取到了超点 8, 此时超点 8 有两条邻接
超边, size 均为 2, 则可应用 high-degree 点近似剪枝, 删除蓝色超点 8. 接下来, 再次取最高度节点取到了超点 9, 此
时超点 9 有两条邻接超边, 其中一条 size 为 1, 另一条 size 为 2, 则可应用 one-size 边精确剪枝 a, 将超点 9 的 size
为 1 的邻接超边删除. 之后再次取最高度超点 0, 与超点 9 相同, 也可应用 one-size 边精确剪枝 a, 将超点 0 的 size