応用情報技術者 2017年 春期 午前2 問03
問題文
ノードとノードの間のエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列に対応させて、ノード間にエッジが存在する場合は1で、エッジが存在しない場合は0で示す。
選択肢
ア：
イ：
ウ：（正解）
エ：
隣接行列から無向グラフを読み取る問題【午前2 解説】
要点まとめ
- 結論：隣接行列の「1」はノード間にエッジがあることを示し、行と列の対応から正しい辺を特定します。
- 根拠：無向グラフの隣接行列は対称行列で、行a列bと行b列aが共に1ならa―b間にエッジが存在します。
- 差がつくポイント：対称性の確認と、行列の各行の「1」の位置を正確に読み取り、選択肢の辺と照合する力が問われます。
正解の理由
隣接行列の各行を見て、1がある列のノードとエッジがつながっています。
例えば、行aは〔0 1 0 0 0 0〕なのでa―b間にエッジがあります。
行bは〔1 0 1 1 0 0〕でa―b、b―c、b―dのエッジが存在。
同様にcはb、d、eとつながり、dはb、cとつながり、eはc、fとつながり、fはeとつながっています。
この情報を基に選択肢を比較すると、ウの辺の組み合わせが隣接行列と完全に一致します。
例えば、行aは〔0 1 0 0 0 0〕なのでa―b間にエッジがあります。
行bは〔1 0 1 1 0 0〕でa―b、b―c、b―dのエッジが存在。
同様にcはb、d、eとつながり、dはb、cとつながり、eはc、fとつながり、fはeとつながっています。
この情報を基に選択肢を比較すると、ウの辺の組み合わせが隣接行列と完全に一致します。
よくある誤解
隣接行列の対称性を見落とし、片方向だけのエッジを誤認することがあります。
また、行と列のラベル対応を間違え、誤ったノード間のエッジを選ぶミスも多いです。
また、行と列のラベル対応を間違え、誤ったノード間のエッジを選ぶミスも多いです。
解法ステップ
- 隣接行列の行と列のラベルを確認し、ノードの対応を把握する。
- 各行の「1」の位置を見て、どのノードとエッジがつながっているかをリストアップする。
- 無向グラフなので、行列は対称であることを確認し、エッジの重複を避ける。
- 選択肢のグラフの辺と照合し、すべてのエッジが一致するものを選ぶ。
- 不一致や余分な辺がある選択肢は除外する。
選択肢別の誤答解説
- ア：d―eのエッジが隣接行列にないのに存在し、c―dのエッジが抜けているため誤り。
- イ：d―eのエッジが誤って含まれており、隣接行列と不一致。
- ウ：隣接行列のエッジと完全に一致し、正解。
- エ：d―eのエッジが余分に含まれており、隣接行列にないため誤り。
補足コラム
隣接行列はノード数が多くなるとサイズが大きくなり非効率ですが、エッジの有無を高速に判定できる利点があります。
無向グラフの隣接行列は必ず対称行列になるため、対称性の確認は重要なチェックポイントです。
無向グラフの隣接行列は必ず対称行列になるため、対称性の確認は重要なチェックポイントです。
FAQ
Q: 無向グラフの隣接行列はなぜ対称になるのですか？
A: 無向グラフは辺に方向がないため、ノードaからbへのエッジがあればbからaへのエッジも同じで、行列の対応する要素が等しくなるためです。
A: 無向グラフは辺に方向がないため、ノードaからbへのエッジがあればbからaへのエッジも同じで、行列の対応する要素が等しくなるためです。
Q: 隣接行列と隣接リストの違いは何ですか？
A: 隣接行列はノード数×ノード数の二次元配列でエッジの有無を示し、隣接リストは各ノードに接続するノードのリストを保持します。隣接行列は高速判定、隣接リストはメモリ効率に優れます。
A: 隣接行列はノード数×ノード数の二次元配列でエッジの有無を示し、隣接リストは各ノードに接続するノードのリストを保持します。隣接行列は高速判定、隣接リストはメモリ効率に優れます。
関連キーワード: 隣接行列、無向グラフ、グラフ理論、エッジ判定、対称行列
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！