离散数学实验四关系闭包

一、实验目的
了解Warshall算法的基本原理，熟练运用该算法计算关系的自反闭包、对称闭包以及传递闭包的具体步骤。

二、实验内容

    定义1  设R是A上的二元关系，R的自反（对称、传递）闭包是关系R1，则
    
    
      
    

① R1具备自反性（对称性、传递性）
② R包含于R1
③ 对所有具有自反性（对称性、传递性）的关系R2，若R包含于R2，则R1包含于R2。
R的自反闭包、对称闭包与传递闭包分别表示为r(R)、s(R)与t(R)。

    定理1  令RAA，则
    
    
      
    

① r®=R∪IA
② s®=R∪R-1
③ t®=R∪R2∪R3…

    Warshall算法：设R是n个元素集合上的二元关系，M是R的关系矩阵；
    
    
      
    

(1)设定新矩阵A:=M
(2)设定i:=1；
(3)for j=1 to n do
若A[j,i]=1则执行以下操作：
for k=1 to n do
A[j,k]:=A[j,k]+A[i,k]
(4)i=i+1；
(5)若i<=n则跳转至(3)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)(17