応用情報技術者試験 応用情報技術者試験 平成29年度秋期 午前 問6: ノード 1 〜 5 をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列の i 行 j 列目の成分は，ノード i とノード j を結

正解

イ. 01001 / 10110 / 01000 / 01000 / 10000

正答率 78.6%（721人中 567人が正解）

問題の解説

木は、閉路がなく全ての節点がつながったグラフであり、節点が5個なら辺は4本になる。無向グラフの隣接行列は辺1本につき1が2個並ぶので、1の個数が8個のものだけが候補になる。該当する行列は辺が1-2、1-5、2-3、2-4の4本で、五つの節点が全てつながり閉路もないので木である。

選択肢ごとの解説

• ア辺が1-2、2-3、3-4、4-5、5-1の5本あり、五つの節点が環状につながる閉路になっているので、木ではない。
• イ正しい。辺は1-2、1-5、2-3、2-4の4本で、五つの節点が全てつながり、閉路もないので木である。
• ウ辺が1-2、1-4、2-3、3-4、3-5の5本あり、1-2-3-4-1が閉路になるので、木ではない。
• エ辺が6本あり、1-2-3-1や3-4-5-3が閉路になるので、木ではない。