$n$ 個の頂点を持つ有向グラフに対し, 頂点 $i$ を始点とし頂点 $j$ を終点とするような辺がある時 $(i,j)$ 成分が $1$ であり, それ以外の成分は $0$ であるような $n$ 次正方行列をそのグラフの隣接行列という。
次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。
$\begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$
$\begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$
$\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}$
$\begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}$
頂点 $1$ から $3$, $2$ から $2$, $2$ から $3$, $3$ から $1$, $3$ から $2$, $3$ から $4$, $4$ から $3$ にそれぞれ辺が繋がっているので, $(1,3)$ 成分, $(2,2)$ 成分, $(2,3)$ 成分, $(3,1)$ 成分, $(3,2)$ 成分, $(3,4)$ 成分, $(4,3)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。
よって隣接行列は $\begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$ となる。