离散数学【关系】习题解析（二）自反对称传递，闭包，warshall_综合

1.求三大闭包

在这里插入图片描述
R的关系矩阵如下

$MR=[1010000101001000000110000]M_R=\begin{bmatrix} 1&0&1&0&0\\ 0&0&1&0&1\\ 0&0&1&0&0\\ 0&0&0&0&1\\ 1&0&0&0&0 \end{bmatrix}$
自反闭包r( R)将对角线补齐即可
$Mr(R)=[1010001101001000001110001]M_r(R)=\begin{bmatrix} 1&0&1&0&0\\ 0&1&1&0&1\\ 0&0&1&0&0\\ 0&0&0&1&1\\ 1&0&0&0&1 \end{bmatrix}$
对称闭包s( R)将矩阵沿着对角线补对称
$Ms(R)=[1010100101111000000111010]M_s(R)=\begin{bmatrix} 1&0&1&0&1\\ 0&0&1&0&1\\ 1&1&1&0&0\\ 0&0&0&0&1\\ 1&1&0&1&0 \end{bmatrix}$
传递闭包t( R)需要进行关系的复合
$M(R2)=[1010000101001000000110000]?[1010000101001000000110000]=[1010010100001001000010100]M(R^2)=\begin{bmatrix} 1&0&1&0&0\\ 0&0&1&0&1\\ 0&0&1&0&0\\ 0&0&0&0&1\\ 1&0&0&0&0 \end{bmatrix} \circ \begin{bmatrix} 1&0&1&0&0\\ 0&0&1&0&1\\ 0&0&1&0&0\\ 0&0&0&0&1\\ 1&0&0&0&0 \end{bmatrix}= \begin{bmatrix} 1&0&1&0&0\\ 1&0&1&0&0\\ 0&0&1&0&0\\ 1&0&0&0&0\\ 1&0&1&0&0 \end{bmatrix}$
因为2传递的
$R?R2=[1010000101001000000110000]?[1010010100001001000010100]=[1010010101001001000110100]R\bigcup R^2=\begin{bmatrix} 1&0&1&0&0\\ 0&0&1&0&1\\ 0&0&1&0&0\\ 0&0&0&0&1\\ 1&0&0&0&0 \end{bmatrix} \bigcup \begin{bmatrix} 1&0&1&0&0\\ 1&0&1&0&0\\ 0&0&1&0&0\\ 1&0&0&0&0\\ 1&0&1&0&0 \end{bmatrix}= \begin{bmatrix} 1&0&1&0&0\\ 1&0&1&0&1\\ 0&0&1&0&0\\ 1&0&0&0&1\\ 1&0&1&0&0 \end{bmatrix}$

$M(R3)=[1010010100001001010010100]M(R^3)=\begin{bmatrix} 1&0&1&0&0\\ 1&0&1&0&0\\ 0&0&1&0&0\\ 1&0&1&0&0\\ 1&0&1&0&0 \end{bmatrix}$

可以看出R³ $?\nsubseteq$ R $?\bigcup$ R²

所以
$R?R2?R3=[1010000101001000000110000]?[1010010100001001000010100]?[1010010100001001010010100]=[1010010101001001010110100]R\bigcup R^2\bigcup R^3=\begin{bmatrix} 1&0&1&0&0\\ 0&0&1&0&1\\ 0&0&1&0&0\\ 0&0&0&0&1\\ 1&0&0&0&0 \end{bmatrix} \bigcup \begin{bmatrix} 1&0&1&0&0\\ 1&0&1&0&0\\ 0&0&1&0&0\\ 1&0&0&0&0\\ 1&0&1&0&0 \end{bmatrix} \bigcup \begin{bmatrix} 1&0&1&0&0\\ 1&0&1&0&0\\ 0&0&1&0&0\\ 1&0&1&0&0\\ 1&0&1&0&0 \end{bmatrix}= \begin{bmatrix} 1&0&1&0&0\\ 1&0&1&0&1\\ 0&0&1&0&0\\ 1&0&1&0&1\\ 1&0&1&0&0 \end{bmatrix}$

