基本情報技術者試験 基本情報技術者試験 令和元年度 秋期 午前 午前 問3: ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対

問題本文

ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させ，ノード間にエッジが存在する場合は1で，エッジが存在しない場合は0で示す。 a b c d e f a 0 1 0 0 0 0 b 1 0 1 1 0 0 c 0 1 0 1 1 0 d 0 1 1 0 0 0 e 0 0 1 0 0 1 f 0 0 0 0 1 0

選択肢

• ア.ノード接続: a-b, b-c, c-d, c-e, d-e, e-f
• イ.ノード接続: a-b, b-c, b-d, c-e, d-e, e-f
• ウ.ノード接続: a-b, b-c, b-d, c-d, c-e, e-f
• エ.ノード接続: a-b, b-c, b-d, c-d, d-e, e-f

正解

ウ. ノード接続: a-b, b-c, b-d, c-d, c-e, e-f

解説

行列の1の位置: (a,b),(b,c),(b,d),(c,d),(c,e),(e,f)。これに一致するグラフがウ。

選択肢ごとの解説

• ア.c-d, d-e のエッジは合うが b-d がないので不一致。
• イ.d-e があり c-d がないので行列と不一致。
• ウ.a-b, b-c, b-d, c-d, c-e, e-f を含み一致=正解。
• エ.d-e があり c-e がないので行列と不一致。