CAJ | 학술논문

无向图 G 的生成树问题，在电气工程和计算机科学领域应用广泛；针对Mayeda生成树不易编码实现问题，提出易于编码实现的Mayeda生成树实用算法及基于矩阵环和操作的实现方法。提出Mayeda生成树实用算法，并证明该实用算法生成树的不重复性和完备性；进而提出基于矩阵环和操作的实用算法的实现方法，以命题的形式证明了该实现方法的有效性；相对于遍历方法，该实现方法具有更高的计算效率。算法复杂性分析及算例均证明了所提方法的有效性。Mayeda生成树实用算法的完备性、不重复性(即不同的树支交换必定生成不同的树)以及基于矩阵环和操作实现方法的快速性，为基于它编码的电力系统配网重构随机进化优化快速获得其最优解奠定了理论基础。因此具有很好的工程应用前景。
무향도 G 적생성수문제，재전기공정화계산궤과학영역응용엄범；침대Mayeda생성수불역편마실현문제，제출역우편마실현적Mayeda생성수실용산법급기우구진배화조작적실현방법。제출Mayeda생성수실용산법，병증명해실용산법생성수적불중복성화완비성；진이제출기우구진배화조작적실용산법적실현방법，이명제적형식증명료해실현방법적유효성；상대우편력방법，해실현방법구유경고적계산효솔。산법복잡성분석급산례균증명료소제방법적유효성。Mayeda생성수실용산법적완비성、불중복성(즉불동적수지교환필정생성불동적수)이급기우구진배화조작실현방법적쾌속성，위기우타편마적전력계통배망중구수궤진화우화쾌속획득기최우해전정료이론기출。인차구유흔호적공정응용전경。
Spanning tree problem of undirected graph G is widely used in electrical engineering and computer science. Considering the uneasy-coded problem of Mayeda spanning tree method, a practical Mayeda spanning tree method and its implementation strategy based on matrix exclusive OR operation were proposed in the paper. The practical Mayeda spanning tree method was presented, and its unrepeatability and completeness in constructing new trees were proved;then the implementation strategy of the practical method whose computional efficiency is higher than the traversal method, was presented based on matrix exclusive OR operation. The complexity analysis result of the algorithm and the case study results verified the effectiveness of the method. The completeness and unrepeatability (means different branch exchanges consequentially generate different trees) of the practical Mayeda spanning tree method, and the capability of the implementation strategy to quickly construct a new tree, laid a theoretical foundation for quickly achieving optimal solutions of stochastic evolutionary optimization in power distribution network reconfiguration based on the proposed coding method, and thus is feasible.