$M(R4)=[1010010100001001010010100]M(R^4)=\begin{bmatrix} 1&0&1&0&0\\ 1&0&1&0&0\\ 0&0&1&0&0\\ 1&0&1&0&0\\ 1&0&1&0&0 \end{bmatrix}$

发现 R⁴ $?\subseteq$ R $?\bigcup$ R² $?\bigcup$ R³

所以t(R)=R $?\bigcup$ R² $?\bigcup$ R³

2. warshall算法

在这里插入图片描述
R的关系图如下

在这里插入图片描述
R的关系矩阵如下
$M(R)=[000011000000101000000010010000000000]M(R)=\begin{bmatrix} 0&0&0&0&1&1\\ 0&0&0&0&0&0\\ 1&0&1&0&0&0\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix}$
warshall算法的核心是，从列开始计算，在为1的元素中，身处在那x列就将x行的值加入当前元素所在的行
$M31=[000011000000101011000010010000000000]M31=\begin{bmatrix} 0&0&0&0&1&1\\ 0&0&0&0&0&0\\ 1&0&1&0&1&1\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix}$

$M52=[000011000000101011000010010000000000]M52=\begin{bmatrix} 0&0&0&0&1&1\\ 0&0&0&0&0&0\\ 1&0&1&0&1&1\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix}$

$M33=[000011000000101011000010010000000000]M33=\begin{bmatrix} 0&0&0&0&1&1\\ 0&0&0&0&0&0\\ 1&0&1&0&1&1\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix}$

$M15=[010011000000101011000010010000000000]M35=[010011000000111011000010010000000000]M45=[010011000000111011010010010000000000]M15=\begin{bmatrix} 0&1&0&0&1&1\\ 0&0&0&0&0&0\\ 1&0&1&0&1&1\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix} M35=\begin{bmatrix} 0&1&0&0&1&1\\ 0&0&0&0&0&0\\ 1&1&1&0&1&1\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix} M45=\begin{bmatrix} 0&1&0&0&1&1\\ 0&0&0&0&0&0\\ 1&1&1&0&1&1\\ 0&1&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix}$

$M16=M36=[010011000000111011010010010000000000]M16=M36=\begin{bmatrix} 0&1&0&0&1&1\\ 0&0&0&0&0&0\\ 1&1&1&0&1&1\\ 0&1&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix}$

M36就是她的传递闭包t(R)，关系图为，其中红色线（代替虚线更加明显）部分是新加入的序偶

在这里插入图片描述

3 求传递闭包和对称闭包

在这里插入图片描述
关系矩阵如下
$M(R)=[0101110100000111010001011]M(R)=\begin{bmatrix} 0&1&0&1&1\\ 1&0&1&0&0\\ 0&0&0&1&1\\ 1&0&1&0&0\\ 0&1&0&1&1\\ \end{bmatrix}$
其对称闭包为，只需将矩阵沿对角线补齐即可
$Ms(R)=[0101110101010111010111111]M_s(R)=\begin{bmatrix} 0&1&0&1&1\\ 1&0&1&0&1\\ 0&1&0&1&1\\ 1&0&1&0&1\\ 1&1&1&1&1\\ \end{bmatrix}$
传递闭包的warshall算法
$M21=[0101111111000111010001011]M41=[0101111111000111111101011]M21=\begin{bmatrix} 0&1&0&1&1\\ 1&1&1&1&1\\ 0&0&0&1&1\\ 1&0&1&0&0\\ 0&1&0&1&1\\ \end{bmatrix} M41=\begin{bmatrix} 0&1&0&1&1\\ 1&1&1&1&1\\ 0&0&0&1&1\\ 1&1&1&1&1\\ 0&1&0&1&1\\ \end{bmatrix}$

