基本情報技術者試験 基本情報技術者試験 令和2年度 科目A 修了認定試験 午前 問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、b-d、c-d、c-e、e-f）

選択肢

• ア.（選択肢ア）a-b-c-d-e-f に追加で別パターン
• イ.（選択肢イ）別パターン
• ウ.（選択肢ウ）a-b、b-c、b-d、c-d、c-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）から辺を読み取り、それと一致する図を選択する。

選択肢ごとの解説

• ア.行列の辺リストと一致しない図。
• イ.行列の辺リストと一致しない図。
• ウ.a-b、b-c、b-d、c-d、c-e、e-f の辺集合と一致する図=正解。
• エ.行列の辺リストと一致しない図。