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

問題本文

ノード 1 〜 5 をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列の i 行 j 列目の成分は，ノード i とノード j を結ぶエッジがある場合は 1，ない場合は 0 とする。

選択肢

• ア.01001 / 10100 / 01010 / 00101 / 10010
• イ.01001 / 10110 / 01000 / 01000 / 10000
• ウ.01010 / 10100 / 01011 / 10100 / 00100
• エ.01100 / 10100 / 11011 / 00101 / 00110

正解

イ. 01001 / 10110 / 01000 / 01000 / 10000

解説

木とは『閉路(サイクル)をもたず，全ノードがつながっている連結グラフ』であり，ノードが 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本もあり，閉路を含むため木にならない。