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

正解：イ

AI解説

木とは「閉路(サイクル)をもたない連結グラフ」である。ノード数nの木の辺数は必ずn−1本なので、5ノードなら辺数4本、かつ全ノードがつながっていて閉路がないものを選ぶ。隣接行列は対称行列で、成分1の個数は辺数の2倍になることを使って辺数を数える。 ア: 辺数や連結性の条件を満たさず、閉路が生じる又はノードが分断されるため木ではない。 イ: 正解。辺数が4本(=5−1)で全ノードが連結し、閉路も存在しないため木である。 ウ: 閉路を含む構造になるため木の条件を満たさない。 エ: 閉路や非連結部分が生じる構造であり、木の条件を満たさない。 💡 木の判定は「辺数=ノード数−1」と「連結」の2条件を両方確認する。辺数だけ合っていても、閉路+孤立ノードの組合せがあり得るので片方だけでは判定できない。