写出求传递闭包的warshall 算法,某关系的序偶为 R=1≤12-,-1,4-,<1,5-,-2,1>,<2,3-,-3,4-,-3,5-,-4,1>,<4,3>,$3,4,<3.2-,<5;52),求此关系的传递闭包与对称递包,必须给出计算步骤,最后给出等价类。
时间: 2023-10-15 22:05:35 浏览: 74
Warshall传递闭包算法
Warshall算法是一种用于求解有向图传递闭包的经典算法,其基本思想是通过矩阵运算来快速计算出图的传递闭包。具体而言,Warshall算法可以通过以下步骤来计算有向图G的传递闭包:
1. 构建一个邻接矩阵A,其中A[i][j]为1表示存在一条从i到j的有向边,为0表示不存在这样的有向边。
2. 对于任意的i、j和k,如果A[i][j]=1且A[j][k]=1,则将A[i][k]设为1,表示存在一条从i到k的路径。
3. 重复上一步骤,直到A中的所有元素都不再变化为止。
以下是使用Warshall算法计算传递闭包的具体步骤:
1. 首先,根据给定的序偶,可以构造出一个邻接矩阵A,其中A[i][j]表示从i到j是否存在一条有向边。
```
1 2 3 4 5
1 1 0 0 1 0
2 0 0 1 1 1
3 0 0 0 0 1
4 0 0 1 0 0
5 0 0 0 0 0
```
2. 接着,按照Warshall算法的步骤,对邻接矩阵A进行运算,计算出其传递闭包B。
```
1 2 3 4 5
1 1 0 0 1 0
2 1 0 1 1 1
3 0 0 0 0 1
4 0 0 1 0 0
5 0 0 0 0 0
```
3. 最后,根据传递闭包B,可以计算出该关系的等价类,具体方法是将B转化为一个有向图,并对其进行拓扑排序,得到的每个强连通分量即为一个等价类。在这个例子中,对B进行拓扑排序后得到的强连通分量为{1,4}和{2,3,5},因此该关系的等价类为{{1,4},{2,3,5}}。
接下来,我们来计算该关系的对称递包。对称递包的计算方法是将关系R和它的逆关系R^(-1)取并集,并进行传递闭包运算。这里的逆关系指的是将R中的所有序偶的元素交换位置得到的关系。例如,序偶<1,5>的逆关系为<5,1>。
1. 首先,将关系R和它的逆关系R^(-1)合并得到关系S。
```
1 2 3 4 5
1 1 0 0 1 1
2 0 0 1 1 1
3 0 0 0 0 1
4 1 1 0 0 0
5 1 1 1 0 0
```
2. 然后,对关系S进行传递闭包运算,得到其对称递包T。
```
1 2 3 4 5
1 1 1 1 1 1
2 1 1 1 1 1
3 1 1 1 1 1
4 1 1 1 1 1
5 1 1 1 1 1
```
3. 最后,对于任意的i和j,如果(T[i][j]=1且T[j][i]=1),则(i,j)属于T的等价类,否则(i,j)不属于T的等价类。在这个例子中,T的等价类为{{1,2,4,5},{3}}。
综上所述,该关系的传递闭包为{{1,4},{2,3,5}},对称递包为{{1,2,4,5},{3}},其等价类分别为{{1,4},{2,3,5}}和{{1,2,4,5},{3}}。
阅读全文