アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20220612 実施分 問4
ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は1で，エッジが存在しない場合は0で示す。
隣接行列（行・列とも a b c d e f）:
| 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免除 修了試験 20220612 実施分 問4（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：ウ
覚える知識
隣接行列とグラフの対応読解
隣接行列は、ノードiとjの間にエッジがあれば(i,j)成分を1とするグラフの表現である。
この問題で必要なこと
隣接行列の1の位置からエッジを読み取る。a-b,b-c,b-d,c-d,c-e,e-fを満たす図を選ぶ。
ひっかけ
エッジが1本欠けた/余計な図を並べて、行列の読み落としを誘う。
この知識の出題：本試験系 2 回・免除試験 4 回（公開問題での観測値）