| アドウィンテクノ塾

有向グラフの隣接行列

$n$ 個の頂点を持つ有向グラフに対し, 頂点 $i$ を始点とし頂点 $j$ を終点とするような辺がある時 $(i,j)$ 成分が $1$ であり, それ以外の成分は $0$ であるような $n$ 次正方行列をそのグラフの隣接行列という。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

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

頂点 $1$ から $2$, $1$ から $3$, $3$ から $2$ にそれぞれ辺が繋がっているので, $(1,2)$ 成分, $(1,3)$ 成分, $(3,2)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。

よって隣接行列は $ $\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ $ となる。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

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

頂点 $1$ から $2$, $1$ から $3$, $2$ から $1$ にそれぞれ辺が繋がっているので, $(1,2)$ 成分, $(1,3)$ 成分, $(2,1)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。

よって隣接行列は $ $\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$ $ となる。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

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

頂点 $1$ から $3$, $2$ から $1$, $2$ から $3$, $3$ から $1$ にそれぞれ辺が繋がっているので, $(1,3)$ 成分, $(2,1)$ 成分, $(2,3)$ 成分, $(3,1)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。

よって隣接行列は $ $\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ $ となる。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

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

頂点 $1$ から $1$, $1$ から $3$, $2$ から $1$, $2$ から $2$, $3$ から $2$ にそれぞれ辺が繋がっているので, $(1,1)$ 成分, $(1,3)$ 成分, $(2,1)$ 成分, $(2,2)$ 成分, $(3,2)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。

よって隣接行列は $ $\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ $ となる。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

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

頂点 $1$ から $2$, $2$ から $1$, $3$ から $3$ にそれぞれ辺が繋がっているので, $(1,2)$ 成分, $(2,1)$ 成分, $(3,3)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。

よって隣接行列は $ $\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ $ となる。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

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

頂点 $1$ から $1$, $1$ から $2$, $1$ から $3$, $1$ から $4$, $3$ から $3$ にそれぞれ辺が繋がっているので, $(1,1)$ 成分, $(1,2)$ 成分, $(1,3)$ 成分, $(1,4)$ 成分, $(3,3)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。

よって隣接行列は $ $\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$ $ となる。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

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

頂点 $1$ から $1$, $1$ から $2$

頂点 $2$ から $2$, $2$ から $3$, $2$ から $4$

頂点 $3$ から $1$, $3$ から $2$, $3$ から $3$

頂点 $4$ から $3$, $4$ から $4$ にそれぞれ辺が繋がっているので,

$(1,1)$ 成分, $(1,2)$ 成分, $(2,2)$ 成分, $(2,3)$ 成分, $(2,4)$ 成分, $(3,1)$ 成分, $(3,2)$ 成分, $(3,3)$ 成分, $(4,3)$ 成分, $(4,4)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。

よって隣接行列は $ $\begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{pmatrix}$ $ となる。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

$ $\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}$ $ となる。

次の有向グラフの隣接行列として最も適切なものを以下の選択肢から選びなさい。

有向グラフ

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

頂点 $1$ から $2$, $2$ から $4$, $4$ から $3$, $3$ から $1$ にそれぞれ辺が繋がっているので, $(1,2)$ 成分, $(2,4)$ 成分, $(4,3)$ 成分, $(3,1)$ 成分が $1$ で, それ以外の成分を $0$ とすればよい。

よって隣接行列は $ $\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$ $ となる。

有向グラフの隣接行列 09

有向グラフの隣接行列 08

有向グラフの隣接行列 07

有向グラフの隣接行列 06

有向グラフの隣接行列 05

有向グラフの隣接行列 04

有向グラフの隣接行列 03

有向グラフの隣接行列 02

有向グラフの隣接行列 01

学習コース

練習問題一覧