アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20220724 実施分 問2
隣接行列 A で表されるグラフはどれか。ここで，隣接行列とは，n 個の節点から成るグラフの節点 Vi と Vj を結ぶ枝が存在するときは第 i 行第 j 列と第 j 行第 i 列の要素が 1 となり，存在しないときは 0 となる n 行 n 列の行列である。
〔隣接行列 A〕
[0 1 1 0]
[1 0 0 1]
[1 0 0 1]
[0 1 1 0]
選択肢はいずれも節点 V1〜V4 のグラフ図。
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20220724 実施分 問2（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：エ
覚える知識
隣接行列とグラフの対応読解
隣接行列は、節点間に枝があれば1、なければ0とするn行n列の行列である。
この問題で必要なこと
隣接行列の第i行第j列が1なら節点ViとVjを結ぶ枝がある。行列から枝の集合を読み取り、図と照合する。
ひっかけ
枝の有無の読み違い(例えばV1-V4を結んでしまう)を狙った選択肢で、行列と図の対応を誤らせる。
この知識の出題：本試験系 2 回・免除試験 4 回（公開問題での観測値）