基于含连通图约束的背包问题的图分割方法

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

Graph Partitioning Method Based on Connected Graph Constrained Knapsack Problem

Graph partition technology is significant in transportation,power grid fault diagnosis,power system partition,etc.In this paper,a new graph partition problem that is connected graph constrained knapsack problem(CGKP) was first built,and an efficient approximation algorithm was designed to solve it in the paper.Four node sets relating to graph connectivity were defined,the characteristics and searching methods of which were proved and provided in the form of propositions.On the basis of that,the algorithm of graph constrained knapsack problem(GKP) was extended,and the approximation algorithm for CGKP was achieved.The computation complexity of the algorithm was also thoroughly discussed.The test result of the sample demonstrates the validity of the proposed method.Since the optimal controlled partition of power system could be treated as a CGKP at some condition,all the above new node sets,propositions and algorithms for CGKP provide theory foundation for solving the optimal controlled partition of power system.