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

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

xadj 0 2 3 5

adjncy a c a a b b c

eptr 0 3 5

eind 0 1 2 2 3 0 3
图 2 存储结构

假设超点序号从 0 开始, 则第 i 个超点的邻接超边的序号保存于 adjncy[xadj[i]] 到 adjncy[xadj[i+1]–1], 第 i 个
超点的度为 xadj[i+1]–xad[j]; 类似的, 假设超边序号从 0 开始, 则第 j 条超边中包含的超点保存于 eind[eptr[j]] 到
eind[eptr[j+1]–1], 第 j 条超边的大小为 eptr[j+1]–eptr[j].
如图 2 所示, 2 号超点参与组成了 a 和 b 两条超边, 则在数组 adjncy 中, 2 号超点的邻接边序号从 xadj[2]=3 开
始, 到 xadj[2+1]–1=4 结束. 类似的, a 号超边 (在数组 eptr 中用 0 号超边来表示) 包含了 0, 1 和 2 这 3 个超点, 则在
数组 eind 中, a 号超点的邻接边序号从 eptr[0]=0 开始, eptr[0+1]–1=2 结束.

4 超图独立集的性质分析

首先本文基于超图的性质和超图独立集的定义, 提出以下两个性质.
性质 1. 对于同一超边上的 n 个点, 最多只能选择一个点加入独立集.
证明: 根据本文超图独立集定义, 一个独立集中任何两个超点都不能同时参与形成同一条超边, 则对于一个超
点 u∈e, 若超点 u 是一个超图独立集中的一个点, 假设有另一超点 v∈e 也是该超图独立集中的一个点, 这对于超
边 e, 它存在两个超点 u, v 都在独立集中. 显然这与定义不相符, 所以假设不成立.
性质 2. 对于同一条超边上的点, 与其选择该超边上与其他超边有邻接关系的点加入最大独立集, 不如选择该
超边上与其他超边没有有邻接关系的点. 一旦选择了该超边上与其他超边有邻接关系的点, 那么其他超边上的点
就也不能选了.
证明: 假设对于超图 G, 其最大独立集为 S. 则对于一条超边上的两点 u, v∈e, 若 degree(u)>1, degree(v)=1. 则
∃e′∈E, e′≠e, u∈e′. 若选择超点 u 加入独立集 S, 则由超边 e 和 e′中的其他超点就都不会再有机会加入独立集了.
此时 α(G)=α(G\e\e′)+1. 若选择超点 v 加入独立集 S, 则只有超边 e 中的其他点不能加入独立集. 此时超图独立集大
小 α(G)=α(G\e)+1. 显然 α(G\e)≥α(G\e\e′). 由此可知, 选择超点 v 的结果不差于选择超点 u, 则性质 2 得证.

5 超图最大独立集的基础算法

首先, 本文提出一种比较简单的基于贪心策略的超图最大独立集算法, 如算法 1 所示, 该算法主要根据性质 1
的思想来求解超图最大独立集.
算法 1. 超图独立集基础算法.

输入: 超图 G = (V,E) ;
输出: 超图 G 的最大独立集.
1. for v ∈ V of G do //初始化状态标记
2. State[v] = INITIAL
3. for v ∈ V of G do //遍历 INITIAL 超点
4. if State[v] = INITIAL then
State[v] = IS
5.