求二元关系传递闭包的新方法  

A New Way on Binary Relation Transitive Closure

作　　者：赵玉兰[1] 车淑兰[1] 

机构地区：[1]内蒙古大学计算机学院,内蒙古呼和浩特010021

出　　处：《内蒙古大学学报（自然科学版）》2000年第5期541-543,共3页Journal of Inner Mongolia University：Natural Science Edition

摘　　要：二元关系的闭包运算在网络、语法分析以及开关电路中的故障检测和诊断等领域有着重要的作用 .通过求二元关系各幂的并获得关系闭包方法后来被认为是十分困难的和甚为繁琐的 .在三十多年前 ,War Shall给出了一种算法 ,使问题得以简便解决 .但是该算法存在着大量不必要的重复计算 .本文就此做了改进 .改进的算法比 War Shall的算法在时间复杂度从 O( n3)上能够降低到 O( n2 )Closure operation of binary relation plays an important role in network, parsing and detection and diagnosis of malfunction in switch circuit. The way of gaining relation closure by calculating the union of binary relation is thought to be very difficulty and complex. WarShall gave an algorithm thirty years ago. The algorithm simply solved the problem, but it existed a lot of unnecessary repeated calculations. This paper improved it. The improved algorithm can reduce time complexity to O(n 2) compared with Warshall algorithm whose time complexity is O(n 3).

关 键 词：传递闭包 时间复杂度 二元关系 离散数学 

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