平成24年度 春期 基本情報技術者試験 問3

解説

正解は4です。 隣接行列から、どの節点の間に枝があるかを読み取る問題です。 第i行第j列が1なら、節点V_iとV_jの間に枝があります。 【行列の読取り】 第1行は0,1,1,0なので、V_1はV_2とV_3につながっています。 第2行は1,0,0,1なので、V_2はV_1とV_4につながっています。 第3行は1,0,0,1なので、V_3はV_1とV_4につながっています。 第4行は0,1,1,0なので、V_4はV_2とV_3につながっています。 したがって枝はV_1-V_2、V_1-V_3、V_2-V_4、V_3-V_4の4本です。 V_1-V_4とV_2-V_3の間には枝がありません。 【選択肢別解説】 1：× 図のアは、V_4から放射状にV_1、V_2、V_3へ枝が出ています。 さらにV_2-V_3の枝もあり、V_1はV_4としかつながっていないため行列と一致しません。 2：× 図のイは、4つの節点すべてが互いにつながった完全グラフで、枝は6本です。 行列で0になっているV_1-V_4とV_2-V_3の枝まで存在するため誤りです。 3：× 図のウは、V_1がV_2、V_3、V_4とつながり、V_2-V_3の枝もあります。 V_4はV_1としかつながっておらず、行列のV_2-V_4、V_3-V_4の枝がありません。 4：○ 図のエは、V_1からV_2とV_3へ、V_4からV_2とV_3へ枝が出たひし形の形です。 枝は4本で、行列から読み取った枝の組と完全に一致します。 【ポイント】 無向グラフの隣接行列は対角線に関して対称になります。 各行の1の個数が、その節点につながる枝の本数（次数）になります。 本問では全節点の次数が2なので、それだけでも選択肢1〜3（図のア〜ウ）を除外できます。