アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20210124 実施分 問3
ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は 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
- ア [図] ノード a〜f が横一列。エッジ: a-b，c-d，d-e，e-f，c-e（上の弧），b-d（下の弧）
- イ [図] ノード 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（下の弧）
出典：基本情報技術者試験 科目A免除 修了試験 20210124 実施分 問3
答えと解説を見る
正解：ウ
覚える知識
隣接行列とグラフの対応読解
隣接行列のi行j列が1ならノードiとjの間にエッジがあり、無向グラフでは対称行列になる。
この問題で必要なこと
隣接行列の1の位置が無向グラフのエッジに対応する。行列から辺はa-b、b-c、b-d、c-d、c-e、e-fで、d-eは存在しない。
ひっかけ
d-eなど存在しない辺を含む選択肢や、必要な辺が抜けた選択肢が紛らわしい。
この知識の出題：本試験系 2 回・免除試験 4 回（公開問題での観測値）