摘要：图分割技术（网络分割技术）在互联网研究、交通运输、电网故障诊断和电力系统解列等方面有着重要的意义。首次建立一个新的图分割问题——含连通图约束的背包问题（connectedgraphconstrainedknapsackproblem，CGKP），并提出其有效近似算法。引入与图连通性相关的4个新节点集合，证明这些新节点集合的性质，并提出这些节点集合的搜索方法；结合新节点集合的性质及搜索算法，通过对含图约束的背包问题近似算法进行扩展，提出求解CGKP的近似算法，并讨论此算法的计算复杂性。算例结果证明了该算法的有效性。因电力系统主动最优解列问题在一定条件下可归结为一个CGKP，该研究成果为电力系统最优主动解列断面搜索问题的求解奠定了理论基础。

关键词：图分割 含连通图约束的背包问题 含图约束的背 包问题 近似算法 

单位：智能电网教育部重点实验室（天津大学） 天津市南开区300072 天津市电力公司技术中心 天津市西青区300384 东北电力调度通信中心 辽宁省沈阳市110180