平成29年度 秋期 応用情報技術者試験 午前 問6
ノード 1 〜 5 をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列の i 行 j 列目の成分は，ノード i とノード j を結ぶエッジがある場合は 1，ない場合は 0 とする。
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：イ
木とは、全てのノードがつながっていて（連結）、閉路をもたないグラフです。ノード数が 5 の木のエッジ数は必ず 5 − 1 = 4 本になります。隣接行列は対称なので、右上半分の 1 の数がエッジの本数です。
選択肢の検討
-
ア: ア の隣接行列
誤り。エッジは 1-2、1-5、2-3、3-4、4-5 の 5 本です。1-2-3-4-5-1 という閉路があるので木ではありません。 -
イ: イ の隣接行列
正しい。エッジは 1-2、1-5、2-3、2-4 の 4 本です。ノード 5 個に対してエッジが 4 本で、全てのノードがつながっていて閉路がないので木です。 -
ウ: ウ の隣接行列
誤り。エッジは 1-2、1-4、2-3、3-4、3-5 の 5 本です。1-2-3-4-1 という閉路があるので木ではありません。 -
エ: エ の隣接行列
誤り。エッジは 1-2、1-3、2-3、3-4、3-5、4-5 の 6 本です。1-2-3-1 などの閉路があるので木ではありません。
答え
イ: イ の隣接行列
出典：平成29年度 秋期 応用情報技術者試験 午前 問6
