隣接行列からグラフを描く
出典: 平成29年度 春期 応用情報技術者試験 午前 問3 (IPA)
ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は 1 で，エッジが存在しない場合は 0 で示す。
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 0 | 1 | 0 | 0 | 0 | 0 |
| b | 1 | 0 | 1 | 1 | 0 | 0 |
| c | 0 | 1 | 0 | 1 | 1 | 0 |
| d | 0 | 1 | 1 | 0 | 0 | 0 |
| e | 0 | 0 | 1 | 0 | 0 | 1 |
| f | 0 | 0 | 0 | 0 | 1 | 0 |
- ア
- イ
- ウ
- エ
正解と解説を見る
正解: ウ
- ア: c−d の間にエッジがなく、行列にない b−c が抜けた形になっています。行列と一致しません。
- イ: d−e のエッジがありますが、行列では d と e の間は 0 です。
- ウ: a−b、b−c、b−d、c−d、c−e、e−f の 6 本がちょうどそろっているので正しい答えです。
- エ: b−d ではなく b−d 以外の組や d−e などのエッジがあり、行列と一致しません。
ポイント
行列で 1 になっている組を書き出すと、エッジは次の 6 本です。
- a−b、b−c、b−d、c−d、c−e、e−f
無向グラフなので行列は対角線に対して対称です。各選択肢の図と、この 6 本が一致するものを探します。