平成24年度 春期 基本情報技術者試験 午前 問3
テクノロジ／基礎理論隣接行列 A で表されるグラフはどれか。ここで，隣接行列とは，n 個の節点から成るグラフの節点 Vi と Vj を結ぶ枝が存在するときは第 i 行第 j 列と第 j 行第 i 列の要素が1となり，存在しないときは0となる n 行 n 列の行列である。
出典：平成24年度 春期 基本情報技術者試験 午前 問3
- アグラフア
- イグラフイ
- ウグラフウ
- エグラフエ
正解：エ
解説
隣接行列の1の位置を読み取ると，V1-V2，V1-V3，V2-V4，V3-V4 の4本の枝があり，V1-V4 と V2-V3 の枝は存在しません（対角成分は0で自己ループもなし）。これは V1→V2→V4→V3→V1 とたどる4頂点のサイクル（環）になっています。この4本の枝の組合せと完全に一致するグラフを選びます。
選択肢ごとの解説
- ア誤り。V1とV4を結ぶ枝が含まれ，V2とV3を結ぶ枝が含まれるなど，隣接行列の枝の組合せと一致しません。
- イ誤り。V1とV4を結ぶ枝を含み，行列に無い枝が含まれています。
- ウ誤り。V1とV4を結ぶ枝を含み，行列に無い枝が含まれています。
- エ正しい。V1-V2，V1-V3，V2-V4，V3-V4 の4本の枝から成る4頂点のサイクルで，V1-V4とV2-V3の枝がなく，隣接行列と完全に一致します。