CAJ | 학술논문

针对在已有传递闭包的基础上新增序偶后的传递闭包求解问题，提出了一种基于新增序偶的传递闭包求解算法，并给出了详细证明过程。该算法在已有的传递闭包基础上，通过把新增序偶及该序偶的所有派生间接指向序偶添加到已有的传递闭包中实现求解过程，从而使算法的时间复杂度降低为O（n2），并且不受稀疏矩阵或序偶链的链长等不确定因素影响，最后通过一个实例说明了该算法的执行过程。
침대재이유전체폐포적기출상신증서우후적전체폐포구해문제，제출료일충기우신증서우적전체폐포구해산법，병급출료상세증명과정。해산법재이유적전체폐포기출상，통과파신증서우급해서우적소유파생간접지향서우첨가도이유적전체폐포중실현구해과정，종이사산법적시간복잡도강저위O（n2），병차불수희소구진혹서우련적련장등불학정인소영향，최후통과일개실례설명료해산법적집행과정。
A transitive closure solution algorithm based on new ordered couples was proposed , which aimed to solve transitive closure problems after adding new ordered couples to current transitive closure . The demonstration process was provided as well .In order to solve the problem , the new ordered couples and all the derivatives indirectly pointed to the ordered couples were added to the existing transitive clo -sure.Thus, the time complexity of the algorithm can be reduced to O (n2), while the algorithm will not be affected by sparse matrix or chain length of ordered couple chain .Finally, an example was given to il-lustrate the execution of the algorithm .