题目

已知一个有向图[1]的邻接矩阵[2]为 } 0 & 1 & 1 & 1 0 & 1 & 1 & 0 1 & 0 & 0 & 0 1 & 0 & 0 & 0

已知一个有向图[1]的邻接矩阵[2]为 $\begin{pmatrix} 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$，则它的可达矩阵为（）

A. $\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}$

B. $\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix}$

C. $\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}$

题目解答

答案

根据邻接矩阵 $ A $，逐层分析各顶点间路径： - 1 可达 1（1→3→1 或 1→4→1）、2、3、4。 - 2 可达 1（2→3→1）、2、3、4（2→3→1→4）。 - 3 可达 1、2（3→1→2）、3（3→1→3）、4（3→1→4）。 - 4 可达 1、2（4→1→2）、3（4→1→3）、4（4→1→4）。 综上，所有顶点间均可达，故可达矩阵为： \[ P = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix} \] 答案：B. \[ \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix} \]