問題プレビューID: def3a1e5基本情報技術者試験 午前免除試験 2022年6月12日

問 4
基本情報技術者試験 午前免除試験 2022年6月12日

ノードとノードの間のエッジの有無を,隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合,グラフで表現したものはどれか。ここで,ノードを隣接行列の行と列に対応させて,ノード間にエッジが存在する場合は 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
解説

正解は「ウ」です。

隣接行列で 1 になっている成分が,ノード間にエッジがあることを表します。与えられた行列から読み取れるエッジは,a-b,b-c,b-d,c-d,c-e,e-f です。すなわち,ノード b,c,d が互いに結ばれた三角形と,辺 a-b,辺 c-e,辺 e-f からなるグラフになります。

  • ウ: 辺の集合が {a-b, b-c, b-d, c-d, c-e, e-f} となり,隣接行列と一致します。正しい。
  • ア: b-c の辺がなく,隣接行列にない d-e の辺をもつため一致しません。
  • イ: c-d の辺がなく,隣接行列にない d-e の辺をもつため一致しません。
  • エ: 隣接行列にない d-e の辺が余分にあり,一致しません。

関連問題

本文が同じ・似ている問題を表示しています