传递闭包的增量式更新研究  

Research on the incremental updating of the transitive closure

作　　者：汪小燕[1] 杨思春[1] 叶红[1] 周建平[1] 

机构地区：[1]安徽工业大学计算机科学与技术学院,安徽马鞍山243032

出　　处：《苏州科技学院学报（自然科学版）》2015年第1期45-48,共4页Journal of Suzhou University of Science and Technology （Natural Science Edition）

基　　金：安徽省高校自然科学基金资助项目(KJ2012Z024;KJ2012Z031)

摘　　要：针对二元关系中添加序偶原有传递闭包更新问题,先提出一种新的传递闭包算法,并基于新的传递闭包算法给出传递闭包的增量式更新方法,只需要在原有传递闭包的基础上,根据所添加的不同序偶,进行简单的更新即可,利用该方法可以较快地实现动态变化的二元关系传递闭包的求解。Aimed at the updating problem for transitive closure when ordered pairs added to a binary relation,we put forward a new transitive closure algorithm. Based on this new transitive closure algorithm,the paper proposed a new method for the incremental updating of the transitive closure. According to the different ordered pairs added to a binary relation,the transitive closure of the new binary relation can be obtained by simply updating the original transitive closure. Using this method,we can achieve the solution for the transitive closure of a dynamic binary relation more effectively.

关 键 词：二元关系 传递闭包 恒等关系 增量 更新 

分 类 号：O158[理学—数学]