文章目录一、闭包求法二、求闭包示例 ( 关系图角度 )三、求闭包示例 ( 关系矩阵角度 )四、闭包运算与关系性质五、闭包复合运算一、闭包求法R 关系是
A 集合上的二元关系 ,
R \subseteq A , 且
A 集合不为空集 ,
A \not= \varnothing求自反闭包 :
r(R) = R \cup I_A , 给每个顶点添加环 ;
如果 R 关系是自反的 , 当且仅当 ,
I_A \subseteq R求对称闭包 :
s(R) = R \cup R^{-1}原来 没有有向边 ( 有序对 ) , 自然也没有对应的逆 , 此时不添加边原来 有一条有向边 ( 有序对 ) , 再添加一个反向的有向边 , 组成 关系图中的 顶点间的 双向有向边原来 有两条有向边 ( 有序对 ) , 此时就不用添加其它边如果 R 关系是对称的 , 当且仅当 ,
R = R^{-1}求传递闭包 :
t(R) = R \cup R^2 \cup R^3 \cup \cdots将
R 关系所有的幂运算值并起来 , 就是其传递闭包 ,
R 关系的
1 次幂 ,
R 关系的
2 次幂 ,
R 关系的
3 次幂 ,
\cdots ,
R 关系的
n 次幂 , 并起来 , 就是其传递闭包 ;
如果
A 是有穷集 , 其关系也是有穷的 , 求出其所有的
n 次幂 , 不用求出很多幂运算 , 因为关系的幂运算后面都是循环的 , 求出已知的所有
n 次幂 取 并集即可 ;
如果
R 关系是传递的 , 当且仅当 ,
R^2 \subseteq R二、求闭包示例 ( 关系图角度 )集合
A = \{ a, b, c , d \}关系
R = \{
R 的自反闭包
r(R) , 对称闭包
s(R) , 传递闭包
t(R)求自反闭包 : 就是给每个顶点加上环 :
求对称闭包 : 将 顶点间 单向边改成双向边 , 不管 顶点间双向边 和 顶点间没有边 的情况 ;
求传递闭包 : 将能到的点直接连起来 ;
a 可以到 b , 路径 a -> b ; a 可以到 c , 路径是 a -> b -> c ; a 可以到 d , 路径是 a -> b -> c -> d ; 因此添加 a 到 c , d 的有向边 ;b 可以到 a , 路径 b -> a ; b 可以到 c , 路径是 b -> c ; b 可以到 d , 路径是 b -> c -> d ; 因此添加 b 到 d 的有向边 ;c 可以到 d , 路径 c -> d ; 没有可连接的边 ;d 哪都到不了 , 没有可连接的边 ;另外出现双向边时 , 两个顶点必须加环 ;三、求闭包示例 ( 关系矩阵角度 )关系
R = \{
将上述关系写成矩阵形式为 :
M(R) = \begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix}自反闭包 : 将主对角线值 , 全部改成
1 , 左上角到右下角为主对角线 ;
M(r(R)) = \begin{bmatrix} 1 & 1 & 0 & 0 \\\\ 1 & 1 & 1 & 0 \\\\ 0 & 0 & 1 & 1 \\\\ 0 & 0 & 0 & 1 \end{bmatrix}对称闭包 : 主对角线两端要对称 , 以对角线为基准 , 使对角线两边的值对称 ;
M(s(R)) = \begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \end{bmatrix}传递闭包 : 求该关系矩阵的 二次幂 , 三次幂 , 四次幂 ,
\cdots , 直到出现相同的循环的值为止 ;
将上述所有的不同的 矩阵幂运算 进行逻辑相加 ( 或 ) 操作 , 就是其传递闭包对应的矩阵 , 计算机算法适合使用该方法 , 如果人计算 , 还是关系图比较形象 ;
参考 : 【集合论】关系表示 ( 关系矩阵 | 关系矩阵示例 | 关系矩阵性质 | 关系矩阵运算 | 关系图 | 关系图示例 | 关系表示相关性质 ) 四、关系矩阵运算
注意逆序合成
M(R^2) = M(R \circ R) = M(R) \bullet M(R) =\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} \bullet \begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix}M(R^3) = M(R^2 \circ R) = M(R) \bullet M(R^2) = \begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} \bullet \begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 1 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix}M(R^4) = M(R^3 \circ R) = M(R) \bullet M(R^3) =\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} \bullet \begin{bmatrix} 0 & 1 & 0 & 1 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} = M(R^2)因此其
R^4 之后的幂运算值 , 偶数次幂关系矩阵与
M(R^2) 值相同 , 奇数次幂关系矩阵与
M(R^3) 值相同 ;
M(t(R)) = M(R) \lor M(R^2) \lor M(R^3) =\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & 1 & 1 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix}四、闭包运算与关系性质
自反性
对称性
传递性
r
(
R
)
r(R)
r(R)
1
1
1 ( 本身性质 )
1
1
1
1
1
1
r
(
R
)
r(R)
r(R)
1
1
1
1
1
1 ( 本身性质 )
r
(
R
)
r(R)
r(R)
1
1
1
1
1
1
1
1
1 ( 本身性质 )
r(R)1 ( 本身性质 )
11r(R)11 ( 本身性质 )
r(R)111 ( 本身性质 )
上述表格中值为
1 , 说明原来存在该性质 , 求对应的 自反/对称/传递 闭包后 , 仍具有该性质 , 反之不具有该性质 ;
表格第二行含义 :
r(R) 对应的行 ;
自反性 : 假如 R 原来是自反的 , 那么
r(R) 也是自反的 ;
对称性 : 假如 R 原来是对称的 , 那么
r(R) 也是对称的 ; 求自反闭包 , 只是给顶点加环 , 不影响对称性 ;
传递性 : 假如 R 原来是传递的 , 那么
r(R) 也是传递的 ; 求自反闭包 , 只是给顶点加环 , 不影响传递性 ;
仅有一个特例 : 原来
R 是传递的 , 如果求对称闭包 , 其对称闭包的传递性就不存在了 ;
表格第二列说明 ( 自反性 ) : 如果
R 关系是自反的 , 那么其 对称闭包
s(R) 和 传递闭包
t(R) 也是自反的 ;
R 自反 \Rightarrow s(R) 和 t(R) 自反表格第三列说明 ( 对称性 ) : 如果
R 关系是对称的 , 那么其 自反闭包
r(R) 和 传递闭包
t(R) 也是对称的 ;
R 对称 \Rightarrow r(R) 和 t(R) 对称表格第四列说明 ( 传递性 ) : 如果
R 关系是传递的 , 那么其 自反闭包
r(R) 也是传递的 ;
R 传递 \Rightarrow r(R) 传递五、闭包复合运算R 关系是
A 集合上的二元关系 ,
R \subseteq A , 且
A 集合不为空集 ,
A \not= \varnothing1.
rs(R) = sr(R) :
rs( R ) : 先求 R 关系的 自反闭包 , 然后再求自反闭包的 对称闭包
sr( R ) : 先求 R 关系的对称闭包 , 然后再求对称闭包的自反闭包
上述两个闭包运算的 结果相同2.
rt(R) = tr(R)rt( R ) : 先求 R 关系的 自反闭包 , 然后再求自反闭包的 传递闭包
tr( R ) : 先求 R 关系的传递闭包 , 然后再求传递闭包的自反闭包
上述两个闭包运算的 结果相同3.
st(R) \subseteq ts(R)st( R ) : 先求 R 关系的 对称闭包 , 然后再求对称闭包的 传递闭包
ts( R ) : 先求 R 关系的传递闭包 , 然后再求传递闭包的对称闭包
上述两个闭包运算的结果 , ts(R) 关系 包含
st(R) 关系 ;