传递闭包R+的Warshall算法:
(1)置新矩阵A=M;(M为R对应的矩阵)
(2)置i=1;
(3)对所有j,如果A[j,i]=1,则对k=1,2,···,n,令
A[j,k]=A[j,k]+A[i,k];
(4)i=i+1;
(5)若i<n
设集合A=(a,b,c,d)上的关系:
R={< a,b>,< b,a>,< b,c>,< c,d>}
(i)用矩阵运算的方法求出R的自反、对称、传递闭包。
(ii)用Warshall算法,求出R的传递闭包。
设R为集合X上的二元关系,R在X上是反传递的定义为:若< x,y >∈R,< y,z >∈R,则证明:R是反传递的,当且仅当.
设R是有限集X上的一个二元关系,证明:
a)对于任意在X上的二元关系R,有R+是可传递的。
b)若有X上任何其他传递关系P,使得
c)R+就是定义3-8.1中所说的传递闭包。
证明下列断言:
(a)如果R是拟序,那么也是拟序。
(b)如果R是偏序,那么也是偏序。
(c)如果R是线序,那么也是线序。
(d)存在一集合S和S上的关系R,使(S,R)是良序集合,但不是。