修了試験 2022-12-11実施分 基本情報技術者試験 問7

解説

正解は2です。 木とは、すべてのノードがつながっていて（連結）、閉路を含まないグラフです。 ノードがn個の木では、エッジの数は必ずn－1本になります。 ノードが5個なので、エッジが4本で連結なものを探します。 隣接行列は対称なので、上半分の1を数えるとエッジの数が分かります。 【選択肢別解説】 1：× エッジは1-2、1-5、2-3、3-4、4-5の5本です。 1、2、3、4、5、1と一周する閉路があるので木ではありません。 2：○ エッジは1-2、1-5、2-3、2-4の4本です。 すべてのノードがつながり、閉路もないので木の条件を満たします。 3：× エッジは1-2、1-4、2-3、3-4、3-5の5本です。 1、2、3、4、1という閉路があるので木ではありません。 4：× エッジは1-2、1-3、2-3、3-4、3-5、4-5の6本です。 1、2、3の三角形と3、4、5の三角形という閉路があるので木ではありません。 【ポイント】 木かどうかは「エッジ数＝ノード数－1」と「連結」の2点で判断できます。 隣接行列では、行ごとの1の合計を2で割るとエッジ数になります。