华氏运算法则.pptVIP

微机021 钟尚勤 0214020110 设R是集合A={a1，a2，……，an}上的一个关系。如果x1,x2,……,xm是上的一条路径，那么，除x1和xm外的顶点都叫做这条路径的内部顶点。现在，对于1≤k≤n，我们定义一个布尔矩阵如下。 wk在i行、j列上有一个1，当且仅当在上有一条从ai到aj的路径，其中它的内部顶点只能来自于集合{a1，a2，……，ak} 。 由于顶点都来自集合{a1，a2，……，an},所以必然有矩阵Wn在位置i、j上有一个1,当且仅当在R上有某一条路径连接ai和aj。换言之，Wn =M R∞。如果我们定义W0为MR，那么我们会得到一组序列W0，W1，……Wn，即以W0开头，以M R∞结束。 我们将演示一下怎样通过前面的矩阵Mk-1计算每个矩阵Mk。那么，我们可以从矩阵R开始，依次进行每一步，进行n步，直到我们得到矩阵R∞为止。这种程序就叫做华沙运算法则。这些矩阵Wk不同于矩阵MR的幂，这种不同使得保存计算的传递闭包过程中的步骤有可能成为现实。 图4.44 假设Wk=[ti j]， Wk-1=[Si j]。如果ti j=1，那么，一定有一条从ai到aj的路径，其内部顶点来自集合{a1，a2，……，ak} 。若顶点ak不是该路径的内部顶点，那么所有内部顶点一定来自集合{a1，a2，……，ak-1} ，所以si j=1。若ak是内部顶点，则其位置关系就如图4.44所示。根据定理2的证明，我们可以设想所有内部顶点都是独立的。所以ak只在路径中出现一次，那么所有分路1和分路2的内部顶点一定都来自集合{a1，a2，……，ak} 。这意味着si k=1和sk j=1。因此，t I j=1，当且仅当（1） si j=1或（2） si k=1并且sk j=1 。这就是华沙运算法则的基础。 如果Wk-1在位置i j上有一个1，那么，由（1）得Wk在位置上也有一个1，由（2）可得一个新的1可以加到Wk的位置i j上，当且仅当Wk-1的k列上位置i处和k行上位置j处都有一个1。于是我们从Wk-1计算Wk有下述步骤。 步骤1：首先把Wk-1中全部的1迁移到Wk中。 步骤2：列出Wk-1中k列上有1的位置p1， p2…… ，并 且列出Wk-1中k行上有1的位置q1， q2…… 步骤3：将1放到Wk中所有位置为pi qj 处。（如果该 处原来没有1） 例1 设A={1,2,3,4}，并且让R={ (1,2),(2,3),(3,4),(2,1) }。求R的传递闭包。 解：有已知有 W0=MR= ( n=4) 首先计算W1，此时k=1，由于W0在第1列位置2处和第1行位置2处都有1，所以W1在W0基础上，在位置2，2处加上一个1。得： W1= 现在来算W2，此时K=2，这时须参考W1的第2列和第2行。矩阵W1在第2列上位置1和2处以及在第2行上位置1，2，3处都有1，所以，要得到W2 ，我们必须把1放到W1中位置1，1；1，2；1，3；2，1；2，2和2，3处（如果该处原来没有1）。 我们得到： W2= 接下来，我们看到W2中的第3列位置1，2处有1，而第3行中位置4处有1，要得到W3，我们必须把1放到W2中位置1，4和2，4处，于是 W3= 最后， W3在第4列位置1，2，3处有1，但在第4行中无1，所以没有新的1增加，于是M R∞ = W4= W3。该结论与我们在课本上例1中结果相同。 例2 设A={a，b，c，d}，R={（a，a），（a，b），（a，d），（b，c），（c，b），（a，d），（d，c）}。 解： W0=MR= 华氏运算法： 1. CLOSURE=MAT 2.对于K=1，2，……，N （1）对于I=1，2，……，N 对于J=1，2，……，N CLOSURE[I，J]= CLOSURE[I，J] V（ CLOSURE[I，K]Λ CLOSURE[K，J]） （结束） 通过上两例对计算过程的说明，产生出以下运算法则，用以求用NXN矩阵（MAT）表示的关系R的传递闭包CLOSURE。 * *