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

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

ノード 1〜5 をもつグラフを隣接行列で表したもののうち,木となるものはどれか。ここで,隣接行列の i 行 j 列目の成分は,ノード i とノード j を結ぶエッジがある場合は 1,ない場合は 0 とする。

解説

正解は「イ」です。

木とは,連結でかつ閉路(サイクル)をもたないグラフであり,ノード数が 5 のとき枝の本数は 4 本になります。各隣接行列から読み取れるエッジを確認します。

  • イ: エッジは 1-2,1-5,2-3,2-4 の 4 本で,すべてのノードが連結しており閉路もありません。木の条件を満たします。正しい。
  • ア: エッジは 1-2,1-5,2-3,3-4,4-5 の 5 本で,1-2-3-4-5-1 の閉路をもちます。
  • ウ: エッジは 1-2,1-4,2-3,3-4,3-5 の 5 本で,1-2-3-4-1 の閉路をもちます。
  • エ: エッジは 1-2,1-3,2-3,3-4,3-5,4-5 の 6 本で,閉路をもちます。

関連問題

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