基本情報技術者試験 - 令和4年12月修了 - 問7

答え ： イ
分野 ： テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › データ構造
解説 ：
「木」とは，グラフ理論において，全てのノードが連結されており，かつ閉路（サイクル）を持たない構造のグラフのことです。ノードが5個ある木の場合，辺（エッジ）の数はノードの数より1少ない4本になります。隣接行列は対称な行列であり，対角成分（自分自身との関係を示す部分）は必ず0になります。

この問題では，各選択肢に示された隣接行列について，行列内の1の個数（エッジの数）を数え，さらにその構造が閉路を持たず全てのノードが連結されているかどうかを確認する必要があります。

選択肢「イ」の隣接行列は，1の個数がちょうど木の条件を満たす数になっており，かつ全てのノードが連結され，閉路も存在しない構造になっているため，これが木となります。

他の選択肢の行列は，エッジの数が多すぎて閉路ができてしまっていたり，逆に少なすぎて一部のノードが孤立してしまっていたりするため，木の条件を満たしません。