题目

已知一个有向图[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} \]

解析

本题考查有向图的邻接矩阵与可达矩阵的知识。解题思路是根据邻接矩阵判断图中各顶点之间是否存在路径，若存在路径则可达矩阵对应位置为 1，不存在路径则为 0。具体通过分析每个顶点到其他顶点的可达性来确定可达矩阵。
设邻接矩阵为 $A=\begin{pmatrix} 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$。

  1. 分析顶点 1 的可达性：
    • 从顶点 1 出发，根据邻接矩阵可知，顶点 1 直接可达顶点 2、3、4，即 $A_{12}=1$，$A_{13}=1$，$A_{14}=1$。
    • 对于顶点 1 到自身，存在路径 $1→3→1$ 或 $1→4→1$，所以顶点 1 可达顶点 1。
    • 综上，顶点 1 可达顶点 1、2、3、4。
  2. 分析顶点 2 的可达性：
    • 从顶点 2 出发，根据邻接矩阵可知，顶点 2 直接可达顶点 3，即 $A_{23}=1$。
    • 因为顶点 3 可达顶点 1，所以顶点 2 可达顶点 1（路径为 $2→3→1$）。
    • 又因为顶点 1 可达顶点 2、4，所以顶点 2 可达顶点 2、4（路径 $2→3→1→2$ 和 $2→3→1→4$）。
    • 综上，顶点 2 可达顶点 1、2、3、4。
  3. 分析顶点 3 的可达性：
    • 从顶点 3 出发，根据邻接矩阵可知，顶点 3 直接可达顶点 1，即 $A_{31}=1$。
    • 因为顶点 1 可达顶点 2、3、4，所以顶点 3 可达顶点 2（路径为 $3→1→2$）、3（路径为 $3→1→3$）、4（路径为 $3→1→4$）。
    • 综上，顶点 3 可达顶点 1、2、3、4。
  4. 分析顶点 4 的可达性：
    • 从顶点 4 出发，根据邻接矩阵可知，顶点 4 直接可达顶点 1，即 $A_{41}=1$。
    • 因为顶点 1 可达顶点 2、3、4，所以顶点 4 可达顶点 2（路径为 $4→1→2$）、3（路径为 $4→1→3$）、4（路径为 $4→1→4$）。
    • 综上，顶点 4 可达顶点 1、2、3、4。

由于所有顶点间均可达，所以可达矩阵 $P$ 中所有元素都为 1，即 $P = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix}$。