アルゴリズムとプログラミング
令和元年度 秋期 基本情報技術者試験 午前 問3
ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は 1 で，エッジが存在しない場合は 0 で示す。
隣接行列（行・列とも a b c d e f）:
選択肢のグラフはいずれもノード a〜f が横一列に並び，隣り合うノード間の直線と，c-e を結ぶ上側の弧，b-d を結ぶ下側の弧で構成される。
| 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 |
- ア [図] ノード a-f の無向グラフ。辺: a-b, c-d, d-e, e-f, c-e（上の弧）, b-d（下の弧）。b-c 間に辺なし
- イ [図] ノード a-f の無向グラフ。辺: a-b, b-c, d-e, e-f, c-e（上の弧）, b-d（下の弧）。c-d 間に辺なし
- ウ [図] ノード a-f の無向グラフ。辺: a-b, b-c, c-d, e-f, c-e（上の弧）, b-d（下の弧）。d-e 間に辺なし
- エ [図] ノード a-f の無向グラフ。辺: a-b, b-c, c-d, d-e, e-f, c-e（上の弧）, b-d（下の弧）
出典：令和元年度 秋期 基本情報技術者試験 午前 問3
答えと解説を見る
正解：ウ
覚える知識
隣接行列とグラフの対応読解
隣接行列は、ノード間にエッジがあれば1、なければ0を要素とする正方行列である。
この問題で必要なこと
隣接行列の1の位置から、エッジがあるノード対だけを拾ってグラフと照合する。
ひっかけ
1本だけエッジが欠けた、または余分なグラフを選ばせる。
この知識の出題：本試験系 2 回・免除試験 4 回（公開問題での観測値）