応用情報技術者 2017年 秋期 午前2 問06
問題文
ノード 1〜5をもつグラフを隣接行列で表したもののうち、木となるものはどれか。ここで、隣接行列のi行j列目の成分は、ノードiとノードjを結ぶエッジがある場合は1、ない場合は0とする。
選択肢
ア：
イ：（正解）
ウ：
エ：
隣接行列で表したグラフのうち木となるものはどれか【午前2 解説】
要点まとめ
- 結論：選択肢イの隣接行列が示すグラフが木である。
- 根拠：木は「連結かつ閉路を持たない」無向グラフで、ノード数が5ならエッジ数は4である必要がある。
- 差がつくポイント：隣接行列からエッジ数を正確に数え、連結性と閉路の有無を判定できるかが重要。
正解の理由
選択肢イの隣接行列は、ノード数5に対してエッジ数が4本であり、すべてのノードが連結しているため木の条件を満たします。
他の選択肢はエッジ数が多すぎるか、閉路が存在するため木とは言えません。
他の選択肢はエッジ数が多すぎるか、閉路が存在するため木とは言えません。
よくある誤解
隣接行列の1の数を単純に数えるだけでなく、無向グラフのため対称行列であることを考慮し、エッジ数を正しく半分にする必要があります。
また、エッジ数が正しくても連結でなければ木とは言えません。
また、エッジ数が正しくても連結でなければ木とは言えません。
解法ステップ
- 隣接行列の1の数を数える（全体のエッジ数は1の数の半分）。
- ノード数が5なので、木ならエッジ数は4であることを確認。
- グラフが連結かどうかを判定（DFSやBFSで全ノードに到達可能か確認）。
- 閉路が存在しないかを確認（エッジ数と連結性の条件で判定可能）。
- 条件を満たす選択肢を選ぶ。
選択肢別の誤答解説
- ア：エッジ数が5本（1の数は10）で多く、閉路が存在するため木ではない。
- イ：エッジ数4本で連結、閉路なし。木の条件を満たす。
- ウ：エッジ数が6本（1の数12）で多く、閉路が存在する。
- エ：エッジ数が8本（1の数16）で多すぎ、明らかに閉路がある。
補足コラム
木は「連結かつ閉路なし」の無向グラフであり、ノード数 のときエッジ数は必ず です。
隣接行列は対称行列で、エッジ数は行列中の1の総数を2で割った値となります。
連結性の判定はDFSやBFSで簡単に行えます。
隣接行列は対称行列で、エッジ数は行列中の1の総数を2で割った値となります。
連結性の判定はDFSやBFSで簡単に行えます。
FAQ
Q: なぜエッジ数は でなければならないのですか？
A: 木は最小限のエッジで全ノードを連結する構造で、閉路がないためエッジ数はノード数より1少なくなります。
A: 木は最小限のエッジで全ノードを連結する構造で、閉路がないためエッジ数はノード数より1少なくなります。
Q: 隣接行列で閉路の有無はどう判断しますか？
A: 閉路の有無はエッジ数と連結性の関係から推測できます。エッジ数が を超える場合は閉路が存在します。
A: 閉路の有無はエッジ数と連結性の関係から推測できます。エッジ数が を超える場合は閉路が存在します。
関連キーワード: 隣接行列、木、グラフ理論、連結性、閉路検出
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！