$M12=[1111111111000111111101011]M52=[1111111111000111111111111]M12=\begin{bmatrix} 1&1&1&1&1\\ 1&1&1&1&1\\ 0&0&0&1&1\\ 1&1&1&1&1\\ 0&1&0&1&1\\ \end{bmatrix} M52=\begin{bmatrix} 1&1&1&1&1\\ 1&1&1&1&1\\ 0&0&0&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ \end{bmatrix}$

$M34=[1111111111111111111111111]=t(R)M34=\begin{bmatrix} 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ \end{bmatrix}=t(R)$

所以传递闭包t(R)为M34

等价类定义如下
在这里插入图片描述

5 求直积

在这里插入图片描述
P(A)={A的所有子集的集合}=2^A
求P(A)与A的直积

AXP(A)={<a,a>,<a, $?\emptyset$ >,<a,b>,<a,a,b>,<b,a>,<b,b>,<b, $?\emptyset$ >,<b,a,b>}

6 判断集合类型

在这里插入图片描述
(1) R={<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4>,<2,6>,<4,1>,<4,2>,<,4,4>,<4,6>,<6,1>,<6,2>,<6,4>,<6,6>}

没有<1,1>有<2,2>所以既不是反自反也不是自反

每一条线都有反向的所以是对称的

是可传递的

(2)R={<1,1>,<2,1>,<2,2>,<4,1>,<4,2>,<4,4>,<6,1>,<6,2>,<6,6>}

每个节点都有自旋，所以是自反的

任何不相等的节点连线都只有一条，所以是反对称的

不是可传递的

7 求t( R)

在这里插入图片描述
R关系矩阵如下

	b	c	d	e
a	1	0	0	0
b	0	1	0	1
c	0	0	1	0
d	0	1	0	0
e	0	0	0	1

包含的序偶

R={<a,b>,<b,c>,<b,e>,<c,d>,<d,c>,<e,e>}

r?={<a,a>,<a,b>,<b,b>,<b,c>,<b,e>,<c,c>,<c,d>,<d,c>,<d,d>,<e,e>}

s(R)={<a,b>,<b,a>,<b,c>,<b,e>,<c,b>,<c,d>,<d,c>,<e,b>,<e,e>}

使用warshall算法求得的传递闭包
$R)=\begin{bmatrix} 0&1&0&0&0\\ 0&0&1&0&1\\ 0&0&0&1&0\\ 0&0&1&0&0\\ 0&0&0&0&1 \end{bmatrix} M12=\begin{bmatrix} 0&1&1&0&1\\ 0&0&1&0&1\\ 0&0&0&1&0\\ 0&0&1&0&0\\ 0&0&0&0&1 \end{bmatrix}$

$M13=[0111100101000100010000001]M23=[0111100111000100010000001]M43=[0111100111000100011000001]M13=\begin{bmatrix} 0&1&1&1&1\\ 0&0&1&0&1\\ 0&0&0&1&0\\ 0&0&1&0&0\\ 0&0&0&0&1 \end{bmatrix} M23=\begin{bmatrix} 0&1&1&1&1\\ 0&0&1&1&1\\ 0&0&0&1&0\\ 0&0&1&0&0\\ 0&0&0&0&1 \end{bmatrix} M43=\begin{bmatrix} 0&1&1&1&1\\ 0&0&1&1&1\\ 0&0&0&1&0\\ 0&0&1&1&0\\ 0&0&0&0&1 \end{bmatrix}$

$M34=[0111100111001100011000001]M34=\begin{bmatrix} 0&1&1&1&1\\ 0&0&1&1&1\\ 0&0&1&1&0\\ 0&0&1&1&0\\ 0&0&0&0&1 \end{bmatrix}$

$M55=[0111100111000100011000001]M55=\begin{bmatrix} 0&1&1&1&1\\ 0&0&1&1&1\\ 0&0&0&1&0\\ 0&0&1&1&0\\ 0&0&0&0&1 \end{bmatrix}$

所以t(R)=M55