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

正解

イ. 01001 / 10110 / 01000 / 01000 / 10000

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

問題の解説

木とは『閉路(サイクル)をもたず，全ノードがつながっている連結グラフ』であり，ノードが n 個なら辺はちょうど n−1 本になる。ノード5個なら辺は4本，無向グラフの対称な隣接行列では1の個数は辺数の2倍=8個でなければならない。イは1が8個で辺が(1,2)(1,5)(2,3)(2,4)の4本，全ノードが連結し閉路もないため木になり，イが正しい。ア・ウ・エは1の個数が10〜12個=辺が5〜6本あり，必ず閉路を含むので木にならない。

選択肢ごとの解説

• ア誤り。1の個数が10個=辺が5本あり，ノード5個で辺5本だと必ず閉路が生じるため木にならない。
• イ正しい。辺は(1,2)(1,5)(2,3)(2,4)の4本ちょうど。全ノードが連結し閉路がないので木の条件を満たす。
• ウ誤り。1の個数が10個=辺が5本で，辺数がノード数−1を超えるため閉路を含み木にならない。
• エ誤り。1の個数が12個=辺が6本もあり，閉路を含むため木にならない。