基于图论的配电网电气连通性分析算法

配电网电气连通性分析是配电网管理系统的基础,目前常用的电气连通性分析算法主要是邻接矩阵法,该方法由于具有结构性强、分析过程清晰而得到广泛的应用;但当网络规模充分大时,该方法用于连通性分析的运算时间将随节点数n的平方增长,算法时间开销大.文章结合图论理论和配电网的特点,提出了一种连通性分析新算法,算法通过构造支路状态矩阵来反映开关运行状态的变化,运用索引表和相邻点表来描述图的结构,压缩了数据的存储空间;并采用连通片生长法进行连通性搜索,降低了算法的时间复杂度.验算结果表明,该算法具有内存开销少,计算速度快等优点.同时,该算法可推广应用于其他与图的连通性分析有关的问题中.

Research on the Algorithm of Electric Connectivity Analyzing for Distribution Network Based on Graph Theory

Power distribution network connectivity analysis is the base of distribution management system. At present, the adjacent matrix method is used as the basic method for connectivity analysis in distribution network because its process with better data structure and clear analyzed procedure. But if the network scale expands, the adjacent matrix method would be extreme time-consuming. Thus it is not tolerable for great distribution network. A new connectivity analysis algorithm is presented in this paper. Branch status matrix is used to describe the status change of distribution network in this algorithm with a index table and a adjacent point table to describe the graph structure, and it can compress memory of date. A growth method of connected-component is introduced to make search of connectivity. The spending of time can be reduced effectively. Computer simulation shows that the algorithm is validity and feasibility. At the same time, the algorithm may be extended applied in other problems concerned with the connectivity check of graph.