ノード1～5をもつグラフを隣接行列で表したもののうち，木となるものはどれか。
ここで，隣接行列のi行j列目の成分は，ノードiとノードjを結ぶエッジがある場合は1，ない場合は0とする。
正答2
解説
正解は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-1と3-4-5-3という閉路があるので木ではありません。
【ポイント】
「連結で、辺の数が節点数より1少ない」グラフは木です。
まず辺の数を数えて4本でないものを除外すると、素早く解けます。