問題プレビューID: 2cb1c1c7応用情報技術者試験 2017年(平成29年度)秋期 午前

問 6
応用情報技術者試験 2017年(平成29年度)秋期 午前

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

解説

正解は「イ」です。

ノード数が 5 の木は,閉路をもたず,かつ連結である必要があります。連結なグラフが木となる条件は,「エッジの本数がノード数 − 1 = 4 本」で「閉路がない」ことです。隣接行列の 1 の総数の半分がエッジの本数に当たります。

  • ア: 1 の数からエッジは 5 本(ノード数と同じ)あり,閉路をもつため木ではありません(5 個のノードが一つの輪になっています)。
  • イ: エッジは,1-2,1-5,2-3,2-4 の 4 本で,閉路がなく連結なので木となります。正しい。
  • ウ: エッジは 6 本(1-2,1-4,2-3,3-4,3-5)となり,1-2-3-4-1 の閉路をもつため木ではありません。
  • エ: エッジは 7 本と多く,複数の閉路をもつため木ではありません。

関連問題

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