集合论
当有限集A的元素较多时，对关系R的传递闭包t（R）进行矩阵运算，还是显得很为繁琐。为此，沃舍尔①在1962年提出了t（R）的一个有效算法。沃舍尔算法计算t（R）关系矩阵M=（mij）的步骤如下：
（1）M赋初值R的关系矩阵MR；
（2）置k=1；
（3）对所有i如果A=1，则对j=1，2，…，n执行： A←AA；
（4）k增1；
（5）如果k≤n，则转到步骤（3），否则停止。
所得的矩阵A即为关系R的传递闭包t（R）的关系矩阵。
沃舍尔算法从关系矩阵M的第一列开始到第n列结束，逐步检查其每行元素是否为1，若mij=1，则将第j行元素对应加（布尔加）到第i行元素上去。
问题：如何证明沃舍尔算法的结果就是所求的传递闭包？
页:
[1]