問題プレビューID: d8b9298d基本情報技術者試験 午前免除試験 2022年7月24日

問 2
基本情報技術者試験 午前免除試験 2022年7月24日

隣接行列 A で表されるグラフはどれか。ここで,隣接行列とは,n 個の節点から成るグラフの節点 Vᵢ と Vⱼ を結ぶ枝が存在するときは第 i 行第 j 列と第 j 行第 i 列の要素が 1 となり,存在しないときは 0 となる n 行 n 列の行列である。

〔隣接行列 A〕
       V₁ V₂ V₃ V₄
V₁      0  1  1  0
V₂      1  0  0  1
V₃      1  0  0  1
V₄      0  1  1  0
解説

正解は「エ」です。

隣接行列で 1 になっている成分が,節点間に枝(エッジ)があることを表します。与えられた行列から読み取れる枝は,V₁−V₂,V₁−V₃,V₂−V₄,V₃−V₄ です。これは V₁−V₂−V₄−V₃−V₁ の順に一周する四角形(閉路)になります。

  • エ: 枝の集合が {V₁−V₂, V₁−V₃, V₂−V₄, V₃−V₄} となり,隣接行列と一致します。正しい。
  • ア: V₁ が V₄ とのみ結ばれており,隣接行列にある V₁−V₂,V₁−V₃ の枝がありません。
  • イ: V₂−V₃ や V₁−V₄ など,隣接行列にない枝が余分にあります。
  • ウ: V₄ が V₁ とのみ結ばれており,隣接行列にある V₂−V₄,V₃−V₄ の枝がありません。

関連問題

本文が同じ・似ている問題を表示しています