木になる隣接行列
出典: 平成29年度 秋期 応用情報技術者試験 午前 問6 (IPA)
ノード 1～5 をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列の i 行 j 列目の成分は，ノード i とノード j を結ぶエッジがある場合は 1，ない場合は 0 とする。
- ア
- イ
- ウ
- エ
正解と解説を見る
正解: イ
- ア: エッジは 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 本で、全ノードがつながり閉路もないので木です。正しい答えです。
- ウ: エッジは 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 本で、閉路があるので木ではありません。
ポイント
- 木: 全てのノードがつながっていて、閉路 (ループ) がない グラフです。ノードが 5 個なら、エッジは必ず 4 本 です。
- 隣接行列は対称なので、1 の個数 ÷ 2 がエッジの本数です。
- イのエッジは 1−2，1−5，2−3，2−4 の 4 本で、全てのノードがつながり、閉路もありません。