アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20221211 実施分 問7
ノード 1～5 をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列の i 行 j 列目の成分は，ノード i とノード j を結ぶエッジがある場合は 1，ない場合は 0 とする。
選択肢ア～エはいずれも 5×5 の隣接行列（各行を改行区切りで choices に記載）。
- ア [図] 5×5 隣接行列 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0
- イ [図] 5×5 隣接行列 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0
- ウ [図] 5×5 隣接行列 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0
- エ [図] 5×5 隣接行列 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0
出典：基本情報技術者試験 科目A免除 修了試験 20221211 実施分 問7
答えと解説を見る
正解：イ
覚える知識
隣接行列とグラフの対応読解
木とは、連結で閉路を持たず、辺の数がノード数-1のグラフである。
この問題で必要なこと
木は連結かつ閉路がなく、辺数がノード数-1となるグラフである。イは辺が4本で連結かつ閉路なしになる。
ひっかけ
アは5本の辺で環状(閉路あり)、ウとエは辺が多すぎたり閉路があったりして木にならない。
この知識の出題：本試験系 2 回・免除試験 4 回（公開問題での観測値）