过程详情
【例子】关系的矩阵是:
\boldsymbol{W}_{0}=\left[\begin{array}{llll}
0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{array}\right]
$$
求传递闭包。
【分析与解答】
我们看第 1 列:$\pmatrix{0\\1\\1\\0}$。
$\pmatrix{\color{red}0\\1\\1\\0}$ $a_{11}=0$ 跳过。
$\pmatrix{0\\\color{blue}1\\1\\0}$ $a_{\color{green}2\color{red}1}=1$,则 $a_{\color{red}1}$ 行加到 $a_{\color{green}2}$ 行:
\boldsymbol{W}=\left[\begin{array}{llll}
\color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}1 \\
1+\color{blue}0 & 0+\color{blue}0 & 1+\color{blue}0 & 0+\color{blue}1 \\
1 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{array}\right]
$$
得到:
\boldsymbol{W}=\left[\begin{array}{llll}
0 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{array}\right]
$$
$\pmatrix{0\\1\\\color{blue}1\\0}$,$a_{31} = 1$,则 $a_1$ 行加到 $a_3$ 行,得到:
\boldsymbol{W}=\left[\begin{array}{llll}
0 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{array}\right]
$$
$\pmatrix{0\\1\\1\\\color{red}0}$,$a_{41} = 0$,跳过。
接下来是第二列(注意:不是原矩阵的第二列,而是上面处理后最后的矩阵的第二列,下同):
我们看第 2 列:$\pmatrix{0\\0\\0\\0}$。全是零,意味着 $a_{i2}$ 都跳过处理。
我们看第 3 列:$\pmatrix{0\\1\\0\\1}$
注意到 $a_{23} = 1$,则 $a_3$ 行加到 $a_2$ 行,得到:
\boldsymbol{W}=\left[\begin{array}{llll}
0 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{array}\right]
$$
注意到 $a_{43} = 1$,则 $a_3$ 行加到 $a_4$ 行,得到:
\boldsymbol{W}=\left[\begin{array}{llll}
0 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 1
\end{array}\right]
$$
我们看第 4 列:$\pmatrix{1\\1\\1\\1}$
注意到 $a_{14}\sim a_{44} = 1$,也就是 $a_4$ 行依次加到上面各行:
\boldsymbol{W}=\left[\begin{array}{llll}
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 1
\end{array}\right]
$$
\boldsymbol{W}=\left[\begin{array}{llll}
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 1
\end{array}\right]
$$
\boldsymbol{W}=\left[\begin{array}{llll}
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1
\end{array}\right]
$$
\boldsymbol{W}=\left[\begin{array}{llll}
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1
\end{array}\right]
$$
这就是最终正确答案。
例题
【例子】计算传递闭包之于:
\boldsymbol{A}=
\begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0
\end{bmatrix}
$$
【分析与解答】
按列从左到右,每列按行从上到下扫描:
$(4,1) = 1$,故:
\boldsymbol{T}=
\begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0
\end{bmatrix}
$$
$(1,2) = 1$,故:
\boldsymbol{T}=
\begin{bmatrix}
0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0
\end{bmatrix}
$$
$(4,2) = 1$,故:
\boldsymbol{T}=
\begin{bmatrix}
0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1
\end{bmatrix}
$$
$(4,3) = 1$,故:
\boldsymbol{T}=
\begin{bmatrix}
0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1
\end{bmatrix}
$$
$(1,4) = 1$,故:
\boldsymbol{T}=
\begin{bmatrix}
1 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1
\end{bmatrix}
$$
$(2,4) = 1$,故:
\boldsymbol{T}=
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1
\end{bmatrix}
$$
$(4,4) = 1$,故:
\boldsymbol{T}=
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1
\end{bmatrix}
$$
🦔最终解。