問6応用情報技術者 平成29年度 秋期

解説

正解は2。木は、全てのノードがつながっていて閉路がないグラフで、ノードがn個ならエッジはn−1本。ここではノード5個なのでエッジは4本、対称な隣接行列なら1が8個になる。イは、エッジが1-2、1-5、2-3、2-4の4本で、全ノードがノード1・2を通じてつながり、閉路もないので木になる。

1（ア）は、エッジが1-2、1-5、2-3、3-4、4-5の5本で、1-2-3-4-5-1の閉路がある。
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）。